参加しながら考えたこと試したことの源泉かけ流し。
問題文はこちら
1 日目
問題を読んでサンプルを走らせる。
サンプルは全ケースで正の点が得られる貪欲解だったので、これをそのまま出す人は多いはず。順位表からトップ層の得点の目安を立てるのに使えそう。
二次元グリッド上での同じ道を通らない一筆書きと言えば、やはりパッと思いつくのは「フカシギの数え方」。
とりあえずググってみる。
うーん、よく考えたら今回やりたいのは数え上げじゃなくて列挙したパスを全通り試して一番スコア高いやつを選ぶとかだから、ちょっと違うのかもしれない。
普通に DFS でいっか。
もちろん大きい盤面ではパスの列挙ができないので、盤面を大きく区切って部分問題を解いて繋げるみたいなのがやりたい。
ただまぁ、どうなんだろう。数が 9 まであるケースとかだと 9 の塊が激強になるので、アドホックに大きい数の塊を作りにいく方が良いんだろうか。
それとも上の方針でもある程度塊ができてくれるんだろうか。
5 乗強いよなぁ…。
ただまぁ、4 方向囲めるということは蛇上で少なくとも 3 個その数字が連続してないといけないわけで、そういう箇所はそのブロックの角に配置したらボーナスとかにすればそれなりに固まりやすくなるんじゃなかろうか。だめかな。
とりあえず明日は楽に試せそうなアドホック塊作成からやってみるか。
2 日目
よく考えたらあまり大きい数字がないケースだとアドホックは弱そうだし、盤面を区切って部分問題の方が最終的に焼き鈍しっぽいこともできそうで未来がありそうだ。そっち先やろう。
盤面を一辺が 3~5 の、$N' \times N'$ 個の長方形のブロックに分割する。
それぞれのブロック内は全探索する等して最適化する。一辺が 5 程度なら一筆書きのパス数も 10,000 通り程度っぽい（左上から右下なら 8512 通りらしい）ので、全探索可能だろう。
ブロック間をどの順で巡るかは…とりあえずサンプルと同じような左上からグルグルでいいか。ブロック数を奇数かつ上下左右シンメトリーに分割すればそれでまかり通る。
という訳で、今日はブロック内のパスの全探索まで実装できた。
試しに seed=1 の盤面を $7 \times 7$ のブロックと見なして時間いっぱい実行してみる。
おお、中々良い感じ。
最初の 8 手くらいがデフォの進行方向なので全然探索しきれてない感はあるけど、そこそこ良さそうに見えた問題ページのお手本と同じぐらいのスコアは出せてる。
10 秒で 1900 万通りのパスを見つけられたようなので、10,000 * ブロック数もまぁ間に合うでしょう。
3 日目
最適化した各ブロックを繋げる処理を書いた。
おぉ…いい感じ。下手したらアドホックより良いんじゃない？
ブロックの分割の仕方は良いロジックが思いつかなかったので真心を込めた。
if (N == 9) blockSizes = {3, 3, 3}; else if (N == 11) blockSizes = {3, 5, 3}; else if (N == 13) blockSizes = {4, 5, 4}; else if (N == 15) blockSizes = {5, 5, 5}; else if (N == 17) blockSizes = {3, 3, 5, 3, 3}; else if (N == 19) blockSizes = {3, 4, 5, 4, 3}; else if (N == 21) blockSizes = {4, 4, 5, 4, 4}; else if (N == 23) blockSizes = {4, 5, 5, 5, 4}; else if (N == 25) blockSizes = {5, 5, 5, 5, 5}; else if (N == 27) blockSizes = {3, 4, 4, 5, 4, 4, 3}; else if (N == 29) blockSizes = {4, 4, 4, 5, 4, 4, 4}; else if (N == 31) blockSizes = {4, 4, 5, 5, 5, 4, 4}; else if (N == 33) blockSizes = {4, 5, 5, 5, 5, 5, 4}; else if (N == 35) blockSizes = {5, 5, 5, 5, 5, 5, 5}; else if (N == 37) blockSizes = {4, 4, 4, 4, 5, 4, 4, 4, 4}; else if (N == 39) blockSizes = {4, 4, 4, 5, 5, 5, 4, 4, 4}; else if (N == 41) blockSizes = {4, 4, 5, 5, 5, 5, 5, 4, 4}; else if (N == 43) blockSizes = {4, 5, 5, 5, 5, 5, 5, 5, 4}; else if (N == 45) blockSizes = {5, 5, 5, 5, 5, 5, 5, 5, 5}; else if (N == 47) blockSizes = {4, 4, 4, 4, 5, 5, 5, 4, 4, 4, 4}; else if (N == 49) blockSizes = {4, 4, 4, 5, 5, 5, 5, 5, 4, 4, 4}; else assert(false);
意気揚々と提出してみたけど、53.82627 点の暫定 6位 / 23 人。
現時点でトップの wleite 氏が 97.04701 点。結構差あるな…。
サンプルは 25.77381 点。
試しに N = 17 の場合のブロックサイズを以下のように変えてみたら該当するケースのスコアが平均 2 倍くらいになった。
// else if (N == 17) blockSizes = {3, 3, 5, 3, 3}; else if (N == 17) blockSizes = {6, 5, 6};
やっぱり探索空間小さすぎだよね…。あと隣のブロックとの連携があまりうまくいっていなそう。
ただ、$5 \times 5$ ブロック 1 つ、$5 \times 6$ と $6 \times 6$ をそれぞれ 4 つずつを全部全探索して 5 秒くらいかかるので、結構シビア。
枝刈りとか高速化頑張る…？
DFS 中に壁にぶつかって左右にしか進めないとき、目的地が含まれる方向しか探索をしないようにしたら 1.5 倍速くらいになった。
これで $6 \times 6$ ブロック 9 個くらいなら大丈夫。
これに伴いブロックサイズとして 6 を採用したり 5 の割合を増やしたりして、ぼちぼちスコアが伸びた。
現時点で 62.48415 点 3 位 / 26 人。
あとは実行時間持て余してる（概ね 300ms 以内くらいで処理終えてる）ので、何かに使いたいが…。
ブロックの分割の順序をシャッフルして一番良かったのを採用ってのは試したけど、どうも小さいブロックを端に持ってくるのがベストっぽいのであまり意味はなかった。
ブログ読み返してたら焼き鈍しっぽいこともできそうって書いてあった。
焼き鈍しまでは行かなくても、全部の move を決めたあとに再度ブロック毎に最適解を全探索し直すとかはありな気がする。
ただまぁ、wleite さんとの差を詰められるアイデアとはあまり思えない…。
4 日目
特に良いアイデアが思いつかないので、ブロックの分割方法の調整と、全部の move を決めた後に再度ブロックごとに最適化し直すやつをやった。
ブロックの分割方法調整で平均 8% くらい、ブロックの再最適化で 6% くらいスコアが伸びた。
で、提出してみるも、61.69072 -> 62.11491 と僅かな伸び。…？？
ジャッジサーバ上でも時間制限で打ち切ったケースが 9000ms 程度で終わってるので、多分 TLE ではないと思うんだけど…。RE？
同じものを提出し直してみるも、61.78212 だった。むむむ…。
って言ってたら配列外参照を見つけた。はい。
直して提出して 64.87449 点。うーん、もうちょい伸びる気がしたけど…。
今気付いたけど前回提出分は pretest で変なログ出てた。ほぼ全ケースに付いてたからこれがデフォなのかなと思っちゃった。
Test Case #2: Score = 610867.0 Run Time = 6081ms *** stack smashing detected ***: <unknown> terminated
5 日目
ブロック内の DFS 中にタイムオーバーしたらそこで探索を打ち切ってその時点での最善パスを返すようにしていて、一つもパスが見つからなかった場合は assert してたんだけど、よく考えたら探索開始直後にタイムオーバーしたら RE になるなというのに気付いた。それはそう。
修正して 68.35566 点。これはまぁ納得のいくスコア。
後はブロックの端に置いた数字の大きさに基づくボーナスを大きくしてみたりしたけど、全体としてはあまり大きなスコア変動はなかった。
行き詰まってきたので最初に考えていたアドホック案を考えてみる。
大きい数が snake 上で 3 連続していたら 4 方向囲むチャンスなので、3 連続箇所の数分 4 方向ポイントが手に入ると考えよう。
seed = 2 の snake 上で 3 連続箇所を集計してみると、999 が 4 箇所、888 が 10 箇所。
ざっくり $9^{5} \times 4 + 8^{5} \times 10 = 563,876$ 点？今のスコアが 610,867 なので 4 方向囲む以外もちょっと工夫すれば追い抜ける？
他のケースも見てみたけど、そもそも盤面大きくないと 3 連続はあまり発生せず、4 方向囲い特化のみで抜けそうな感じではなかった。
あと考えられるとしたら、全探索 DFS の枝刈り…？
6 日目
アイデアが尽きたので出力結果を眺めてみる。
うーん、空いてるセルがもったいない感じ。
隣のブロックが既に配置済みで空セルがあったら侵食して OK にしてみても良いかもしれない。
7 日目
昨日の隣のブロックに侵食するアイデアはあまりスコア伸びなかった。最後の望みが…。
仕方がないのでブロック分割のパターンを追加したら平均 6% くらいスコアが伸びた。Previsional score は 65.13451 -> 67.82326。
そこで多少伸びるならプロファイラ走らせて高速化頑張るのもやった方が良かったかもしれない。
残念ながら Windows 用の CLion ではプロファイラが使えないっぽいので、今回は時間切れ。
最終スコア
| seed | score |
|---|---|
| 1 | 3269 |
| 2 | 610867 |
| 3 | 212816 |
| 4 | 218809 |
| 5 | 10875 |
| 6 | 465379 |
| 7 | 95797 |
| 8 | 146462 |
| 9 | 35218 |
| 10 | 105460 |
暫定順位は 19 位 / 59 人。
もう少し上まで行きたかったけど、ブロック分割に限界を感じつつ他のアイデアを出せなかったので残当という感じ。
また次回頑張ります。
