参加しながら考えたこと試したことの源泉かけ流し。
最終的な方針は まとめ にまとめてあります。
問題概要
N×N のグリッドがあり、各セルには -V ~ V の整数（0は除く）が書かれている。あなたはこのグリッド上で、各表面に整数が書かれたサイコロを転がしていく（側面を上下左右の隣接セルに接地させて転がしていくイメージ）。サイコロを転がすごとに、今いるセルに書かれた整数の絶対値とサイコロの底面の整数が一致した場合、今いるセルに書かれた整数がスコアに加算される。同じセルは一度しか通れない。経路の始点と終点が隣接セルのとき、スコアにボーナス B が乗算される。サイコロの各面の整数とサイコロを転がす経路を決めてスコアを最大化せよ。
1 日目
問題を読む。...サイコロ転がす系かぁ。実装がダルそうなイメージ。
サンプル gif を眺めていたが、緑になったとこが一致したセルかな？と思ったら、v が正なら一致した場合に緑、v が負なら不一致の場合に緑らしい。
初見だと直感に反したけど、要するに緑が多いほど嬉しいってことね。
決め打ちした経路に対する最適なサイコロの目は遅くとも O(経路の長さ)、うまくやれば定数時間で求まりそうな気がする。
ので、経路の変更を遷移としてその経路に最適なサイコロの目でスコアを評価する焼き鈍しかな？
決め打ちしたサイコロの目に対する良さげな経路を探す...のは筋が悪そうに思える。
作る経路は長い方が良いのか？
負の値のセルの割合は最大でも 0.3 なので基本的に長い経路の方が良いことが多そう。
まぁこの辺は焼き鈍しやるなら人が考えることではないかも。
Bonus は狙った方が良いのか？
常に狙うと経路の多様性が結構減っちゃうので、Bonus 倍率小さいときはリングにしない方が良さそう。
必ずリング状の解を作るソルバとそうでないソルバを作って、B の値のどのあたりを境界として二つのソルバの強さが逆転するか実験する必要がある？
どんな遷移をする？
パッと思いつくのは経路のある区間を消し去って、ランダムウォークで繋ぎ直すやつ。
経路の変更はその区間だけでも、後続する経路に接するサイコロの面が全部変わるのが面倒だなあ。うまく定数時間でエイヤができるといいけど。
近傍は近い方が良い気がするのでランダムウォークせずに脇に経路をちょこんと膨らませるとかでも良いかもしれない。
うーん、これ遷移時に繋ぎ直した部分より後ろの経路に関する情報定数時間で更新はムズいんじゃないか...？
ある箇所より後ろでどの面がどの数値を何回通ったみたいな情報を定数時間で出せるならそれは累積和っぽいデータ構造のはずで、そんなデータ構造の更新が定数時間でできるとは思えない。
あ、あとリング状の経路の良いところとして、スタート地点を自由に変えられるというのがあるな。
なので、リング状経路に対しては最適なスタート地点とサイコロの目を求めることになる。
どの面がどの値に何回接するみたいなのは、スタート/ゴール地点を一つずらしても差分計算が可能なので、最適なスタート地点も求めるのはそんなに計算コスト大きくないと思う。
ひとまず、ある経路に対してどの面がどの数値に何回接するか愚直に求めるやつ書こうか。
盤面の外周をぐるっと一回りして、自前のスコア計算とテスタのスコアが一致することを確認した。
次はこの経路に対して最適なサイコロの目を求めてみて、スコアが上がることを確認する。
100 ケース回して全ケースでスコアが伸びたのでまぁ大丈夫でしょう。
（スコアベースでコードの正当性を測るのはあまり良くないが...。）
じゃ最適なスタート地点も求めるやつやるね。
やった。長さ 900 のループ経路に対する最適なスタート位置とサイコロの目の計算を 1000 回やって手元で 230ms（多分本番だと 500ms 弱くらい？）。
うーん、どうだろう...。焼き鈍しするにはちと心許ないか。
でも最適なスタート位置まで変わることを考えると差分計算なんかできる気がしないんだよな...。
まぁ、とりあえず書くか、山登りを。
経路の繋ぎ変えが面倒なので遷移は経路の脇の 2 マスを追加するだけにしたら全然内側に辿り着けなかった...。
もっとがっつり変えなきゃだめっぽいのでやはりランダムウォークによる繋ぎ変えか。
2 日目
繋ぎ変えが面倒なので、ひとまずスコアが上がらなくても変更を採用するようにした。
これで盤面を埋め尽くすランダムなパスは生成できるようになったので、たくさんパス作ってベスト解を選ぶやつはできるようになった。
ここらで提出してみる。70 点くらいは欲しいところだが...。
60.11。なるほどですね〜。
まぁ、現状山登りですらないわけだからね...。
うーん、これどうせサイコロの目は V とか V-1 とか V-2 あたりになるわけだから、目とスタート地点は決め打ちした上で経路を最適化していく方が良い気がしてきたな。
と言いつつ繋ぎ変えの山登りを書いていた。
経路上のある点から別方向にランダムに進んで、元の経路の一部にぶつかったらそこと切り替えを試す感じ。
盤面の外周をぐるっと一回りからスタートだと、またも大きい盤面で中央が全然活かせない感じになった。むーん。
じゃあ初期経路はさっきまでやってた経路脇に 2 マス追加をランダムに繰り返したやつにするか。
悪くはないが、伸びはイマイチ...。焼き鈍しっぽくスコア低下も許容してみようかな。
いろいろ試してみた感じ、スコアの低下が 今のスコア * 0.01 * 残り時間の割合 未満なら採用するみたいにしたらぼちぼち伸びるようになった。
こういうのの調整ってどうやるんですか？わからない。
提出して 59.44 -> 69.77。むむー。
やっぱり方針間違えてない？
盤面状の各数値の合計を数えてみたら、今のスコアは V と V-1 のセルを全取得した場合に少し負けるくらいのスコアっぽい。
やっぱり V ~ V-2 くらいまでに絞ってなんかやった方が良いんじゃないかなあ。
例えば V だけに絞ると、サイコロの目を全部 V にして -V のセルを通らずに V のセルを全部通るようなパスを見つける問題になるわけで、そんな感じに。
3 日目
考えたんだけど、やっぱり今までやってた焼き鈍しは近傍が遠すぎるような気がするというか。
途中に道を追加するとそれより後ろが全変更になるのがちょっと厳しさあるんじゃないかなあ。
そんなだから、前から経路を確定させていくようなやり方の方が合ってるんじゃないかなあ。
V ~ V-2 のセル（と、-V ~ -(V-2) のセル）だけを抜き出して表示してみる。
# が -V ~ -(V-2) の部分。V=9 だと比較的スカスカだ。
これ # を避けつつうまいこと全部回れそうじゃない？
どう巡ったもんかなぁ...と思っていたが、こんなのを思いついた。
まず、サイコロの目は V, V-1, V-2 を 2 つずつだとすると、サイコロの状態は 90 通り。
で、多分、幅 2 の通路があれば、その通路上を通りつつ結構良い感じに拾ったり避けたりできると思うんですよね。
ほとんどのセルは無害なので、そこを適当に転がりつつサイコロの面を調整できるので。
なので、盤面状に幅 2 の通路を張り巡らせて、その通路状を DP しながら進んでいく。
DP テーブルは State dp[Y][X][サイコロの状態]; みたいな感じ。
いけそう！！！
いけたァ！！！！
seed=2 だと 7, 8, 9 のセルを全部拾って合計 1717 なので、このやり方の理論値の 85% くらいは取れてる計算。
あとこれ左上スタートの右下ゴールでループ状になってないので、その辺を調整すればまだ伸びそう！ウオオオオ
とりあえず提出しとこ！
69.25 -> 73.93。思ったより渋いな。こんなもん？
DP にはせいぜい 200ms くらいしか使ってなくて残りの時間は今までと同じ焼き鈍ししてるので、もうちょっと伸びると思ったのだけど...。
手元でも半分くらいのケースで +10% ~ +50% くらい改善してたので。
もっとスコア伸ばせそうなアイデアとしては、
- ループを作る
- V-2 未満の目も使う
あたり？
上と関係ないけど N≦8 くらいの小さい盤面では焼き鈍しより乱択をたくさん回した方が良いということがわかったので、そうすることにした。
サイコロの目を V-3, V-2, V-1, V-1, V, V にした DP も試すようにして、少しだけ伸びた。
ループ作ってまた少し伸びた。
画像だと分かりづらいけど、(2, 0) スタートで左 2 列だけ残して右でぐねぐねした後、残した 2 列を上に登って (1, 0) で終わる感じ。
提出して 73.83 -> 80.62。うんうん。
N % 4 == 3 のケースでぐねぐねの最後に無駄があるので明日直すこと。
あとぐねぐねの幅を柔軟に変更できるようリファクタしたい。
4 日目
N % 4 == 3 のケースでぐねぐねの最後に無駄があるので明日直すこと。
あとぐねぐねの幅を柔軟に変更できるようリファクタしたい。
やった。
N=14 とかでも、ぐねぐねの幅を 2, 2, 2, 2, 3, 3 みたいに、最後 3 で帳尻合わせて右から左の通路で終われるようにした。
ちなみにこれ、例えば 2, 3, 3, 2, 2, 2 だとまた違うスコアになるから、余裕があれば違うパターンも試してみたいところ。
あと DP の高速化（各 State が今までの経路情報の全部を持っていたので差分だけ持つように）をして DP 部分の処理時間が 500ms くらいから 20ms くらいに縮んだ。
これだけ速くなれば盤面回転されたパターンとかも試せるね。
回転した盤面での DP も試すようにして提出して 80.29 -> 86.22。OK!
手元で 100 ケース回したところ、ベスト解の割合は
- 乱択たくさん: 8 ケース
- 焼き鈍し: 6 ケース
- DP: 86 ケース
提出時のスコア的には伸び代がまだまだあるわけだけど、これ見ると DP を磨くべきなのかなぁ。
DP で V-4 の目も使ったり左右反転した盤面を試したりして少し伸びた。
幅 3 の通路を DP で通すのってあまり効率的ではないので、できれば使いたくない。
のだけど、N % 4 == 3 のケースだと幅 3 の通路が 3 つできちゃう。
これ、序盤は横方向の幅 2 のぐねぐねで最後の 9 行だけは縦方向の幅 2 のぐねぐねみたいなことをしたら無駄が少なくなったりしないかな。
↑ のやつはダメだった...。多分折り返し部分での効率があまり良くないからだと思う。ここらで提出しとこか。
ん、2 時間前に 86.22 だった相対スコアが 82.30 になってる。やば〜
82.30 -> 83.50。まぁそうね。
今の DP もそろそろ限界っぽい気がするので、別の何か考えないとなぁ。
手前から決めてくってのは悪くないと思うのだけれど。
5 日目
今 DP では V-2 以上の目は必ず使うようになってるんだけど、V=3 とかの場合は 1 は切り捨てて 2, 3 に回した方が良い気がしてきた。
DP でサイコロの目を V-1, V それぞれ 3 つずつでも試すようにして 83.49 -> 84.06。やはり V=3 のケースで 2%~10% 程度スコアが伸びているようだ。
改善の糸口になるかわからないけど、今の解がそれぞれの数をどれくらいの割合拾えてるのか調べてみよう。
まず seed=2。
Dice: 9, 8, 7, 8, 6, 9 1: 0/80(0%) -0/-32 2: 0/134(0%) -0/-56 3: 0/192(0%) -0/-81 4: 0/300(0%) -0/-132 5: 0/310(0%) -0/-165 6: 204/396(51%) -12/-174 7: 252/448(56%) -0/-245 8: 520/576(90%) -0/-224 9: 612/693(88%) -0/-252
1 面だけの目でも 50% カバーできるのね。V=9 でスカスカなのもあるだろけど。
2 面使ってる 8, 9 は 90% 前後。良いのか悪いのか。
あと N=30, V=3 の seed=19。
Dice: 3, 2, 3, 3, 2, 2 1: 0/237(0%) -0/-41 2: 406/542(74%) -10/-136 3: 582/678(85%) -15/-171
V=3 だとカバーしたいセルまみれになるわけだけど、思ったよりはカバーできてる。
うーん、これまだ伸ばせるのか...？
幅 3 の通路、一方方向に進むような遷移（下図の上）しか考えてなくて、戻るようなパス（下図の下）も取りうるんだけどな...と思ってたので、遷移を追加してみた。
アッ平均 2% くらい伸びてる！なるほどね〜〜
84.08 -> 85.73！ 本番サーバ上で DP に 2000ms くらいかかってそうなのでそろそろ雑に試行増やすのは控えた方が良いかもしれない。
もしかして...と思って N=24 の場合に全部幅 3 の通路にしてみたら普通に少し伸びた。ほえ〜〜
え、じゃあ幅 3 をベースにした方が良いってことですか？
もっと言うと幅 4 の方が良い？遷移がエラいことになりそうだけど。
とりあえず可能な限り幅 3 を使うようにしてみた。手元で平均 1.7% 増！
ただ遷移が増えて実行時間が少し余裕なくなってきた。
今は次の State オブジェクトを毎回作ってる（メモリ確保してる）ので、もっと遷移増やすならオブジェクトプールする必要があるかも。
提出して 85.72 -> 87.77。
6 日目
なんか今回の MM 本番サーバが手元に比べて速いな〜と思ってたけどデバッグ用に -O2 フラグ外したのそのままにしてた。アホ
State 用のメモリ事前に確保するようにしてみたけどそこまで劇的にははやくならなくて、1350ms が 1150ms になるくらいだった。ちぇっ
ぐねぐね折り返し時の特殊な遷移を追加して 87.93 -> 88.54。
7 日目
88 点台の団子の中にいたので、メモ取るのを忘れて少しでもスコアを伸ばそうと細かい調整に執心してしまった。
いろいろ試したけど一番効いたのは DP でのぐねぐねの幅のバリエーションを追加することだったと思う。
例えば N=14 で元々 {3, 3, 2, 2, 2, 2} でやってたのに加え、それを反転した {2, 2, 2, 2, 3, 3} もやる。
N が大きいケースだと DP で時間いっぱい使ってしまって後に控えてる焼き鈍しとか乱択たくさんは試せなくなるわけだけど、N が大きいケースは DP の方が強いので問題なし。
手元でのスコアは平均 0.4% くらいの改善。
まとめ
暫定順位 / スコア
16 位 / 88.89202
方針
- 幅 2 ~ 3 のループ通路を作り、その通路に沿ってサイコロを転がしていく DP をする。
- DP テーブルは
State dp[y][x][dice_type]のような感じ。dice_typeは各面のサイコロの目で決まる値。State は現在のスコアやサイコロの状態、前の State のポインタ、前の State から今の State への経路等を持つ。 - ループ通路のパターンは 2 通りしか用意してないが、入力された盤面の回転と左右反転させたものでも試して最大 16 通り。（N が大きいと制限時間オーバーで試せないパターンもある）
- サイコロの目は以下の permutation を使う。
- V-1, V-1, V-1, V, V, V （20 通り）
- V-2, V-2, V-1, V-1, V, V （90 通り）
- V-3, V-2, V-1, V-1, V, V （180 通り）
- V-4, V-3, V-2, V-1, V, V （360 通り）
- DP テーブルは
- DP をやって時間が余ったら、
- N ≦ 8 ならランダムにループ経路を作って最適なスタート位置/サイコロの目を計算するのを時間いっぱい行い、ベストな解を選ぶ。
- N > 8 ならループ経路をランダムウォークで繋ぎ直す焼き鈍しをする。
- N ≦ 8 ならほぼ乱択がベスト、そうでなければほぼ DP がベスト、たまに N=9~11 くらいで焼き鈍しが勝つこともある、くらい。
