ARC219 (Div. 2)

perf 1617 rate 1965 → 1934 (-21) 0:00 A 6:40 B 20:10 D(1回目) 26:00 C 1:23:45 D(2回目)(間に合わず) 2:12:10 E(延長戦)(読んだだけ) 最近爆死ばっかだな・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ C問題 ２回以上グルグルするのが最適になるパターンを考慮しておらずWAで、ランテス書いたら気付いた。33分ロス 対岸へ渡るコストが大きいと潜在意識的に思っていたせい。理詰めの精度の悪さは今後治っていくと信じたい D問題 やっぱdfs以外のゲーム問苦手すぎる dfsでTLEするゲーム問の解き方について、思いつく限り列挙してみると ・最終状態からの理詰め・実験 ・Grundy数 ・まねっこ戦略 ・天啓 ・（超現実数） まず理詰めが遅い（視点の切り替えに混乱する）のと、まねっこ戦略系はまじで気付けないのがつらい まねっこ戦略は要するに「相手（負けてる）の動きを無効化する、対称的な動きをすること」。競プロ的な嬉しさは、既に分かっている負けの盤面から、帰納的に色んな負けの盤面を確定させることができること 「理詰め・実験」中に常に頭に入れておいた方がいいかも (0,0)と(0,1)と(1,0)のところのみが残っている場合に(A[0][1]-A[1][0])%(K+1)の値が重要なのは最初の方に気付いていたが、(1,1)追加で考察したら頭が壊れた。(0,1)→(0,0)の動きがここでも可能なのを忘れており、長時間まねっこに至らなかった Grundy数表を書き出そうとしたら(0,1)→(0,0)の動きを思い出せて、(1,1)関係ねえじゃんになり、帰納的に偶数マス全部関係ないのが分かった。ギリギリコンテスト終了前のこと しかし、「関係ない場所を完全に忘れる」ということができなくて（偶数マスに動かした石のその後について考えてしまった）、ただの石取りゲームになるのに気付くのが遅れACを逃した