beet's soil

競プロのことなど

ACPC VC 2020/01/15 DIV1

WA WA WA

Splatter Painting

d ≤ 10
(どれだけ塗るか, 頂点番号)のペアを状態に持ってBFSをします 
同じだったらキューに突っ込まないをしないとMLE/TLEします

Ants on a Circle

蟻本の由来になった問題と同じ言い換えをすると、T秒後の全ての蟻の位置がわかる
また、蟻の相対位置に注目すると、ある蟻から一周したときの順番は固定されていることもわかる
したがって、蟻の位置一匹分さえ求まれば、全部復元できる

蟻と蟻がぶつかったとき、その番号をswapすると捉えられる
w=1の蟻とw=2の蟻がぶつかったとき、前述した考察からw=1側の番号が1増えるとも言い換えられる
したがって、w=1の蟻を一匹固定して、その蟻が各蟻と何回ぶつかるかを求めれば、ある蟻の最終的な番号がわかる

実装は結構大変

Piling Up

これ当時27人しか解いてないのかなり直感に反するな
異なる初期状態から同じ軌跡を作れてしまうのが問題
初期状態と軌跡の一対一を作りたくて、これは(一度でも赤ブロックがなくなったことがあるか)を追加で持てば実現できる

感想

適当にサンプルをガチャガチャしてsubmitデバッグするのは、やめようね!