競プロ参戦記 第9回「コイン大移動」 ABC 109
毎週恒例 AtCoder の競技プログラミング大会に参加したので解説を書きます。今週は ABC-only 回です。
AtCoder Beginner Contest #109
問題:
A - ABC333
問題概要:正の整数 A, B が与えられる。A * B * C が奇数になるような正の整数 C はあるか?
A * B が偶数なら A * B * C は必ず偶数になるので答えはNo。逆に A * B が奇数なら C=1 とすれば A * B * C は奇数、ゆえにYes。
提出:
B - Shiritori
問題概要:英単語のリストが与えられる。これがしりとりになっているか判定せよ。(つまり2つの単語の末尾と先頭が一致して、かつ同じ単語が複数回出現しなければいい。)
同じ単語が複数回出現するかは集合やマップを使って判定できます。単語を読むたび、集合に既に単語があればダメ。なければその単語を加える、というのをやります。今回は単語の個数が少ないので、線型探索でも可。
単語の末尾と先頭が一致するか、というのも似たような方法で判定できます。「直前の単語の末尾」を変数としてもっておき、いま見ている単語の先頭と一致しなければダメ。
提出:
C - Skip
問題概要:数直線上の位置 X から +D か -D の移動を繰り返して、すべての都市を訪問できるか判定せよ。(詳細略。この問題を厳密に書くのは意外と難しい……)
+D の移動は何度でもできるので、座標 X + D, X + 2D, X + 3D, ... には移動できます。-D の移動についても同様で、座標 X - D, X - 2D, X - 3D, ... にも移動できます。
まとめると、整数 n について X + n D と表せる座標に移動できます。逆に、それ以外の座標には訪問できません。
したがって、都市の座標 x_i について x_i = X + n D となる整数 n が存在しなければいけません。つまり |x_i - X| ≡ 0 (mod D) であればいいです。
D はすべての |x_i - X| の約数で最大。最大公約数。
最大公約数を求めるにはユークリッドの互除法を使います。詳細は drken 氏の解説を参照:
提出:
D - Make Them Even
問題概要:縦横 H×W マスの表にコインが入っている。各マスにつき1回、そのマスのコインを上下左右の隣のマスに1枚だけ移動させてよい。最終的にコインの枚数が偶数であるマスの数が最大になるような操作手順を1つ求めよ。
具体的に操作を試していると、どうやらほぼすべてのマスを偶数にできそうです。コインの総数が奇数なら、もちろん少なくとも1つのマスは奇数になります。それ以外をすべて偶数にすることは可能でしょうか? 仮に可能だとして考えます。
なんとなくライツアウトの解法を思い出します。同様に1行目の奇数マスから下にコインを送って2行目のコイン枚数を更新する、2行目の奇数マスからコインを下に送って3行目のコイン枚数を更新する、というのを繰り返していけばいいような気がしました。しかし次のように「偶数マスを経由してコインを送る」必要があるケースがダメ。
H=2 W=3
1 0 0
0 0 1
最後の行でなんとか調整したい。つまり、H=1 の場合はどうでしょうか。
H=1 W=5
1 2 1 2 1
これも同様に、左から1マスずつ見ていって、「奇数なら右に送る」「偶数なら送らない」としていけば最後のマス以外は偶数にできますね。
結局、次のような操作手順でOK。
左上から始めて、右端へ、下へ、左端へ、下へ、と移動を繰り返して表全体に亘るループを書きます。
11 -> 12 -> 13 -> 14
↓
21 <- 22 <- 23 <- 24
↓
31 -> 32 -> 33 -> 34
各マスにつき、直前のマスからコインが送られているなら、その操作を記録します。その送られたコインを加えて、コインの枚数が奇数なら次のマスにコインを流します。
これにより最後のマス以外は必ず偶数枚になります。最後のマスの偶奇はコインの総数の偶奇に一致します。
提出:
おわりに
全完でした。
前の2週間は AtCoder Regular Contest 併設の影響で、異常な難度の D 問題が続きましたが、今回はひさしぶりに“初心者向け”感がありました。
しりとりのように「知ってるけど書いたことはない」ルールを実装するのはわくわくしますね。
この記事が気に入ったらサポートをしてみませんか?