RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)日記編

2/19週は多くの時間を「RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)」に使ったのでその日記になります。

最終的には過去最高の順位が出たのですが各アイディアを組み立てる段階では紆余曲折やドツボにはまったり、アイディアが形になったのが土曜の夜で最後の最後ドキドキの展開が待っていたりとスリル満点な1週間でした。

2/18(Sat)

東京から大阪に戻っている途中でAHC018スタート。問題文だけ確認。

家と水源を岩盤を壊しながらつなげる問題。頑丈さが未知なのでこれを推定しながらよさそうなルートを見つけるのがポイントになりそう。

夜にテストケースをダウンロードしつつVisualizerで眺めてみます。頑丈さの高いエリア(山)は局所的に存在しているのでうまく回避できると良さそうです。

部分問題として

初期状態での家、水源の頑丈さの推定
セルの頑丈さの推定
セルの頑丈さの推定値とCから最適なPの算出
頑丈さの高い領域の推定
セルの頑丈さの推定値から経路を算出

を考えることになりそう。統計をとりたくなる問題で結構得意な分野かもしれません。

いったん頑丈さが分かっている前提で最適経路を考えます。最小費用流っぽいか？と思うもののうまく持ち込めずしばらく考えて

貪欲より良い解があるケースがある
最適解を出すのはNP困難っぽい

という気がしてきて^[1]終了後に知りましたが「最小シュタイナー木問題」というNP困難な問題でした。いったん貪欲でやってあとで焼きなましてみることに。

今回はインタラクティブ問題なのでJudge側とPlayer側を書いている最中に2時を回ったのでいったん終了。

2/19(Sun)

サンプルと同じロジックを目指します。経路復元がバグって苦しみますがようやく動くように。submitして平均コスト(消費体力)270K, 相対スコア16.0Gで117位。

手元で1万ケース分回して最大/最小コストを見てみます。

最小コストは家が1個で距離最短がそのまま解になるケース。順位は相対スコアで評価されるので「最短距離決め打ちに大負けしない」ようにする必要がありそうです。

逆にコスト最大は山を突っ切るパターン。やはり迂回路を探す必要がありそうです。

頑丈さが分かっている前提で貪欲法でコストが少なくなる経路(理論解と呼びます)を算出してみます。(自前のVisualizerの結果のため色合いが異なります)

この後、山登り・焼きなましと進もうかと思っていましたが、見るとかなりそれっぽい経路になっているので深追いしなくてよい気がして、理論解はいったん打ち止め。

頑丈さが分かっているとコストは1/10くらいで済むので頑丈さ分布を推定するのが大切そうです。手元のテストケースで頑丈さ分布を確認することに。

2つ大切なことが分かって

1つは隣接セルの頑丈さは非常に相関が高くて分布まで分かること。分布が分かればパワー選択の最適化ができそう。

もう一つは頑丈さが低いところはある程度は頑丈さが低いところ(平地)が続き、家/水源は平地で連結されている可能性が高いということ。

今までだと色々と可視化、考察を続けるところですが今回は実装、実験をちゃんとしようと思っててアイディアを書き出して実装に入ります。1時半くらいまでやって3割くらい書き上げたところで今日は終了。

02/20(Mon)

近いセルの頑丈さは似ているので距離[math]D[/math]刻みで探索してみます。

ユークリッド距離が[math]D[/math]の格子点から最短路方向の点を選ぶようにします。それっぽい動きをし始めますが

掘削して破壊できないときに頑丈さを更新＆周辺に伝播しないといけない
２点間の推定コストを「２点の平均コスト x 距離」だと山からわざと離れたり、延々と平地を探す
似たような場所に経由点を生成する

と次々と課題が見つかります。うーん、思っていたより難しい。

ちょっとまだバグが残っているけど眠いので早めに終了。

2/21(Tue)

昨日は眠かったはずなのに頭が妙に冴えて眠りはいまいち…。

このあたりで一度submitしてみます。

が、TLE…。掘削回数が多いとTLEするようなのでパワー選択の最適化を考えます。

頑丈さの下限が[math]l[/math]と分かった時に真の頑丈さ[math]s[/math]の条件付確率[math]p(s|l)[/math]は事前にサンプルで集計できます。そこからパワー[math]i[/math]を加えたときに初めて壊れる確率[math]p_{i,l}=p(l+i|l)[/math]も事前に計算できます。ここから

DP[l]: 下限がlであることが分かっているときに破壊に必要な期待コストの最小値

と置きパワー[math]P[/math]をかけると

確率[math]\sum_{p\leq P}p_{p,l}[/math]で破壊
確率[math]1-\sum_{p\leq P}p_{p,l}[/math]で下限が[math]P[/math]増えた状態に移る

ので期待値DPで期待コストが最小になるパワーを出せます！さらに下限が[math]l[/math]の時に次にかける最適パワーを見るとほぼ線形になります。

線形回帰して係数だけ埋め込むことができそうです。我ながらこれは結構良いアイディアな気がしてワクワクしながら実装して実験するとなぜか悪化…えぇぇ。パワー100固定より悪いハズはないので明日調査しよう。

2/22(Wed)

ログを出しながらデバッグ＆ロジック改善。一番効いたのは

家/水源を100固定で破壊すると真の頑丈さが高く見積もられ後続を高いパワーで掘削してしまう
ルートの起点となる家/水源は細かく刻んで壊す

を入れると15%くらいコストが改善。ふぅー良かった。

明日は家族でお出かけなのでそれまでにPCをぶん回す系のタスクを作りたいところ。

頑丈さが分かった前提でのコスト最小路を山登りで探すのを再開。が、改善は誤差レベルで再びこの検討は断念。何かやりようはある気がするんだけどなぁ。

今まで距離Dの格子点をランダムに選んでいたのですが、変に近い点が大量に生成されて100回に1回くらいTLEしたり確率的なコーナーケースで1000回に1回くらい非連結になったりと辛いことが多くなってきたので一度、単純にグリッド格子点にすることに。

実装が面倒かと思いきやむしろシンプルになって無駄な探索が減ってスコアも20%くらい改善してTLEも解消。こんなことなら最初からグリッドにしておけば良かった。

3日ぶりにsubmitして平均コスト146K, 相対スコア22.9Gで102位。

手元で実験するときは理論解との比を見てて、今だと平均3.8。上位陣は自分の半分以下のコストなので2を切る世界に行っているのかぁ。すごいな。

2/23(Thr)

この日は家族で「ひらパー」ことひらかたパークに行ってました。

子供の雪遊びデビューでいきなり雪山に行くよりお手軽で良かったですね。

行き帰りで考えたことは

周辺探索時はコスト最小化ではなく真の値との誤差を減らしたほうが良いかも
経路探索時は常に水源から家に近づくようにしているが双方向から近づいたほうが良いかも
経路が見つかった後にもう少し周辺を探するとより良いルートが見つかる？
家/水源を近い順に結んでいるけどつなげる順を全探索したら良くなる？
コストの増分を要素分解してみてみる

で明日の仕事中の時間を有効活用すべく家/水源の連結順を全探索してみることに。

2/24(Fri)

全列挙した結果を見ると

1/3くらいで改善
改善したものは平均1.6%程改善
最大で17%改善したケースあり

と思っていたより改善していた。良くなったものは貪欲だと

なのが、うまくやると

こうなって経路を共有して全体のコストを下げられる。計算時間的に間に合うかって話はあるけど差がつくポイントかも。

最初に距離Dの範囲からランダムに経由点を選ぶコードを書いてそれを引きずって色々とバグの温床になっていたのでやりたいことを整理して書き直すことに。

職業病で複雑なロジックはついパワポで整理。

ログを出して可視化しながら慎重にコーディングします。が、なぜか経路復元ができなくなってドはまり。目的に応じてデータの持ち方を微妙に変えた結果この1週間で4回くらい経路探索＆復元を書く羽目になってそのたびごとに経路復元でバグらせています。

結局2時間くらい苦しんで原因はオーバーフロー。初期段階で変に高速化を意識してunsigned shortを使うようにしたのが失敗のもとでした…。

デバッグで体力を使い果たしこの日は終了。残り2日で実装できるかちょい不安です。

2/25(Sat)

朝起きると昨日動いていたはずの経路復元が再び動かなくなっています…。

これまた2時間くらい悩んで結局、ヘッダで定義した内容が反映されていなかったのが原因でrebuildしたら動きました…ひどい時間ロス。

ようやく動くようになったものの水曜の提出よりコストは悪化しているのとTLEとなるサンプルがあるのでまだ道のりはあります。

今まで未推定のエリアは不確実さを考慮して悲観的に高い頑丈さを設定していましたが

大多数のケースでは平地で連結にできるので楽観的に未推定エリアは低めに見てもよいのでは？と思い実装。

あと家/水源の両方サイドから近づくようにします。これでほぼ水曜の結果と同じコストまで来ます！

いったんここでどこを詰めればよいかコストの増分を要因分解して考えます。

理論解と比較して今の解がどこでコストがかかっているかを見ます。コストは

周辺探索時のパワー
周辺探索のセル破壊時に余分にかけたパワー
周辺探索時に余分な掘削回数で発生するコスト
算出した経路自体の差
経路掘削のセル破壊時に余分にかけたパワー
経路掘削の掘削回数で発生するコスト

に分解してみます。（要は理論解を頑丈さとぴったりのパワーで破壊するのが理想形でそことの差分を比較）

思っていたより周辺探索にコストをかけてしまっているようです。どうも「山」を認識するためにかなり掘削しているのが気になります。

試し掘りの結果から真の頑丈さを推定する問題を考えます。今まで適当に下限に1.1をかけた値を使っていましたが、ちゃんと下限[math]l[/math]と真の頑丈さの50%点[math]S_{50}[/math]の関係を見ると

「[math]S_{50}=500+2l[/math]」とかなり大きく推定して良さそう。え？ホントに？と思いつつテストすると一気にコストが10%以上減ります。

これをsubmitして相対スコア30.6Gで77位で二桁順位に入ります。

となると破壊できた後の頑丈さ推定も丁寧にやったほうが良い気がしてチューニングするとさらに10%コストが減ります。

パーツが揃った感じで気になったところを直すと改善につながって非常に楽しい。Visualizerでみても

自分が思い描いていた探索ができていてて一人悦に入ります。気分的にもうやりたいことはやり切った気になってきます。この日は満足感に包まれながら就寝。

2/26(Sun)

朝起きるとマシンがつながりません。再起動してみてもダメ。なぜ？と調べたら死んでいたのはネットワークでした。むー、なぜこのタイミングでこんなトラブルが…。

うまく解けていないサンプルを見ると陸の孤島があって山を登るしかないのに楽観探索を続けているケースだったので一定のコストを超えたら楽観探索をやめることに。他にもざっくり定数で与えてたものを線形補間したりして改善。

この段階で出すと

相対スコア35.0Gで39位！

商品圏内に入ってます！このまま終わってくれーー！！

まだパラメタチューニングをほとんどしていないので伸びしろがあるはず…とパラメタチューニングに入ります。

グリッド幅Dのチューニングが効きそうなのでやってみたのですが性能が変化せず。なんで？と思って調べたら

プログラムでD=5以外も読めるようにしたつもりがD=5の結果を読んでいた
データをD=6-10で生成したつもりがD=5を生成していた

と複数のミスを発動させていたことが発覚。終盤になり作業品質も落ちています。

幅Dは5から10まで用意したのですがD=10で張り付いてもっと大きい方が良さそうですが、ここからデータ生成をする時間がないのでD=10を採用することになりそうです。せっかくOptunaを使おうと思っていたのですがパラメタの自由度がなくなって結局は全部試して一番良かったのを採用しました。

さぁこれでさらに伸びてダメに押しになるはずです。Submitすると…

相対スコア35.5Gで39位！

え？あれ？？変わってない？いや、変わっているけど順位は変わってないんだ…。あーみんな伸ばしているのか…。

うー、どうしよう。時刻は17時でもうネタも時間もありません。最後、手持ち資産で家/水源の接続順を試すロジックを上乗せします。

手元の環境だと0.5%くらい良くなります。最後のお願いで出すと

TLE！

え？なんで？手元の環境だと間に合っているし、そもそも時間で打ち切っているし…。よくよくソースコードを見ると時間計測のバグを見つけます。時刻は18:15。実質的に最終提出です。祈りつつ出すと