AHC002に参加しました。
問題はWalking on Tilesで、最長路問題でした。
順位は参加2685人、提出1076人のうち1018位でした。
空文字を出力しただけです…。
問題
得点付きタイルの上を移動する。
ただし1x2や2x1のタイルもあって、その両方を移動することはできない。
移動済タイルを複数回移動することもできない。
考察
最長路問題はNP困難らしい。
ビームサーチ → 得点と移動可能タイルを両方評価するの大変そうだな。どちらかというとDFS系の方が強そう？
MCTS → メモリ制限がきつそう。
延長ルートを探す焼き鈍し → これはあり。
10x10の区画を25個に分ける → これもあり。区間内は愚直DFS？時間大丈夫かな…。開始位置によっては1つの区画を利用できない。かと言って区画を16個にしてしまうと時間が間に合わない。区画36個は…なんかロス多そう。
方針
10x10の25区画に分けるのをやって、区間を跨ぐ改善は追加で焼き鈍しかな。
結果
上手く行くケースは下のように上手く行く。
だけど別の区画に入った瞬間に次の移動が不可能になることがあり、25区間完走はあまり出来ない。区画を移る際に、最後の移動位置で分けて複数持っておけば改善しそうではある。*1あとは完全に詰まった場合は区画を無視して貪欲するとか。
その辺はまだやりようはあったのだけど、実装時間が足りないのとWAが取れずに結局空文字を出力するものしか提出できず。
感想
かなりもやっと。
AHC001もだけど、低確率で発生するバグに殺されすぎですね…。
入力ファイルは改行コードが違ってそのままでは動かない、テスター兼ビジュアライザはバッチ実行できない、バグの再現率は低いのでWAが出るケースを大量に1個1個探さないといけない、とデバッグが苦痛すぎるので、これを改善できない限りはAHC（特にハーフマラソン）は手を付けないのもありかなぁ…。自前テスター作成は流石にハーフマラソンで作ると時間が大変なことになりそうだし。
終了後にまたバグが出るケースを探したけど全然見つからないので苦痛になってきて、これは一旦放置することにしました。良い感じに効率化できる方法が出てきたらまた考え直すことにします。
一応の反省点としては、どうせ焼き鈍しを入れる前提なら別ロジックまで重実装するのは冗長だったというのと、期待点が出るまでがあまりに長すぎて間に合わなかったので軽実装でバグりにくいシンプルなものから始めるという辺りですかね…。
一旦切り替えて、次のマラソンに臨もうと思います。コドゲに出たいのでMM126
はお休みかなぁ…。
*1:ただ、それをやる時間は愚直DFSでは無さそう。詰む場所をチェックしてそこをゴールから外すくらいが現実的かな。
