@drken さんの『AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～』は AtCoder の入門記事としてとても人気があります。
当該記事の最後には、各言語によるACコードまとめへのリンクがありますが、Go 言語版 は 2019/01 現在でリンク切れになってしまっています。 (執筆者さんのアカウント自体がなくなっているようです)
私は競プロに Go 言語で参加することが多いので、今回Goで解いたACコードでまとめを新しく作りました。本記事に乗せてあるコードおよび解説の特徴は次のとおりです：
- 解き方は原則として @drken さんの解説に合わせてあります。もともと C++ と Go は文法が比較的似ている言語なので、そこまで大きな違いはありません。
- 少し私好みの書き方を採用している場合もあります。
- Go 特有の注意点などがある場合は追記しています。
- 別解がある場合はコードと解説をあわせて載せています。
- Goのシンタックスそのものについては解説を省略しています。
以下、AtCoder Beginners Selection のネタバレになりますので、まだABSを解いていない人はご注意ください。
第0問: PracticeA - Welcome to AtCoder
package main
import "fmt"
func main() {
var a, b, c int
var s string
fmt.Scan(&a)
fmt.Scan(&b, &c)
fmt.Scan(&s)
fmt.Println(a+b+c, s)
}
入出力をちゃんとできれば、あとは a+b+c と s を出力すればOKです。Goでの入力は var で変数を宣言したあと、 fmt.Scan() によって読み込む方法がシンプルで最初は使いやすいと思います。
上記コードでは fmt.Scan() を入力の1行ごとに1回ずつ呼び出していますが、 fmt.Scan(&a, &b, &c, &s) のように1回で複数行の入力をScanすることもできます。
出力はこの問題を含め、 ABS に登場する問題であれば fmt.Println() に渡せばOKです。 フォーマットしたい場合には fmt.Printf() を使えば良いでしょう。
なお、入出力する数値の個数が $3 \times 10^5$ あたりになってくると、 バッファリングしない入出力である fmt.Scan() では遅すぎてTLEしてしまう場合があります。将来的にはバッファリングする入出力を使う方法を覚えると良いでしょう。バッファリングする入出力については 『Goで競技プログラミングするときのテクニック』 をご覧ください。
第1問: ABC 086 A - Product
package main
import "fmt"
func main() {
var a, b int
fmt.Scan(&a, &b)
if a*b%2 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}
}
if文をちゃんと使えて、問題文に書いてあるとおりの判定「 a と b の積が偶数か奇数か判定」を実装できればOKです。
Odd (奇数)と Even (偶数)を取り違えたり、綴りを間違えたりしないよう、注意が必要です。 AtCoder では大文字小文字は区別されることが多いです(Odd と出力すべきところで ODD と出力するとWAになる)。綴りについて正確に書き写す自信がない場合は問題文からコピペをするのが一番確実です。
第2問: ABC081A - Placing Marbles
package main
import "fmt"
func main() {
var s string
fmt.Scan(&s)
var ans int
for _, v := range s {
if v == '1' {
ans++
}
}
fmt.Println(ans)
}
3文字からなる入力文字列における 1 の数をカウントすればOKです。
このコードでは、読み取った文字列の長さが制約通り3文字かどうかをチェックしていません。
実用的なプログラムではこういった書き方は普通あり得ないことですが、競技プログラミングのコードでは入力データを信頼して構いません。
第3問: ABC081B - Shift only
package main
import "fmt"
func main() {
var N int
fmt.Scan(&N)
A := make([]int, N)
for i := range A {
fmt.Scan(&A[i])
}
ans := 0
for {
ok := true
for _, v := range A {
if v%2 != 0 {
ok = false
}
}
if !ok {
break
}
for i := range A {
A[i] /= 2
}
ans++
}
fmt.Println(ans)
}
このあたりから少し考えさせる問題になってきますが、制約が小さいので、問題文に書いてあることをそのまま実装するシミュレーションで問題なくACできます。
別解1
問題文に書かれていることを考察すると、別解として次のようなコードを書くこともできます。
package main
import "fmt"
func min(a, b int) int {
if a < b {
return a
}
return b
}
func count(n int) int {
var c int
for n%2 == 0 {
c++
n /= 2
}
return c
}
func main() {
var N int
fmt.Scan(&N)
A := make([]int, N)
for i := range A {
fmt.Scan(&A[i])
}
ans := 40
for _, v := range A {
ans = min(ans, count(v))
}
fmt.Println(ans)
}
この問題は「すべての $A_i$ が偶数であれば、それらを2で割る」という操作を最大で何回できるかを調べよ、という問題です。はじめて操作できなくなるのは、 $A_i$ のうちどれか一つでも奇数になったときです。そのため、$A_i$ を一斉に2で割るという操作を繰り返さなくても、 $A_i$ それぞれについて独立に $2$ で何回割り切れるかを調べ、その最小値を答える、という方法でもACできます。この方針をコード化すると上記の別解になります。
最小値を保持する変数は入力の制約上ありえない数（ここでは40）で初期化しておきます。
別解2
次のようにビット演算を用いた別解もあります。
package main
import "fmt"
func main() {
var N int
fmt.Scan(&N)
A := make([]int, N)
for i := range A {
fmt.Scan(&A[i])
}
var a uint
for i := range A {
a |= uint(A[i])
}
fmt.Println(trailingZeros(a))
}
func trailingZeros(x uint) int {
var count int
for i := uint(0); i < 40; i++ {
if (x>>i)&1 == 0 {
count++
} else {
break
}
}
return count
}
やっていることは
- まず、すべての $A_i$ をビットOR演算でマージする
- マージ結果の数の最下位桁から $0$ がいくつ連続しているか数える。
です。この解法では「何回2で割れるかを調べる」という操作を1回にまとめることができます。
難しい問題では、こういう発想が必要になる場合もあるので、頭の片隅に置いておくと良いと思います。
なお、Go 1.9 以降では下位の連続した $0$ を math/bits.TrailingZeros(uint) で効率よくカウントできますが、 AtCoder の Go のバージョンでは対応しておらずCE (コンパイルエラー)になるため、ここでは愚直に数えています。
第4問: ABC087B - Coins
package main
import "fmt"
func main() {
var A, B, C, X int
fmt.Scan(&A, &B, &C, &X)
var ans int
for a := 0; a <= A; a++ {
for b := 0; b <= B; b++ {
for c := 0; c <= C; c++ {
if 500*a+100*b+50*c == X {
ans++
}
}
}
}
fmt.Println(ans)
}
簡単な全探索を書ければOKです。
枚数を表す変数が3つしかなく、それぞれの最大値も小さいので、500円、100円、50円をそれぞれの枚数でループを回した3重ループを使うのが簡単だと思います。
この3重ループにより構成可能な合計金額をすべて算出し、それが $X$ と等しくなる場合をカウントします。
この問題で3重ループを書くときのポイントとしては、つぎの2つあたりでしょうか：
- ループ変数を $0$ から始めること。これは「ある硬貨を一枚も使わない場合」を試行するために必要です。
- for文の条件式にてループ変数を
<=で最大枚数である $A, B, C$ と比較すること。これは「ある硬貨を最大枚数使った場合」を試行するために必要です。
第5問: ABC083B - Some Sums
package main
import "fmt"
func sum(n int) int {
var res int
for 0 < n {
res += n % 10
n /= 10
}
return res
}
func main() {
var N, A, B int
fmt.Scan(&N, &A, &B)
var ans int
for i := 1; i <= N; i++ {
s := sum(i)
if A <= s && s <= B {
ans += i
}
}
fmt.Println(ans)
}
この問題も $1$ から $N$ までのそれぞれの数が条件に合致するかどうかを全探索するのが楽だと思います。
第6問: ABC088B - Card Game for Two
package main
import (
"fmt"
"sort"
)
func main() {
var N int
fmt.Scan(&N)
a := make([]int, N)
for i := range a {
fmt.Scan(&a[i])
}
sort.Sort(sort.Reverse(sort.IntSlice(a)))
var score [2]int
d := 0
for _, v := range a {
score[d] += v
d = 1 - d
}
fmt.Println(score[0] - score[1])
}
この問題に示されたゲームのルールにおいて「最適な戦略」は明らかに「a に残ったカードの中で最大の値のカードを取る」ことです。したがって、a を大きい順にソートしたうえで交互にカードを前から順に取得していけば、双方のプレイヤーが最適な戦略に基づく行動を取った場合のゲームの進行をシミュレートできます。
上記のコードではプレイヤーのスコアを [2]int 型の変数に格納しています。 d = 1 - d という書き方は、変数の値を 0 と 1 でフリップさせるときの慣用表現です。
第7問: ABC085B - Kagami Mochi
package main
import "fmt"
func main() {
var N int
fmt.Scan(&N)
d := make([]int, N)
for i := range d {
fmt.Scan(&d[i])
}
mp := make(map[int]bool)
for _, v := range d {
mp[v] = true
}
fmt.Println(len(mp))
}
C++における set<T> が必要な場合、 上記のように map[T]bool で代用可能です。ただし、 Go の map は C++ でいう unordered_map 相当なので、最小（または最大）キーの値を取り出したり、キーの小さい順（または大きい順）に走査出来ないことに注意が必要です。また、 range でキー全体の走査は可能ですが、キーはランダムに登場することを意識しておかなければなりません。
第8問: ABC085C - Otoshidama
package main
import "fmt"
func main() {
var N, Y int
fmt.Scan(&N, &Y)
for i := 0; i <= N; i++ {
for j := 0; j <= N; j++ {
k := N - i - j
if k < 0 {
continue
}
if 10000*i+5000*j+1000*k == Y {
fmt.Println(i, j, k)
return
}
}
}
fmt.Println(-1, -1, -1)
}
3種類のお札の枚数を合計して $N$ 枚になるような組み合わせを全探索しますが、 3重ループではTLEしてしまいます。
ここでは「枚数の合計が必ず $N$ 枚である」ことを利用し、2重ループで2種類のお札の枚数を決めたら、3種類目の枚数を「$N$ - 1種類目の枚数 - 2種類目の枚数」を計算することで確定させます。
3種類目の枚数が負の数になってしまうことはあり得ないので、もしそうなってしまったら continue するところがポイントです。このチェックは内側のループの条件式を i+j <= N とすれば省略可能です。
第9問: ABC049C - 白昼夢 / Daydream
package main
import (
"bytes"
"fmt"
)
func main() {
var S string
fmt.Scan(&S)
sb := []byte(S)
rev(sb)
w := [][]byte{
[]byte("dream"),
[]byte("dreamer"),
[]byte("erase"),
[]byte("eraser"),
}
for i := range w {
rev(w[i])
}
i := 0
for i < len(sb) {
var ok bool
for _, t := range w {
if bytes.HasPrefix(sb[i:], t) {
ok = true
i += len(t)
break
}
}
if !ok {
fmt.Println("NO")
return
}
}
fmt.Println("YES")
}
func rev(b []byte) {
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
このあたりの問題から一筋縄では行かなくなってきます。
頭から見ていくと、例えば dreamer... とあったときに dream + (erase または eraser) をマッチさせるべきなのか、 dreamer をマッチさせるべきなのか、難しい判断が必要になります。しかし、後ろから見ていけばそのような判断が不要になります。また、「後ろから見ていく」は「反転させた文字列を前から見ていく」と言い換えることができます。「反転」操作は簡単に実装できるので、後者の戦略をとると楽に実装できます。
ここでは string を []byte にキャストしてから扱っています（好みの問題ですが、個人的に string[i] が rune になるところが競技プログラミングにおいては少し思考の妨げになることがあるので、何か string として扱いたい理由がない限り []byte に統一することにしています）。
Go には string やスライスを反転する関数は用意されていないようなので、自分で rev という関数を書いて使っています。 byte に限らずスライスを反転することは良くあるので、書き方を覚えてしまうのが良いと思います(少し改変すれば回文判定などに利用できます)。スライス b を反転するには i を先頭から後端方向へ、j を後端から先頭方向へ動かしながら、 b[i] と b[j] を交換します。継続条件は i < j としておけば良いです。 b の長さが奇数の場合でも偶数の場合でも、$0$ や $1$ の場合でも正しく動作します。
第10問: ABC086C - Traveling
package main
import "fmt"
func main() {
var N int
fmt.Scan(&N)
t := make([]int, N+1)
x := make([]int, N+1)
y := make([]int, N+1)
for i := 1; i <= N; i++ {
fmt.Scan(&t[i], &x[i], &y[i])
}
for i := 0; i < N; i++ {
dt := abs(t[i] - t[i+1])
dx := abs(x[i] - x[i+1])
dy := abs(y[i] - y[i+1])
if !check(dt, dx+dy) {
fmt.Println("No")
return
}
}
fmt.Println("Yes")
}
func check(dt, dist int) bool {
return dist <= dt && dist%2 == dt%2
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
登場する変数や概念が増えてきて、問題文を理解するのも難しいと思いますが、サンプルを見ながら落ち着いて整理していけば、次のポイントに気づくことができます。$dt = t_{i+1} - t_i, dx = |x_{i+1}-x_i|, dy = |y_{i+1}-y_i|$ とすると、
- $dx + dy \le dt $ でなければ、時間が足りず、$(x_{i+1}, y_{i+1})$ にたどり着けない。
- ある点 $(p, q)$ に到着したあとは $(p, q) → (p, q+1) → (p, q) → (p, q+1) → \dots$のような移動を繰り返して時間をつぶすことも可能なので、時間が余る分には問題ない。
- ただし、 $(dx + dy) % 2 = dt % 2$ でなければ、どんなに時間が余っていてもちょうど $t_{i+1}$ のタイミングで目的地 $(x_{i+1}, y_{i+1})$ 上に居ることができない。
- 言い換えると、 時刻 $t_{i+1} - 1$ の時点で $(x_{i+1}, y_{i+1})$ 上に居ることはできるが、 時刻 $t_{i+1}$ の時点で $(x_{i+1}, y_{i+1})$ のひとつ隣に移動せざるを得ない。
上記のコードでは、このポイントに基づいて時間 $dt$ 経過後に距離 $dist$ 離れた点にとどまることができるかを check(dt, dist int) bool 関数として実装しています。
その他の実装上のポイントとしては、t, x, y のスライスを要素数 N ではなく N+1 確保し、スタート地点を スライス t[0], x[0], y[0] に含めているところです。$t = 0, x = 0, y = 0$ なのでゼロ値をそのまま利用し、明示的に初期化はしていません。これによってスタート時の処理を特別扱いすることなく、実装を簡素化できます。入力の読み込みと走査でのループの初期化や継続条件の違いに注意が必要です。
なお、 abs 関数は math.Abs も利用可能ですが、そちらは float64 型を必要とするため、 int で再実装しています。もちろんこの問題では math.Abs をキャストと一緒に使用しても構いません。
まとめ
AtCoder に登録したら解くべき精選過去問 10 問(+1問) 通称 ABS を Go で解いてみました。
誤りなどありましたらコメントでコメントをお願いします。