とりあえず愚直ビームサーチを書いてみると盤面全体を移動できないうちに行き詰まってしまうことがわかる。
こういうのをどうするかという時に手札があまりなくて困るが、安直な対処として、全体を10x10マスの25個のブロックに区切ってブロックを頂点とするグラフでハミルトンパスをひとつ与えて（偶奇によってはハミルトンパスがなくて24ブロックしか渡れないが）それに沿うような経路を探索するというのはありそう。ベスト方針とは思えないので少しためらっていろいろ考えたが、他に大した案を思いつかないので実装した。
現在のブロックを$B_1$、次のブロックを$B_2$とするとき、$B_1$内では幅6000のビームサーチをする。移動先は$B_1$内のいずれかのマスか、$B_2$のマスで$B_1$に隣接しているもの（高々10個）に限る。後者は最高点の経路だけ保持する。$B_1$のビームサーチが終わったら$B_2$のマスで$B_1$に隣接しているものを始点に$B_2$のビームサーチを始める。これで$5.2 \times 10^6$点程度だった。もう少し考えると、$B_1$と$B_2$にまたがるタイルを取る/取らないで$B_2$における探索に影響があるので、それらの違いも考慮して経路を保持する（高々$10 \times 2^{10}$状態だが、平均的にはそれよりだいぶ小さい。) これで$5.3 \times 10^6$台に上がった。ビームサーチの幅を増やすと点はある程度上がるようだったので、最後の数十分は高速化をして幅8000のビームサーチが間に合うようにしたが、更新できなかった。
- 結果を見ると、2個程度のテストケースで25個のブロックを渡りきる前に行き詰まって終了しているようだ。そうなる可能性は認識していたけれど、seed=0から99まででは大丈夫だったので軽視していた。応急処置としては、時間があまりすぎていたらもう一回別のハミルトンパスで探索する等は思いつくが……
- コンテストが終わったあとで調べていたが、そもそもどう動いても隣接ブロックに移れないか、移れる経路が極端に限られるような配置がたまにあるようだ。
- 最初の考察で、タイル毎に取るほうを決め打つと普通の最長経路問題になるなと思ってしばらく考えていたが、それを利用する方針は思いつかず。
- 経路を一部破壊してからつなぎなおす方針で上位に入っている人がけっこういるようだ。これも考えたけれど、4時間で詰められると思えなかったので捨ててしまった。
