TopcoderのMarathonMatch135に参加しました。
問題はBridgeBuilder。パズル「橋をかけろ」のほぼコピーでした。
結果は提出44人中、17位でした。（暫定も17位）
問題
パズル「橋をかけろ」を解いてね。
頂点は全部使わなくてもいいし、連結成分がいくつかに分かれてもいいよ。
でもスコア的には大きい連結成分が1つある方がいいよ。
1辺の橋の上限数(C)はケースによって2～5だよ。*1
考察
パズルの解法は理解。
部分解（それなりの大きさの連結成分）を求めるのがそもそも大変そう。連結成分に含む全ての島が条件を満たしていないといけないので、大きい連結成分を見つけるために「広げる」、連結成分を完成させるために「収束させる」という2つの方針を両立させないといけない。そんなボドゲあったな。
小さめのものを見つけるのも大変だし、小さい連結成分に島を付け加えて大きい連結成分を作れるかというと、そういう保証も無いように見える。そうなると、適当にガチャガチャやって上手くいくか見るしかない…のか？
連結成分同士が干渉せず、スコア計算も完全に分かれているのは日本橋ハーフのマッサージチェアっぽい。うーん、解法も同じにしてみるか？
使う島を決めればパズルを解くだけになる。そうして成立する連結成分をいくつか求めたら、得点が最大になるよう組み合わせる。大きい連結成分を作れるように島たくさんでも探索したいが、それが出来なかったときのために小さめでも探索したい。うーん、島2個からランダムに1個ずつ増やして、最大まで行ったらリセットの形にするか。
連結成分の組み合わせは、スコア的にはほぼ貪欲になりそう。とりあえず貪欲で組んだ後は、焼きなましやビームサーチでも出来そうだけど、今まで使ったことの無いchokudaiサーチを使ってみようかな。
やったこと
島を全部連結
パズルを解く。
1方向にしか繋げない場合と、任意の方向に橋をかけないと矛盾が生じるパターンに対応。確定で橋を増やせる場所が無いなら頂点を1つ決めて、分岐で各方向に橋を1つかける。*2
seed1～1000のうち、996～997ケース程度は時間内に計算可能。
全て同一の連結成分に出来るもの、複数の連結成分に分かれるもの、解決不能なものがある。*3
そのため、全部の島を使うのが最善ではないケースがある。seed=1が分かりやすい。
上手く行かないケースではサンプルコードの解をそのまま出す。
提出結果は12点。
島2つ成分を列挙
探索出来る回数にもよるけど、小さい連結成分は全列挙して良さそう。
とりあえず島全部の連結に加えて、この成分を使って貪欲に組み合わせる。
提出結果は13点。
島N個成分を列挙
島2つから始めて、接続可能な島をランダムに1個ずつ増やす。
重複する島成分は島有無のZobristHashで排除。組み合わせることを考えると橋の有無単位でHashした方が良かったかも。まぁ、連結成分の大きさでほぼ決まるので誤差だと思うことに。
連結成分が2個以上に分かれるのは許容した。これを弾くとスコアが下がる。あと、連結成分の登録は横着して複数連結成分を1セットで登録した。（この辺の仕様が決まり切らないので作り切れなかった）
橋の数の和が奇数になる場合は成立しないのでシミュレート自体スキップ。
提出結果は47点。
組み合わせをchokudaiサーチに
各種ブログやツイートを参考に組む。
時間軸ごとの優先度付きキュー（元ツイートだとHeapというものだった）が溢れてしまい、capacityの自動拡張か、あまりに悪い状態を追い出す機能（両端キュー）のどちらかが必要そうとなる。
今回はほぼDFSで良い問題と見て、溢れるならキューに入れないという最悪な対処でなんとかする。
提出結果は49点。
前計算＆枝刈り
モンテカルロ系でもそうなんだけど、シミュレーションの妥当さというのは大事。妥当でないパターンを延々計算するのは無駄なので、枝刈りするべき。
同時使用できない島を求める。
C=2でBi=7の島を使うと仮定すると、必ず4方向に橋を張らないといけない。そうすると隣接の島も使うので、その島でも同様に必ず張る橋を…と再帰的に求める。この"必ず使う橋"同士が交差する島は同時使用できないと言える。
島を増やすとき、同時使用できない島を考慮する。
提出結果は55点。
何も分からん
明らかに上位と別ゲームをしているので、方針の見直し。
6000msから既存の連結成分を拡張する方針にしてみたり、単純な拡張ではなく焼きなましにしてみたりと色々実験するも改善なし。
やっぱり既存成分の拡張はあまり意味が無いのかなぁくらいの確認に。
それなりの人数が一晩レベルで高得点を取っているので、そんなに難しい手法では無さそうだけれど…。
ランダムに橋を増やす
全く別の解法に着手。
橋を適当に置いて行って、パターンが成立か破綻するまで続ける。（もちろんゲームルールから自明な橋は置く。）
CやEが多いケース（生成ルールに対して多方向に橋を張りやすく破綻しやすい？）、島が少ないケース（従来手法の方がはまる）、あたりは苦手な様子。
これだけで提出すると54点でちょっと下がる。
Cと島の数で戦略を切り替えて59点。
駄目押しの高速化で60点。で終了。
他の人の解法を見て
愚直に辺ごとの橋の数を探索するだけで良かったっぽい。
枝刈りが上手く効いたりラッキーで時間内に妥当な解を見つける必要がありそうなんだけど、なんか上手く行くらしい。
実行時間が間に合いそうもない手法に突っ込んで撃沈するのはいつもやりがちで今回は避けたんだけど、よりによって今回は当たり方針だったという。試さなかったのが悪いのはそれはそうなんだけど、なんかすっきりしない。
感想
〇初めてchokudaiサーチを試した。
〇過去の知見を活かした。
×過去の知見を活かした。
〇今月あと2本マラソンがある。
×今月あと2本マラソンがある。
