LoginSignup
6
3

More than 5 years have passed since last update.

@kzkiq2ndin株式会社LIFULL

AtCoder過去問精選10問をGo + テスト付きで解いてみた

Posted at

Goの標準テスト練習として、テストファーストで AtCoder に登録したら解くべき精選 10 問 を解いてみました。

第 1 問: ABC 086 A - Product (100 点)

標準入力出力と関数を分け、出題の入出力例を Table Driven Tests に書き換えています。

main.go
package main

import "fmt"

func main() {
    var a, b int
    fmt.Scan(&a, &b)
    fmt.Println(evenodd(a * b))
}

func evenodd(i int) string {
    if i%2 == 0 {
        return "Even"
    }
    return "Odd"
}
main_test.go
package main

import "testing"

func TestEvenodd(t *testing.T) {
    cases := map[string]struct {
        a, b int
        want string
    }{
        "1": {a: 3, b: 4, want: "Even"},
        "2": {a: 1, b: 21, want: "Odd"},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := evenodd(tc.a * tc.b); got != tc.want {
                t.Fatalf("want = %v, got = %v", tc.want, got)
            }
        })
    }
}

第 2 問: ABC 081 A - Placing Marbles (100 点)

A問題くらいだとテストコードの方が長くなりますね。

main.go
package main

import "fmt"

func main() {
    var input string
    fmt.Scan(&input)
    fmt.Println(one(input))
}

func one(input string) int {
    var i int
    for n := range input {
        if input[n] == '1' {
            i++
        }
    }
    return i
}
main_test.go
package main

import "testing"

func TestOne(t *testing.T) {
    cases := map[string]struct {
        in   string
        want int
    }{
        "1": {in: "101", want: 2},
        "2": {in: "000", want: 0},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := one(tc.in); got != tc.want {
                t.Fatalf("want = %v, got = %v", tc.want, got)
            }
        })
    }
}

第 3 問: ABC 081 B - Shift Only (200 点)

テストファーストだと、テストケース構造体を書く時に標準入力の格納方法を考える、という思考順序になりました。

main.go
package main

import "fmt"

func change(n int, list []int) int {
    var c int
    var oddFlag bool
    for {
        for i, num := range list {
            if num%2 != 0 {
                oddFlag = true
                break
            }
            list[i] = num / 2
        }
        if oddFlag == true {
            break
        }
        c++
    }
    return c
}

func main() {
    var n int
    fmt.Scan(&n)
    a := make([]int, n)
    for i := range a {
        fmt.Scan(&a[i])
    }
    fmt.Println(change(n, a))
}
main_test.go
package main

import "testing"

func TestChange(t *testing.T) {
    cases := map[string]struct {
        n    int
        list []int
        want int
    }{
        "1": {n: 3, list: []int{8, 12, 40}, want: 2},
        "2": {n: 4, list: []int{5, 6, 8, 10}, want: 0},
        "3": {n: 4, list: []int{382253568, 723152896, 37802240, 379425024, 404894720, 471526144}, want: 8},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := change(tc.n, tc.list); got != tc.want {
                t.Fatalf("want %v, got %v", tc.want, got)
            }
        })
    }
}

第 4 問: ABC 087 B - Coins (200 点)

main.go
package main

import "fmt"

func coins(a, b, c, x int) int {
    var cnt int
    for i := 0; i <= a; i++ {
        for j := 0; j <= b; j++ {
            for k := 0; k <= c; k++ {
                if 500*i+100*j+50*k == x {
                    cnt++
                }
            }
        }
    }
    return cnt
}

func main() {
    var a, b, c, x int
    fmt.Scan(&a, &b, &c, &x)
    fmt.Println(coins(a, b, c, x))
}
main_test.go
package main

import "testing"

func TestPattern(t *testing.T) {
    cases := map[string]struct {
        a, b, c, x int
        want       int
    }{
        "1": {a: 2, b: 2, c: 2, x: 100, want: 2},
        "2": {a: 5, b: 1, c: 0, x: 150, want: 0},
        "3": {a: 30, b: 40, c: 50, x: 6000, want: 213},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := coins(tc.a, tc.b, tc.c, tc.x); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

第 5 問: ABC 083 B - Some Sums (200 点)

main.go
package main

import "fmt"

func main() {
    var n, a, b int
    fmt.Scan(&n, &a, &b)
    fmt.Println(sum(n, a, b))
}

func sum(n, a, b int) int {
    var t int
    for i := 1; i <= n; i++ {
        s := sumDigits(i)
        if s >= a && s <= b {
            t += i
        }
    }
    return t
}

func sumDigits(n int) int {
    var s int
    for n > 0 {
        s += n % 10
        n /= 10
    }
    return s
}
main_test.go
package main

import "testing"

func TestSum(t *testing.T) {
    cases := map[string]struct {
        n, a, b, want int
    }{
        "1": {n: 20, a: 2, b: 5, want: 84},
        "2": {n: 10, a: 1, b: 2, want: 13},
        "3": {n: 100, a: 4, b: 16, want: 4554},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := sum(tc.n, tc.a, tc.b); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

第 6 問: ABC 088 B - Card Game for Two (200点)

main.go
package main

import (
    "fmt"
    "sort"
)

func game(n int, a []int) int {
    var diff int
    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    for i, num := range a {
        if i%2 == 0 {
            diff += num
        } else {
            diff -= num
        }
    }
    return diff
}

func main() {
    var n int
    fmt.Scan(&n)
    a := make([]int, n)
    for i := range a {
        fmt.Scan(&a[i])
    }
    fmt.Println(game(n, a))
}
main_test.go
package main

import "testing"

func TestGame(t *testing.T) {
    cases := map[string]struct {
        n    int
        a    []int
        want int
    }{
        "1": {n: 2, a: []int{3, 1}, want: 2},
        "2": {n: 3, a: []int{2, 7, 4}, want: 5},
        "3": {n: 4, a: []int{20, 18, 2, 18}, want: 18},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := game(tc.n, tc.a); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

第 7 問: ABC 085 B - Kagami Mochi (200点)

main.go
package main

import "fmt"

func bucket(d []int) int {
    b := map[int]int{}
    for i := range d {
        b[d[i]]++
    }
    return len(b)
}

func main() {
    var n int
    fmt.Scan(&n)
    d := make([]int, n)
    for i := range d {
        fmt.Scan(&d[i])
    }
    fmt.Println(bucket(d))
}
main_test.go
package main

import "testing"

func TestMochi(t *testing.T) {
    cases := map[string]struct {
        n    int
        d    []int
        want int
    }{
        "1": {n: 4, d: []int{10, 8, 8, 6}, want: 3},
        "2": {n: 3, d: []int{15, 15, 15}, want: 1},
        "3": {n: 7, d: []int{50, 30, 50, 100, 50, 80, 30}, want: 4},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := bucket(tc.d); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

第 8 問: ABC 085 C - Otoshidama (300点)

この 085C の様にケースに対する回答が複数パターンあるものの扱いはちょっと考えています。

main.go
package main

import (
    "fmt"
)

func dama(n, y int) (int, int, int) {
    d := make([]int, n+1)
    a, b, c := -1, -1, -1
    for i := range d {
        for j := range d {
            k := n - i - j
            if k < 0 {
                continue
            }
            if y == 10000*i+5000*j+1000*k {
                a = i
                b = j
                c = k
                return a, b, c
            }
        }
    }
    return a, b, c
}

func main() {
    var n, y int
    fmt.Scan(&n, &y)
    fmt.Println(dama(n, y))
}
main_test.go
package main

import (
    "reflect"
    "testing"
)

func TestDama(t *testing.T) {
    cases := map[string]struct {
        n, y int
        want []int
    }{
        "1": {n: 9, y: 45000, want: []int{0, 9, 0}},
        "2": {n: 20, y: 196000, want: []int{-1, -1, -1}},
        "3": {n: 1000, y: 1234000, want: []int{2, 54, 944}},
        "4": {n: 2000, y: 20000000, want: []int{2000, 0, 0}},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            a, b, c := dama(tc.n, tc.y)
            got := []int{a, b, c}
            if !reflect.DeepEqual(got, tc.want) {
                t.Fatalf("want is %v , got is %v", tc.want, got)
            }
        })
    }
}

第 9 問: ABC 049 C - Daydream (300点)

main.go
package main

import (
    "fmt"
)

func dream(s string) string {
    dp := make([]int, len(s)+1)
    dp[0] = 1
    for i := range s {
        if dp[i] == 0 {
            continue
        }
        if i+5 <= len(s) && s[i:i+5] == "dream" {
            dp[i+5] = 1
        }
        if i+7 <= len(s) && s[i:i+7] == "dreamer" {
            dp[i+7] = 1
        }
        if i+5 <= len(s) && s[i:i+5] == "erase" {
            dp[i+5] = 1
        }
        if i+6 <= len(s) && s[i:i+6] == "eraser" {
            dp[i+6] = 1
        }
    }
    if dp[len(s)] == 1 {
        return "YES"
    }
    return "NO"
}

func main() {
    var s string
    fmt.Scan(&s)
    fmt.Println(dream(s))
}
main_test.go
package main

import "testing"

func TestDream(t *testing.T) {
    cases := map[string]struct {
        s, want string
    }{
        "1": {s: "erasedream", want: "YES"},
        "2": {s: "dreameraser", want: "YES"},
        "3": {s: "dreamerer", want: "NO"},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := dream(tc.s); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

第10問: ABC 086 C - Traveling (300点)

main.go
package main

import (
    "fmt"
    "math"
)

func abs(n int) int {
    return int(math.Abs(float64(n)))
}

func travel(n int, t, x, y []int) string {
    post, posx, posy := 0, 0, 0
    for i := range t {
        difft := abs(t[i] - post)
        diffx := abs(x[i] - posx)
        diffy := abs(y[i] - posy)
        if difft < diffx+diffy {
            return "No"
        }
        if difft%2 != (diffx+diffy)%2 {
            return "No"
        }
        post = t[i]
        posx = x[i]
        posy = y[i]
    }
    return "Yes"
}

func main() {
    var n int
    fmt.Scan(&n)
    time, x, y := make([]int, n), make([]int, n), make([]int, n)
    for i := range time {
        fmt.Scan(&time[i])
        fmt.Scan(&x[i])
        fmt.Scan(&y[i])
    }
    fmt.Println(travel(n, time, x, y))
}
main_test.go
package main

import "testing"

func TestTravel(t *testing.T) {
    cases := map[string]struct {
        n          int
        time, x, y []int
        want       string
    }{
        "1": {n: 2, time: []int{3, 6}, x: []int{1, 1}, y: []int{2, 1}, want: "Yes"},
        "2": {n: 1, time: []int{2}, x: []int{100}, y: []int{100}, want: "No"},
        "3": {n: 2, time: []int{5, 100}, x: []int{1, 1}, y: []int{1, 1}, want: "No"},
    }

    for n, tc := range cases {
        tc := tc
        t.Run(n, func(t *testing.T) {
            if got := travel(tc.n, tc.time, tc.x, tc.y); got != tc.want {
                t.Fatalf("want is %v, got is %v", tc.want, got)
            }
        })
    }
}

まとめ

解くスピードを競う点に関して一切メリットが無いですが、標準テスト書きの素振りにおすすめです。

6
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
3