こんにちは。Today03 と申します。 今回は AHC020 に参加したので、感想や戦略などを記していきたいと思います。
コンテスト前～開始
前日の ABC の興奮によりなかなか寝付けず、起きたらなんと 14 時 58 分になっていました。飛び起きて PC 起動 & 参加登録。冷静に考えるとアルゴリズムのコンテストと違って 1 分 1 秒を争うようなものではないのでいったん心を落ち着かせながら問題文に目を通しました。
前回参加した AHC016 よりも問題概要は理解しやすかったです。
問題概要
個の放送局 (
) とそれをつなぐ
本の辺、
人の住人 (
) がいます。
住民と放送局の座標、辺の重みが与えられます。
各放送局は
にある放送局と連結でなければ機能しません。
各放送局は「強度(=放送半径)」を設定することにより、一定の半径以内にいる住民に放送を届けることができます。
コストは使う辺の重み、各放送局の強度の 2 乗(=面積)の総和により定められます。
コストが小さいほど得点は大きくなります。また、放送が届かない住民がいると得点は大幅に小さくなります。得点を最大化してください。
正確な記述ではないですが、大体上に書いたような感じです。問題文を見たとき、「あ、これはアルゴリズムの知識である程度戦えそうだ」と感じました。第一印象は以下のような感じです。
第一印象
とりあえず、辺のコストに関しては最小全域木を構築してやればよさそう。
となると鍵は各放送局の強度の決め方になるけど、とりあえず、「各住民が自分と一番距離の近い放送局の放送範囲に収まる」ように決めてみよう。
そんなこんなで実装して提出したコードがこれです。
結果は 411516112 点。この時点で 22 位、橙パフォ相当の得点が出て非常にびっくりしました。
（グラフはこちらのものを使わせていただいております。）
改善 1
ここまでは、各住民について「自分と一番距離の近い放送局の放送範囲に収まる」ように放送局の強度を決めていましたが、これだと無駄があるように感じました。「住民 A は放送局 B と一番近いけど、それより遠くにある放送局 C の放送範囲をちょっとだけ広げればその方が結果的に軽いコストで済むのにな」みたいなケースがあると思ったからです。というわけで、強度の決め方を次のようにしました。（住民ベースの決め方になります）
各住民について「どの放送局に属するか」を次のように決める。
放送局を全探索し、「住民がその放送局の放送範囲に収まるために追加で必要なコスト」が最小になるような放送局を選んで、そこに属するようにする。
そんな感じで実装して提出したコードがこれです。得点は 440108423 点、なんとびっくり、その時点で 10 位に入る得点が取れました。
ここでいったん休憩して順位表を眺めたりコンビニにたけのこの里を買いに行って食べたりしていました。
改善 2
しばらく休憩してから、また改善に取り掛かりました。 先ほどの提出を visualize してみると、次のような感じになっていました。
この画像からわかる通り、明らかに無駄な点が2つあります。
使用していないのに、 (0,0) の放送局と辺でつながっているニート放送局がいる。
円がかぶっている箇所がかなり多い。
前者については (0,0) から DFS をすることによってある程度解決できます。(解説放送では Prim 法を改良したアルゴリズムが紹介されていました。また、Twitterのタイムラインでは「最小シュタイナー木」なるものの考え方を使うとよいという情報がありました。ここに関しては単に DFS するよりもよい解決策があるはずです。)
問題は後者の方で、自分のアルゴリズムの能力ではなかなか改善することができませんでした。
とりあえず DFS した解を提出しました。(これ)
ニートの処理は少なからず効果があったようで、得点は 453993080 点。また少し順位が上昇しました。
改善 3
これ以降は手探りで改善していく状況が続きました。手元でいろいろ試していたはずですが、コードをすべて一つのファイルで管理していたため、記録が残っていませんでした。最終的な提出はこれです。フォーマッタをかけずに提出したので非常に見にくいコードになっております。申し訳ありません。
これまでの方法でいったん各住民が属する放送局を決定した後、次のような貪欲法を回しました。
ある放送局が別の放送局の最遠住民（放送範囲の一番端にいる住民）を奪い取ることを考える。
これにより少しでもコストが減るなら採用、減らないなら無視。
これを念のため時間の限り回すようなコードを実装しました。
少しは効果があったようで、30 位だけ順位が上がりました。得点 462915587 点です。
visualize すると次のような感じでした。かなり地味ですが、細かい部分の円の面積やかぶりが減っています。
コンテスト終了
これ以降もいろいろ試して提出してみましたが、結局改善はできず、コンテスト終了。最終提出の直前に北海道に大きめの地震が来ました。怖かったです。「AHC やめれないんだけどｗｗｗｗ」みたいなツイートをしようかと思いましたがさすがに自重しました。
最終結果
最高得点は 462915587 点で最終順位は 167 位、パフォーマンス 1813 を出すことができました。自分にしてはよくできたと思っています。
いろいろと振り返り
あまりヒューリスティック特有(?)の技術を使えなかったのは心残りな点です。解説放送や感想戦を見た限り、上位勢は山登りや焼きなましなどのランダム性のある探索をしている人が多かったようです。このあたりの知識や技術は復習しつつ身に付けていきたいですね。
今回は初めてしっかり取り組んだ AHC でしたが（過去2回出ていますが、 1 回は参加登録しただけ、もう 1 回は何も分からずほぼ最低ランクの順位をとってしまっていました。）、アルゴの知識もかなり活用できて、とても楽しむことができました。てりーさん、作問ありがとうございました。これからも AHC 楽しんでいきたいと思います。
拙い記事でしたが、最後までご覧くださって本当にありがとうございました。何かの参考になれば幸いです。
