AHC043 解法決定から枠組み完成までの日記

コンテスト日記

※これはPostMortem・解法解説記事ではありません

コンテスト序盤の考察から数日で順位表を駆け上がる部分を日記として残しておこうと思い書いています。駆け上がれるかどうかはわかりません。長期コンテストの立ち回り方のサンプル1として参考になれば幸いです。

02/14

問題を見た。RECRUITさん作問の日本橋ハーフマラソンらしい問題だと感じた。ここ何回か参加した限りのハーフマラソンの問題の特徴は以下。

・おなじみの最適化手法が使える単純な構造が見当たらない

・数式的ではなくゲームに近い

そのため、最適化の「正しさ」みたいなものが保証できることがあまりなく、評価に趣向を凝らして貪欲に近い行動を行うか、行動を実際に適用してスコア計算をするなどが有効。

またデータ規模もAHCの最適化対象としては大きめで、これらがおなじみの最適化手法を妨げている原因の一つでもある。

今回も例にもれず同じような性質を持っているので大枠の取り組み方は同様で問題ないだろう。ただ、乱数要素がないため、問題を適切に変換すれば山登り・焼きなまし・ビームサーチが使えるだろう。

純粋に各地点間をつなぐとM本の鉄道を引けばよいが、家の密度やコストを考えるとtreeを作るのが妥当だろう。

keyPointになりそうな部分を押さえておく。

鉄道の交差禁止

平面上に鉄道を引く都合上交差はできない。厳密には鉄道駅を置くことで交差できるが、コストに余裕がないと無理であるので、基本は考えない方針で行きたい。

そのため迂回が必要になるが、50*50(=2500)点間の距離計算は何度も走らせられるものではないので、「最短距離でつなげられるものをつなぐ貪欲」みたいなものはナイーブに作っても間に合わない気がする。（いや定義にもよるが間に合うか）

いったん手動解を生成する。最後まで作るのは疲れる（かつ、重要なのは序盤の拡大再生産っぽい部分？）と思うのでIncomeが500になるまでやってみる。

大体400ターンくらいで達成し、残り400ターンは放置。

実験してみて再確認できたことは、

・最初につなげる一組はある程度遠いほうが良く（incomeが少なく2組目が遠いため）、段階的に大事ではなくなってきそう。これは直感的にincomeで5000を稼ぐのにかかるターンあたりと対応づく。

・一つの駅がたくさんの家・勤務地をカバーしているほうが良い。ただ、必ずしも全被覆をめざす必要があるのかはわからなかった。資金のインフレ率次第か。

・貪欲につなぐのが最適とは限らない（かつ、良いつなぎ方は評価しにくい）。1組目のincomeが大きいことが大事だが、2組目、3組目がスムーズに繋がられなければ序盤のインフレスピードが思ったより伸びない。上のGIF解は序盤の組選びを失敗していそう。

・順位表はまだまだ圧縮されそう。人の少ないseed0で雑貪欲、後半放置でも初期の10倍の資金になったので、おそらくもっともっと稼げるのだろう(いまは初期状態でも1Gある)

ひとまず、初日のアイデアを寝る前に書いておく。（手動解で確かめた感触ではまあまあ悪くなさそうなので、明日の用事中に改善が思いつかなければ、このまま最終方針になるかもしれない。）

案1

・被覆(駅の位置)を焼きなましor山登りで決定。

・駅の接続・接続順をビームサーチ（treeを先に決めたらそれに対する最適が求まったりしないよな・・・？）。

評価関数はincomeベースに残資金を加える。深さはターン数が適切か。

（逆にターン数ベースの評価値、深さincomeでもよいが、ビームが細く、無駄な計算も多そう）

・ビーム結果にしたがってつなげる（シミュレーション）。

駅の接続は接続先が4つを超えないようにすれば、適切に離れた駅配置なら問題ないはず・・・？

案2

treeの形状を焼きなまし部分で決定する場合。ビームサーチにtreeの形も決めさせるのは少々酷なので・・・

・被覆(駅の位置)とそれらの接続を焼きなましor山登りで決定。

・駅の接続順のみビームサーチ

・ビーム結果にしたがってつなげる（シミュレーション）。

被覆決定時に接続も焼くことで実際につなげるの際によりつなぎやすい配置になっていそう。

寝る前の今の私の意見としては案2を採用したい。

いずれにせよ、冒頭の通りハーフマラソンは性質上実際にやってみないことにはうまくいくかわかりにくい問題なので、途中で再検討する可能性がある。

2/15

予定のため最終決断はまた今度。入出力の整備はできたらする。のつもりだったがある程度考えを固めている。

寝ている間に「序盤が重要なら序盤の数個の設置を頑張って計算→後半は惰性で頑張る」みたいな時間リソースの配分がよいのでは？という気持ちになる。

以下、昨日から考えていたものもあるが忘れるといけないのでメモしておく。

隙間時間にできるだけもう少し正確に分析しておく。今回の資金増加は

・incomeが少なく、設置コストが律速であるうちはincomeをincomeに比例してあげることができる（これは微分が自身に比例しているととらえてもよい）ため指数関数的な成長を見せる。駅設置のインターバルが調和級数に近いふるまいをすることからも間違いないだろう。

・incomeがある程度増えてきたら、1ターンに1個しか置けないことが律速になる。人口が非常に少ない場合、このフェーズはないかもしれない。incomeは一定ペースで増え、総資産は二次関数的な成長を見せる。

・(あまりに都合よく拡大できた場合に限り)すべての人が利用するようになりincomeの成長は止まる。ここからは一次関数となる。

以上の流れにおいて、指数的フェーズ、二次関数フェーズ、一次関数フェーズはincomeという指標によってのみ一方向に進行していく。incomeを深さにを利用したビームサーチはその意味で強い合理性がある。同じincomeでも早いターンに到達できたものが最終的に資金が多くなるため、評価関数にも合理性がある。

序盤の展開については被覆を考える前に決定したほうが良い可能性もある。income500くらいまでの駅の設置順・接続を模擬的に所要ターンを見積もることで評価できる。有力候補が簡単に列挙することができるならビームサーチが効くが、愚直に駅候補を2500点で考えると有効な検索ができない。家と勤務地のペアのうち一方を抑えているものの相方付近に限定すれば、ある程度のビーム幅でシミュレーション可能か。人口の多いマップでは候補が多い代わりに500達成に必要な家も少ないので、何とかなると思われる。（厳密距離さえ使わなければ候補に対して評価値の計算はO(1)でできるため、2500候補と考えても幅100くらいできたりしないか・・・？）（冷静に考えたら、そもそも10^3ってそんなに大きな数字か？）

初期資金が11000ならはじめは距離15程度の二点しかつなげられず、20000ならギリギリ任意の二点がつなげられる。最初の鉄道によるincomeは指数関数フェーズのどの位置から始まるかに当たるため、かなり重要。相応に大きな距離をつなぐのがよい（最大にこだわる必要はない）。複数の人をつなげられてたくさんincomeが得られるようならなおよし。

二次関数フェーズになってきたあたりから、最適化の価値は少しずつ薄くなっていく。基本的に計算リソースが足りないので、このあたりで被覆するような駅を決めてしまって接続のみを考えることで妥協してしまってよい。被覆は頂点数を基準にして、タイブレークとして(25,25)からの距離和を利用するとよさげ。最後の接続を考慮すると駅範囲がかぶっていたらその数にあわせて減点したいが、高速な方法がほしい。

今回のコンテスト方針を仮決定する。この順で実装を進めたい

・「序盤のビームサーチ」と「次数が高々4のグラフから線路を生成する」部分を作成し、線路生成が可能か、将来性を判定する。できたら提出。

・「頂点被覆の決定」を雑に焼きなましで実装し、ビジュアライザで頂点被覆をみる。あんまり焼けていなくてもまあ良い。

・「接続順の決定」（あるいは「木の生成」→「接続順の決定」）をビームサーチで決定する。貪欲がそこまで悪いとは思わないので、まずは幅は小さくてもよい。できたら提出。

・接続は途中で打ち切ったほうが良い可能性があるため、どこまで接続するかを評価する。ここまでを前半戦のうちに出せたらある程度上位になっているはずで、そうでなければ方針ミスを疑ったほうが良い。

その後の展望として

・雑実装部分を高速化する

・treeの形が決まったところで改めて最初からビームサーチをしてみる

・あらかじめ線路構築を見据えたtree作成

など。主方針を決めてからの改善の余地はかなり多いと思われる。

そういえば、グラフが平面的かどうかは特定の形をマイナーとして含むかどうかで判定できた気がするが、実用的ではなさそうか・・・？もっとも、形がある程度適切な形であれば、そういった考慮はそんなに必要なさそう。

もしかして、序盤のビームサーチでは今後を見据えた線路を作る必要がある？例えば、最初につなぐのがAからBだったとして、その次にCにつなぐ場合、AからCを経由してBがつなげられたらCにつなげるときに1手でいいので結果的に早くなりそう。ビームの状態の持ち方は要検討だが、ありそうな候補が多いなら焼いたほうが良いかも。

上の懸念は無視してビームサーチに解を作ってもらった。

9 47
3 9
14 48
18 10
6 42
5 33
1 6
10 43
24 8
31 0

の順にやると260~270手あたりでincome500を達成できるとプログラムは言っている。本当かはわからない。

いわれた順につないだら248手でincome500を達成した。これはかなり早そう。

問題は、言われた通りに線を引くところで、駅のどの方向から出すか・どこで曲がるかといったのは手で順番につないでいく際はわからず何回か修正することになった。計算リソースで殴るか・・・？学術的な話だとrectilinear embeddingというのがあったが、あれは確か頂点位置が固定されてないのでそこからさらに変換をかける必要があるというのはうれしくない。

話は戻ってビームのほうだが、結局ビームの深さはターン、評価はincomeをベースにしたものを採用する。長期的に見ると片側だけ抑えている状況も有効であるため、ポテンシャルと称してそれらの和をとっておく。実行時間超過だがseed=3で400万達成と言っているので実現すればうれしいが・・・。

2/16

予定のためほぼ不参加。

計画から実際の線を決定するところで、良い方法があまり思いつかない。chatGPTさんに初めてビジュアライザを生成してみてもらう。比較的拡大しやすいseed8での計画はこんな感じらしい。（数字は構築順）

次数の制約やそのほかの性質もあってそんなに難しい形はしていなさそう。

しばらくは考察部分に変化なさそうで頑張って書く部分そうなので、何かあれば書いていく。

2/17

深夜に時間が取れたのでAHCをやっていく(2/18 0:00~6:00。2/17とは・・・？)。

バグをかなり踏んでいるよう。ChatGPTに書いてもらったvisualizerがある程度線路の形を作ってくれていたので何回かお願いしてグリッド上に起こしてみてもらう。これを提出プログラムにねじ込む雑仕様で乗り切れるか。線路の分岐方向にある程度性質の良さがあれば、適宜簡単な再ルーティングを行うことで生成には成功するらしい。