AHC003に参加しました。
問題名はShortest Path Queries。
インタラクティブ問題で、最短路探索＋コスト推定です。
暫定テストは90.7Gで、提出1000/AC875 人のうち、316位でした。
→システス308位。→リジャッジ309位。
問題
経路を送ると経路全体のコストが返されるので、
1000経路のコストを全体的に低くしてね。
最初読んだ雑感
・1クエリあたり2ms。大したことは出来なさそう。
・それって結局O(1)あたりの性能が問われるのでは。
・どう見ても数学問題なんですが、数学問題が苦手な方にお勧めとは…？
【AHC003】AHC003は現在開催中です。200時間の長丁場なので、ゆっくり参加してください。
— AtCoder (@atcoder) 2021年5月22日
1問だけに取り組み、出来るだけ良い解を作るコンテストです。数学問題が苦手な方や、1問にしっかり取り組みたい方、実装力を活かしたい方にお勧めです。https://t.co/3SCVS8yi9d
考察
M=1とM=2があって、M=1は行や列ごとにコストがほぼ一定、M=2は行や列ごとに分割点があり、そこでほぼ2種類のコストに分かれるという感じ。
スコアの重み(0.998辺り)は前半717回≒後半283回になるっぽい。とはいえ700回かけて調査は長すぎるかな。300回くらい？→実際は200回前後になった
辺は1740個あり、1回に探索する経路長は最短経路なら10～60。*1経路長35として全部の辺を2回ずつ通るには最低100回くらいの探索が必要、端の辺は通る機会が少ないので実際はもっと必要といったところか。
経路を重ねると差分を取る戦略が取れそう。[A→B→C→D=10]で[A→B→C=8]なら[C→D=2]みたいな。
やったこと
今回はモチベーションが出なかったのでM=1だけ想定して行・列の推定だけ雑に行った。
お気持ち計算で以下の感じに。
コスト={全体コスト/経路長}
確度={特定の列(行)の経路長 / 全体の経路長 * 0.9}
探索時の経路は[横→縦]か[縦→横]の2通りで確度が低い側。*2
スコア稼ぎ時の経路はダイクストラ法。何気に競プロだと初めて実装したらしい。
ダイクストラ時の辺の重みは{コスト * 確度 + 5000 * (1 - 確度)}。
やらなかったこと
M=2の想定や、Dによる分散への対応。
1740辺を全部持つのは本格的に統計でコストと確度を導かないと厳しいかな。行内で2箇所が分かれば間は大体同じコストという推定はできそう。適当にやったらスコアが下がった。
行や列ごとに2分割で持つ方法は雑計算とは相性良さそうだけど、それでも実装すると1日以上飛びそうだったので断念。
あとは経路の差分取りもMM122のマインスイーパに近いので頑張れば出来たのかもしれないけど、こちらは時間が短いし実装すると時間がかかりそうだったので以下同文。
感想
今回は周囲の空気感も掴めていないので感想も無しで…。
