AtCoder Grand Contest 033
ゲーム系が2問出ました
初めてAGC3完できました
A - Darker and Darker (300点)
問題: A - Darker and Darker
白色のマスの、黒いマスからの最短マンハッタン距離を求めればそれがそのマスを塗るための操作の回数になる。
その最短経路は必ず左右を両方含んだり上下を両方に含むことはない。なので、上下左右にスキャンして隣り合うマスに+1しながらテーブルを更新していけば、すべてのマスについて黒くするための操作回数が求まって、その最大値を出力してAC。。
B - LRUD Game (600点)
問題: B - LRUD Game
高橋君が駒を落とすには、A問題と似たように上下左右いずれかの一方向に動くしかないので、それぞれシミュレートしてAC。。
…かと思い込んでいたが、これは嘘解法*1だった。いったん逆方向に移動するのが最適になるケースがありうる！
なので、後ろから考える*2と、後攻青木君が安全地帯を広げて先攻高橋君が安全地帯を狭める、というゲームに言い換えられて、途中で安全地帯が消滅する（＝その手以降はどう頑張っても青木君が駒を盤上に残せない）か最初まで見ていって初期状態の位置が安全地帯に含まれていないときに高橋君が必ず勝てるので 'NO' を出力する。そうでなければ青木君が必ず勝てるので 'YES' を出力する。これで正真正銘AC。。
拙解 (C++14，嘘解法): Submission #5259087 - AtCoder Grand Contest 033
拙解 (C++14，正規解法，コンテスト終了後): Submission #5281136 - AtCoder Grand Contest 033
C - Removing Coins (800点)
問題: C - Removing Coins
これはよく考えると、1枚以上の重なったコインの枚数は区別されず、加えてコインが置いてある頂点全てからなる部分グラフは連結を保つことが分かる（指定した頂点をシンクとしてそこに深さ1つ分吸い込まれるイメージ）。「コインが置いてある頂点全てからなる部分グラフ」を「残り部分グラフ」と言い換えるとすると、高橋君と青木君が行う操作は次のように言い換えられる：
- 残り部分グラフの葉を選ぶ。残り部分グラフの直径は1減る（最遠頂点対の片方の側が吸い込まれる）。
- 残り部分グラフの内部ノードを選ぶ。残り部分グラフの直径は2減る（最遠頂点対の両方の側が吸い込まれる）。
したがって、Grundy数は最初の木の直径の3で割ったあまりが1のとき、またそのときだけ0になる。
木の直径はググるとBFSで求められるとあるので、求めてこれを3で割って1余れば 'Second'、otherwise 'First' を出力してAC。。
D以降
わからんかった
まとめ
初めてAGC-Cが解けて初めての黄パフォでした（やったー）
でもBで嘘解法投げて通っちゃったりCの問題文誤読してて直径が減らない場合もあると思い込んでいたりしたのでそこは反省ですね
atcoder.jp
