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

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

[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E3%81%93%E3%81%93%E3%81%BE%E3%81%A7%E8%A7%A3%E3%81%84%E3%81%9F%E3%82%89)

## グリッドに関する処理：[ABC 075 B](https://atcoder.jp/contests/abc075/tasks/abc075_b)(200点)
↓の様に入力されるグリッドを、スライスのインデックスでとらえる。

```
.....
.#.#.
.....
```

```go: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()`で比較。

```go: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](https://atcoder.jp/contests/abc096/tasks/abc096_c)(300点)

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

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

```go: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"
}
```
```go: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](https://atcoder.jp/contests/abc070/tasks/abc070_b)(200点)

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

```go: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
}
```
テーブル駆動テスト文化は競プロ問題の見本値を羅列するのに便利。

```go: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](https://atcoder.jp/contests/abc055/tasks/abc055_b)(200点)

```go: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
}
```
```go: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](https://atcoder.jp/contests/abc046/tasks/abc046_b)(200点)

```go: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)
}
```
```go: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](https://atcoder.jp/contests/abc048/tasks/abc048_b)(200点)

```go: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
}
```
```go: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](https://atcoder.jp/contests/abc060/tasks/abc060_b)(200点)

```go: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"
}
```
```go: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](https://atcoder.jp/contests/abc065/tasks/abc065_b)(200点)

```go: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
}
```

```go: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](https://atcoder.jp/contests/abc087/tasks/arc090_a)(300点)
グリッドの問題と同じく、スライスを座標風に使う。

```go: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
}
```

```go: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](https://atcoder.jp/contests/abc098/tasks/arc098_a)(300点)

```go: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
}
```

```go: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](https://atcoder.jp/contests/abc079/tasks/abc079_c)(300点)
探索パターンが少ないので手書きで総当たりでも解ける。

```go: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 ""
}
```

```go: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](https://atcoder.jp/contests/abc079/tasks/abc079_c) の様に「+0でも-0でも正解」の様に答えが複数パターンあると現在のテーブルテストでは表現できないのが課題。