AHC020 解説

phspls

ALGO ARTIS プログラミングコンテスト2023（AtCoder Heuristic Contest 020）のコンテスト中 & 後に考えたこと、あと提出の内容と得点について書いています。
最終的にはコンテスト後に496,410,405点で本番6位相当の解法になります。

時系列に沿って書いており長いので、さっくり読みたい方は「方針立て」と「解法まとめ」を読み流してください。

問題へのリンク

方針立て

まず、問題文を読むと、

  • どの住民に対しても出力強度$${P_i \leq 5000}$$で放送を届けられる放送局$${i}$$が存在する

  • コストの総和に関わらず、放送を届けられる住民に差が出れば、より多くの住民に放送を届けられた方がスコアが高い

ことがわかります。そして、この問題の最適解ですが(局所でも厳密でも)、

  • 住人全員に放送が届く(前述の通り放送は届けるほどいいので)

  • $${P_i \gt 0}$$の放送局$${i}$$については、$${P_i}$$を$${1}$$でも下げると放送を届けられない住民が出てくる（そのような住民が出なければ、それは下げられる$${P_i}$$が存在するため、より良いスコアが存在することになる）

  • 放送局をつなぐ通信ケーブル網は最小シュタイナー木になる(出力強度が$${0}$$の放送局は木に含める必要がない)

です。なので

  • 放送が届かない住民が存在する

  • $${P_i}$$を1下げても放送局$${i}$$が放送を届けられる住民の集合は変わらない

といった性質を持つ状態には遷移したくないです。
そこで、

住民$${X}$$については$${P_Y \leq 5000}$$で放送を届けられるような放送局の一つである放送局$${Y}$$が放送を届けるようにし、使う放送局をシュタイナー木でつなぐ

と決めてしまえば、

  • この手法にしておけばそもそも放送を届けられない住民が出ることはない

  • 放送局$${i}$$は決められた住民に届けられればいいので、それを満たす最適な$${P_i}$$が自動的に決まる

とできそうです。というわけで今回の方針を改めて書くと

  1. 貪欲法なりなんなり「住民$${X}$$は放送局$${Y}$$が放送を届ける」という設定をすべての住民に対して決める

  2. 出力強度が$${0}$$より大きい放送局をシュタイナー木で結ぶ。ここまでを初期解とする

  3. 1イテレーションで「住民を一人選び、その住民に放送を届けられる放送局をランダムに選んで割り当てる。住民$${X}$$に届けるために必要な出力強度$${P_Y}$$がわかるので、放送局$${Y}$$の放送範囲$${P_Y}$$内にいる住民は全て放送局$${Y}$$が放送を届け、それ以外の住民-放送局ペアは前回のまま」という焼きなましをする

感じになります。
実際はコンテスト中にここまで考えていたわけではないですが、

  • $${P_i}$$を自由に変更するのは、自分ならバグを埋め込みやすい実装をやりそう

  • 焼きなまし等で制限時間いっぱいまで調整するので、$${P_i}$$を自由に変更するのは無駄が多そう

  • うまく実装しないと、ある住人に届くか届かないかのチェックに$${O(NK)}$$かかりそう

みたいな気持ちは発生していて、面倒そうな考慮することが多そうな、出力強度を自由に変更する手法を避けるようにしました。

コンテスト中の実装

実装順に書いています。乱数で点数がよくなっているだけのものは割愛。
端的にいうと「きちんと勉強しましょう」というような実装になっていました。方針立てで「焼きなましで〜」等書いていますが、きちんと学んだのはコンテスト後です。。。
コンテスト後にその辺直しているので、焼きなまし法はちゃんと使えば点数が跳ね上がることがわかる記事になっているともいえます()

343,337,521点解法

初期解を「それぞれの住民は一番近い放送局が放送を届ける」としています。シュタイナー木ですが、「プリム法で最小全域木を作ろうと試み、使う放送局全てが放送局$${1}$$と連結した段階で終了」としています。この段階では焼きなまし処理は実装していません。

ちなみに最小全域木の実装をミスして最大全域木となっているため点数が低いです。最大全域木という用語があるかは知りませんが、要はpriority_queueの降順昇順をミスしています。

350,486,041点解法

1イテレーションで「住民をランダムに一人選び、その住民$${X}$$に放送を届けられる放送局$${Y}$$をランダムに選んで割り当てる。住民$${X}$$に届けるために必要な出力強度$${P_Y}$$がわかるので、放送局$${Y}$$の放送範囲$${P_Y}$$内にいる住民は全て放送局$${Y}$$が放送を届け、それ以外の住民-放送局ペアは前回のまま」という焼きなまし処理を入れたつもりになっています。
ローカルに「昔焼きなまし法のテンプレート作ったような気がする」という、曖昧な記憶のファイルがあったので、それをテンプレート的に使って実装しました。中身をコンテスト後に調べたところ、診断人さんのブログに記載されている「以下のコード例は、上記の(2.B)の部分を無くした、スコアが悪くなった量は考慮しない焼きなまし法です。もっと効果的な方法「4. 遷移確率と温度」は必ず見てください。」の箇所のコード片を拾ってRustに書き直している途中のものでした。見ていなくて申し訳ないです。

そういうわけでこの時点では、スコアが悪くなった量を考慮しない焼きなまし法となっています。コンテスト後もしばらくこれが続きます。
ちなみにまだこの段階でも最大全域木です。

440,512,948点解法

最大全域木を最小全域木に直しました、それだけです。影響大きいですね。

456,622,911点解法

ここまででシュタイナー木を「プリム法で最小全域木を作ろうと試み、使う放送局全てが放送局$${1}$$と連結した段階で終了」として作っていましたが、この方法だとシュタイナー木の葉で出力強度が$${0}$$の使わない放送局があったので、それらを削除するように修正しています。

コンテスト後の実装

ここでも方針は変えていません。ここまでのまとめとして、コンテスト後の実装に取り掛かるまでに

  • 初期解を「それぞれの住民は一番近い放送局が放送を届ける」としている

  • 1イテレーションで「住民をランダムに一人選び、その住民に放送を届けられる放送局をランダムに選んで割り当てる。住民$${X}$$に届けるために必要な出力強度$${P_Y}$$がわかるので、放送局$${Y}$$の放送範囲$${P_Y}$$内にいる住民は全て放送局$${Y}$$が放送を届け、それ以外の住民-放送局ペアは前回のまま」ことをしている、スコアが悪くなった量を考慮しない焼きなまし法を使っての焼きなまし処理。

  • シュタイナー木を「プリム法で最小全域木を作ろうと試み、使う放送局全てが放送局$${1}$$と連結した段階で終了させ、そこから出力強度が$${0}$$の葉を消していったもの」として実装

という状態になっています。

458,804,552点解法

初期解を解説放送で話されていた貪欲解にしています。具体的には「住民$${1}$$をから順番に見ていって、$${P_i \leq 5000}$$の条件を満たすように放送局の出力強度のスコア分の増分が少ないように決める」です。
なおこの段階ではバグらせています(スコア分の増分なので、出力強度の二乗の差で評価しないといけないところを二乗していない)。

468,025,059点解法

1イテレーションが「住民をランダムに一人選び、その住民$${X}$$に放送を届けられる放送局$${Y}$$をランダムに選んで割り当てる。住民$${X}$$に届けるために必要な出力強度$${P_Y}$$がわかるので、放送局$${Y}$$の放送範囲$${P_Y}$$内にいる住民は全て放送局$${Y}$$が放送を届け、それ以外の住民-放送局ペアは前回のまま」だったものを変更しています。
変更後は選ぶ住人$${X}$$を「住人$${X}$$に放送を届けている放送局$${Y}$$の現在の出力強度$${P_Y}$$が、住人$${X}$$に放送を届けるために最低限必要な出力強度と一致する住民」の中からランダム、としています。

  • 変更前だと、1イテレーションが「ランダムに選ばれた住民$${X}$$にはもともと放送局$${Y}$$が放送を届けていたが、放送局$${Y'}$$に変わった。ただ放送局$${Y}$$は放送局$${Y}$$視点でもっと遠い住人$${X'}$$にも放送を届けていた。そこの割り当ては変わらないので放送局$${Y}$$としては出力強度$${P_Y}$$を落とすことができず、放送局$${Y'}$$の放送強度の増分が発生してスコアが下がる」という遷移が発生していた

  • 変更後だと、「選んだ住民$${X}$$に放送を届けていた放送局$${Y}$$にとって最も遠い住民だった。そのため住人$${X}$$に放送を届けるのを放送局$${Y}$$から放送局$${Y'}$$に変更することで放送局$${Y}$$の出力強度を下げることができるため、出力強度現象に伴うスコア上昇があり得る」遷移のみになります。

1イテレーションで有効な遷移になる確率を上げにいった形になります。

ここまでやって、「ビジュアライザのアニメーション使ったことないや」と気づき、焼きなましが全然収束していないことに気づきます。

484,933,394点解法

焼きなましを改善しようとアルゴリズムを眺めていましたが、温度設定の勘所がアルゴリズムを眺めただけだとわかりそうになかったので一旦山登りで実装し直しました(すぐ後に焼きなましに戻ります)。
ビジュアライザを見た感じだと$${2, 300}$$msec程度で収束します。本番52位相当になります。

496,173,125点解法

ようやく「スコアが悪くなった量を考慮した」焼きなましを導入しました。本番6位相当。

ひとまずビジュアライザを見ながら自身の感覚を信じて開始時と終了時の温度を決めたものがこの提出になります。
seed0のアニメーションを見た感じだと木の葉寄りの部分はガンガン変わるのですが、終始大きく変わらない部分が存在していて、まだ改善できる感じはあります。
ただ、大きく方針を変えないと難しそうです。

496,410,405点解法

初期解のバグ(458,804,552点解法参照)を修正しました。

解法まとめ

最終的な解法はざっくり言えば「住民$${X}$$には放送局$${Y}$$が必ず放送を届ける、として放送局$${Y}$$を変化させていく焼きなまし」となりました。細かい実装は以下の通りです。

  • 初期解を「住民$${1}$$をから順番に見ていって、$${P_i \leq 5000}$$の条件を満たすように放送局の出力強度のスコア分の増分が少ないように決める」貪欲法とする。

  • 出力強度については1イテレーションが「住民を『住人$${X}$$に放送を届けている放送局$${Y}$$の現在の出力強度$${P_Y}$$が、住人$${X}$$に放送を届けるために最低限必要な出力強度と一致する住民』からランダムに一人選び、その住民$${X}$$に放送を届けられる放送局$${Y}$$をランダムに選んで割り当てる。住民$${X}$$に届けるために必要な出力強度$${P_Y}$$がわかるので、放送局$${Y}$$の放送範囲$${P_Y}$$内にいる住民は全て放送局$${Y}$$が放送を届け、それ以外の住民-放送局ペアは前回のまま」となる焼きなまし

  • 放送局を結ぶ通信ケーブル網については「プリム法で最小全域木を作ろうと試み、使う放送局全てが放送局$${1}$$と連結した段階で構築を終了させる。その後その木の葉で出力強度が$${0}$$の使わない放送局は順々に削除していく」として構築

ちなみに焼きなましのイテレーションの回数はローカルで30,000〜40,000回で、高速化は全くと言っていいほどしていないです。理由はローカルで制限時間を5倍程度にしましたが、スコアはそんなに変わらない印象を受けたためです（細かくは調べてないです）。短期AHCだと、高速化によるスコア改善は現在の自分にはあまりできる気がしていないので、一旦学習の優先度下げています。