4,564,046点 の 76位 でした。
サンプル入力のビジュアライズ結果はこんな感じ。
解法と考察過程について書いていこうと思います。
最終解法
- いかに途中で詰まらせずにフィールドを全体的に周るか
- スタート地点が不定であることの実装負荷をいかに減らすか
の対処を重視して、下図のような、全体を10x10のブロックで25分割し*1、内24ブロックを使った巡回路*2を作り、そこに沿って経路を構築していく方針を取りました。 現在地点のブロック内のみの移動を許し*3、巡回路上の次のブロックに到達したらゴールって感じです。
各ブロック内の移動経路は、獲得スコアを評価関数とする幅1,200のビームサーチでもとめました。
また、細かい部分の工夫で、
- 巡回路に含まれていない右下の1ブロックへ、その１つ上か左のブロックを通過するときに侵入を許す
- 既に通過済みのブロックへの侵入を許す
とかもしました。
提出コードはこちらです Submission #22074771 - AtCoder Heuristic Contest 002
考察過程
0:00 問題文を読む
問題文を読んでみてなんとなく、
- 割とありそうな問題っぽい気もするものの、類似事例がパッと思い浮かばないなあ
- 良い感じの貪欲が思い浮かばないなあ
みたいなことを考えてた気がします。
(雑に書ける)貪欲が思い浮かばない時は、焼きなまし系かビームサーチのどちらかに持ち込めないかをとりあえず考えてみることにしてるので、ひとまずそれをしました。 焼きなましは全然方針浮かばずで、ビームサーチはまあできるだろうけど評価関数どうすべきだろ、って感じの考察状況でした。
0:30 とりあえず提出してみる
空文字列を出力するコードを提出。正の点数を得る。
1:20 ランダムウォークを試す
入出力や問題特化の基本操作を用意する目的も兼ねて、ランダムウォークするコードを実装した。 14万点で下位30%くらいだった記憶。既に時間の4分の1が経過してるのにまだこの状況かと焦っていた*4。
ビジュアライザをこのタイミングで初めて試した。コンテスト時間あんま無いことを鑑みて、さっと使えそうなウェブ版がだけを触ってローカル版はひとまず放置することにした*5。 ビジュアライズ結果を見ると、まあやはりというかスタートしてすぐのところで進行経路が塞がって動けなくなっていた。
1:50 雑なビームサーチを試す
あんまり方針が浮かばないので、とりあえず雑なビームサーチだと何が起きるのかを試しに見ることにした。獲得スコアを評価関数とするビームサーチ解を提出。 223万点。トップ層の半分弱くらいのスコアで、順位が半分よりちょい上とかだった記憶。
ビジュアライザを見てみると、上３分の1くらいのエリアしか移動できずに行き詰まって終了していることが分かった。 ここをどうにかしないと話が始まらないなってのと、一方で、この埋まり具合でこのスコアなら、雑にでも全面埋められればそれだけで結構良い順位行けそうだなという気持ちになった。
3:00 盤面を100分割して巡回路を作る方針を考察し、試す
上のビームサーチ結果の考察を受けて、どうやったら途中で詰まらずに盤面を全体的に歩けるかを考えていた。
ビームサーチの延長でやるなら、評価関数にその要素を織り込むになると思うが、何を基準にすべきだろうか？周辺の広さみたいなものを加味する評価関数とか書けると良さそうか？でもあんまり実装イメージ湧かないな。 ルールベースでやるのはどうだろうか？始点が固定じゃないのつらいな。 巡回路作れば、始点がどこでも同様に扱えるので楽そう。盤面を大まかに区切って、区切られたブロック単位では巡回路を固定で用意することにしよう。
って感じの思考を経て、盤面を5x5の100ブロックに分けて、ブロック粒度での巡回路を用意する方針を試すことに決めた。 ブロック内の経路選択は、１つ前のコードを使い回すのが楽そうだったので、先ほどのビームサーチをブロック内の移動のみを許し次のブロックに到達したらゴールとする形に書き換えて使った。
しかし提出してみたところ、68万点と大きくスコアが落ちてしまった。 ビジュアライザを見ると、ブロックが小さすぎるために移動経路を確保しきれず詰まってしまっているように見えた。
3:10 盤面を25分割して巡回路を作る方針を試す
前の結果を受けて、前より大きい10x10のブロックで盤面を25分割する方針を試すことにした。 ブロック数が奇数x奇数になるので、巡回路で全ブロック使えなくなっちゃう*6の嫌だなあとかを思ったりはしたけど、まあしょうがない。
当たり方針かが分からなかったので、とりあえず手を抜いた実装で提出してみることにした。 具体的には、右端の下から３つのブロックは巡回路から外して、それ以外の計22ブロックのみで巡回路を構成する実装とした*7。 383万点で200位くらいまで上がった記憶。
スコア・順位的に方針悪くないなって気持ちになったのと、残り時間がもうあんまり無かったので、大筋の方針はこれで決めにして細部を詰めていくことにした。
3:40 明らかな問題点を潰す
最後に訪れるブロックの移動経路が出力に含まれない実装になっていたのを修正。 390万点。
巡回路が22ブロックしか使ってなかったのを24ブロックに増やす。一番右下のブロックだけが使われていない形に。 430万点。この時点で100位くらいだった記憶。喜ぶ。
一番右下のブロックを、隣接するブロックを周っている時に侵入できるようにする。 456万点(最終スコア)。70位くらいになる。
4:00 短時間でできる改善を試みる
- ビーム幅の調整
- 通過済みのブロックへの侵入を許す
を試したりしたけど、スコア伸びずでそのままコンテスト終了した。
所感
76位の黄色パフォが取れた。大満足。
解法は割と普通のことしかしてないなあって感覚ではあったりします。やっぱり４時間は短いので、大枠の方針を外さず、早くバグらせずに実装しきることの比重が大きいのかなって気持ちになりました。ハーフマラソンはやっぱり１週間マラソンとかとは別ゲーに感じますね。 今回は割と、小さく試してその結果を元に方針決めて対処って流れが上手く回せてたかなって実感があって、この辺が結果にいい感じに繋がってくれたかなとかを思ってたりします。
あとは、コンテスト後にTLを眺めてたらちょこちょこ焼きなまし解を見かけて気になってたりします*8。近傍どうするんだろう。
