LoginSignup
1
0

More than 5 years have passed since last update.

@kzkiq2ndin株式会社LIFULL

AtCoder過去問精選「ここまで解いたら」11 問を Go + テスト付きで解いてみた

Last updated at Posted at 2019-01-14

AtCoder に登録したら解くべき精選 10 問 のオマケ 11 問を Go の標準テスト付きで解きました。

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita

グリッドに関する処理：ABC 075 B(200点)

↓の様に入力されるグリッドを、スライスのインデックスでとらえる。

.....
.#.#.
.....
main.go
package main

import (
    "fmt"
    "strconv"
)

func main() {
    var f, w int
    fmt.Scan(&f, &w)
    maps := make([]string, f)
    for i := range maps {
        fmt.Scan(&maps[i])
    }
    for _, out := range mine(f, w, maps) {
        fmt.Println(out)
    }
}

func mine(f, w int, maps []string) []string {
    dx := []int{-1, 0, 1, -1, 1, -1, 0, 1}
    dy := []int{1, 1, 1, 0, 0, -1, -1, -1}

    minemap := make([]string, f)
    for i := 0; i < f; i++ {
        for j := 0; j < w; j++ {
            if string(maps[i][j]) == "#" {
                minemap[i] += "#"
                continue
            }
            var mine int
            for d := 0; d < 8; d++ {
                posx := i + dx[d]
                posy := j + dy[d]
                if posx < 0 || f <= posx {
                    continue
                }
                if posy < 0 || w <= posy {
                    continue
                }
                if string(maps[posx][posy]) == "#" {
                    mine++
                }
            }
            minemap[i] += strconv.Itoa(mine)
        }
    }
    return minemap
}

テストは入出力サンプルひとつ分。
スライスはreflect.DeepEqual()で比較。

main_test.go
package main

import (
    "reflect"
    "testing"
)

func TestMine(t *testing.T) {
    h, w := 3, 5
    maps := []string{".....", ".#.#.", "....."}
    want := []string{"11211", "1#2#1", "11211"}
    if got := mine(h, w, maps); !reflect.DeepEqual(got, want) {
        t.Fatalf("want is %v, got is %v", want, got)
    }
}

グリッドに関する処理：ABC 096 C(300点)

スライスを座標風に見立てて考えている( slice[y方向][x方向] )。
グリッド問題でよくありそうな「上下左右のマスを調べる」は、相対座標の差のパターンを構造体で用意している。

// 「x軸に対して+1、y軸は変化なし」的な相対座標を保存するペア値の構造体。
type pair struct {
    i, j int
}
// 上下左右4パターンを探索する例
for _, p := range []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {}
main.go
package main

import "fmt"

type pair struct {
    i, j int
}

func main() {
    var h, w int
    fmt.Scan(&h, &w)
    input := make([]string, h)
    for i := range input {
        fmt.Scan(&input[i])
    }
    fmt.Println(grid(h, w, input))
}

func grid(h, w int, input []string) string {
    for i := range input {
        for j := range input[i] {
            if input[i][j] == '.' {
                continue
            }
            var count int
            for _, p := range []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
                si := i + p.i
                sj := j + p.j
                if si >= 0 &&
                    sj >= 0 &&
                    si < h &&
                    sj < w &&
                    input[si][sj] == '#' {
                    count++
                }
            }
            if count == 0 {
                return "No"
            }
        }
    }
    return "Yes"
}
main_test.go
package main

import "testing"

func TestGrid(t *testing.T) {
    h, w := 3, 11
    input := []string{"...#####...", ".##.....###", "##.##.##..#"}
    if expected, actual := "Yes", grid(h, w, input); expected != actual {
        t.Errorf("wont %s but got %s", expected, actual)
    }
}

区間の重なりを求める処理：ABC 070 B(200点)

重なり区間は、2つの始端の max() から、2つの終端の min() の範囲。
一切重なってない場合の 0 を忘れずに。

main.go
package main

import (
    "fmt"
)

func main() {
    in := make([]int, 4)
    for i := range in {
        fmt.Scan(&in[i])
    }
    fmt.Println(robo(in))
}

func robo(in []int) int {
    return max(0, min(in[1], in[3])-max(in[0], in[2]))
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

テーブル駆動テスト文化は競プロ問題の見本値を羅列するのに便利。

main_test.go
package main

import "testing"

func TestRobo(t *testing.T) {
    cases := map[string]struct {
        in   []int
        want int
    }{
        "1": {in: []int{0, 75, 25, 100}, want: 50},
        "2": {in: []int{0, 33, 66, 99}, want: 0},
        "3": {in: []int{10, 90, 20, 80}, want: 60},
    }

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

答えを 1000000007 (など) で割った余りで求める：ABC 055 B(200点)

main.go
package main

import (
    "fmt"
    "math"
)

func main() {
    var n int
    fmt.Scan(&n)
    fmt.Println(train(n))
}

func train(n int) int {
    w, p := int(math.Pow10(9.0))+7, 1
    for i := 1; i <= n; i++ {
        p = p * i % w
    }
    return p
}
main_test.go
package main

import "testing"

func TestTrain(t *testing.T) {
    cases := map[string]struct {
        n, want int
    }{
        "1": {n: 3, want: 6},
        "2": {n: 10, want: 3628800},
        "3": {n: 100000, want: 457992974},
    }

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

数学的問題：ABC 046 B(200点)

main.go
package main

import (
    "fmt"
    "math"
)

func main() {
    var n, k int
    fmt.Scan(&n, &k)
    fmt.Println(paintBall(n, k))
}

func paintBall(n, k int) int {
    pat := float64(k) * math.Pow(float64(k-1), float64(n-1))
    return int(pat)
}
main_test.go
package main

import "testing"

func TestPaintBall(t *testing.T) {
    cases := map[string]struct {
        n, k int
        want int
    }{
        "1": {n: 2, k: 2, want: 2},
        "2": {n: 1, k: 10, want: 10},
        "3": {n: 10, k: 8, want: 322828856},
    }

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

数学的問題：ABC 048 B(200点)

main.go
package main

import "fmt"

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

func between(a, b, x int) int {
    if a <= 0 {
        return b/x + 1
    }
    return b/x - (a-1)/x
}
main_test.go
package main

import "testing"

func TestBetween(t *testing.T) {
    cases := map[string]struct {
        a, b, x, want int
    }{
        "1": {a: 4, b: 8, x: 2, want: 3},
        "2": {a: 0, b: 5, x: 1, want: 6},
        "3": {a: 9, b: 9, x: 2, want: 0},
        "4": {a: 1, b: 1000000000000000000, x: 3, want: 333333333333333333},
    }

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

状態がループするシミュレーション処理：ABC 060 B(200点)

main.go
package main

import "fmt"

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

func choose(a, b, c int) string {
    for i := 1; i <= 100; i++ {
        if i*a%b == c {
            return "YES"
        }
    }
    return "NO"
}
main_test.go
package main

import "testing"

func TestChoose(t *testing.T) {
    cases := map[string]struct {
        a, b, c int
        want    string
    }{
        "1": {a: 7, b: 5, c: 1, want: "YES"},
        "2": {a: 2, b: 2, c: 1, want: "NO"},
        "3": {a: 1, b: 100, c: 97, want: "YES"},
        "4": {a: 40, b: 98, c: 58, want: "YES"},
        "5": {a: 77, b: 42, c: 36, want: "NO"},
    }

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

状態がループするシミュレーション処理：ABC 065 B(200点)

main.go
package main

import (
    "fmt"
)

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

func train(n int, a []int) int {
    p := 1
    for c := range a {
        p = a[p-1]
        if p == 2 {
            return c + 1
        }
    }
    return -1
}
main_test.go
package main

import "testing"

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

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

累積和：ABC 087 C(300点)

グリッドの問題と同じく、スライスを座標風に使う。

main.go
package main

import (
    "fmt"
)

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

func seek(n int, a, b []int) int {
    var s int
    for i := 0; i < n; i++ {
        var sum int
        for _, v := range a[:i+1] {
            sum += v
        }
        for _, v := range b[i:] {
            sum += v
        }
        if sum > s {
            s = sum
        }
    }
    return s
}
main_test.go
package main

import "testing"

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

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

累積和：ABC 098 C(300点)

main.go
package main

import (
    "fmt"
    "math"
)

func main() {
    var n int
    fmt.Scan(&n)
    var s string
    fmt.Scan(&s)
    fmt.Println(face(n, s))
}

func face(n int, s string) int {
    min := int(3 * math.Pow10(5))
    var ce, cw int
    for _, v := range s {
        if v == 'E' {
            ce++
        }
    }
    for _, v := range s {
        if v == 'E' {
            ce--
        }
        if ce+cw < min {
            min = ce + cw
        }
        if v == 'W' {
            cw++
        }
    }
    return min
}
main_test.go
package main

import "testing"

func TestFace(t *testing.T) {
    cases := map[string]struct {
        n    int
        s    string
        want int
    }{
        "1": {n: 5, s: "WEEWW", want: 1},
        "2": {n: 12, s: "WEWEWEEEWWWE", want: 4},
        "3": {n: 8, s: "WWWWWEEE", want: 3},
    }

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

bit 全探索：ABC 079 C(300点)

探索パターンが少ないので手書きで総当たりでも解ける。

main.go
package main

import (
    "fmt"
)

func main() {
    var in string
    fmt.Scan(&in)
    fmt.Println(op(in))
}

func op(in string) string {
    nums := [4]int{int(in[0] - '0'), int(in[1] - '0'), int(in[2] - '0'), int(in[3] - '0')}
    for i := 0; i < (1 << 3); i++ {
        ans := nums[0]
        ops := []string{}
        for j := uint8(0); j < 3; j++ {
            if i&(1<<j) != 0 {
                ans += nums[j+1]
                ops = append(ops, "+")
            } else {
                ans -= nums[j+1]
                ops = append(ops, "-")
            }
        }
        if ans == 7 {
            return fmt.Sprintf("%d%s%d%s%d%s%d=7", nums[0], ops[0], nums[1], ops[1], nums[2], ops[2], nums[3])
        }
    }
    return ""
}
main_test.go
package main

import "testing"

func TestOp(t *testing.T) {
    cases := map[string]struct {
        in   string
        want string
    }{
        "1": {in: "1222", want: "1+2+2+2=7"},
        "2": {in: "0290", want: "0-2+9+0=7"},
        "3": {in: "3242", want: "3+2+4-2=7"},
    }

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

感想

出題類型には関係ないが、ABC 079 C の様に「+0でも-0でも正解」の様に答えが複数パターンあると現在のテーブルテストでは表現できないのが課題。

1
0
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
1
0