【AtCoder】AHC020に参加してみた！【Heuristic Contest】
Heuristic！ 競プロerの霧しゃまです。
去る2023年6月11日、ALGO ARTIS社の主催によるALGO ARTIS プログラミングコンテスト2023（以下、AHC020）に参加しました。
これはヒューリスティック部門という、最適解を出すことが計算量的に難しい問題に対して、自由なアプローチで最適に近い解を目指す競技部門のコンテストです。
今回は初めてヒューリスティック部門のコンテストに参加してみたので、その様子を書き留めておきたいと思います。
忙しい人向けのまとめ
アルゴリズムの知識を活かしやすい問題でした！
ヒューリスティック特有の手法はこれから勉強します！
今後も気が向いたら参加します！
問題概要
今回参加したAHC020では、4時間で1問に取り組みます。
問題内容を大雑把にまとめます。
座標平面が舞台です
$${K}$$ 人の住民が配置されています（最大$${5000}$$ 人）
$${N = 100}$$ 箇所の放送局があります
放送局同士を結ぶ$${M}$$ 本のケーブルがあります（最大$${300}$$ 本）
ケーブルはそれぞれ使うか使わないかを設定でき、使うケーブルだけを残したときに、放送局$${1}$$ と連結な放送局が利用可能になります
放送局ごとに電波強度$${P_i}$$を$${5000}$$ 以内の整数値で設定でき、利用可能な放送局から半径$${P_i}$$以内にいる住民に電波が届きます
多くの住民に電波を届けるほどスコアが高くなり、すべての住民に電波が届いている場合は、総コストが小さいほどスコアが高くなります
コストは、使うケーブルの重みの総和と、電波強度の二乗和からなります
結果
今回、霧しゃまは$${442,603,243}$$ 点で$${325}$$ 位でした。パフォーマンスで言うと水色レベルです。勝手がわからない初参加でしたが、思いのほか良い成績を取れました。
また、最初に決めた方針のもと、概ねできる限りのことはやって、得点を伸ばせるところまで伸ばすことができました。総じて良い立ち回りができたのではないかと思っています。
この得点は$${300}$$ 個あるテストケースの合計点なので、テストケースごとの平均点を出すと約$${1,475,344}$$ 点になります。
簡単に方針を説明すると、次の通りです。
各住民について、距離$${5000}$$ 以内の放送局をすべて求める
各住民を最寄りの放送局にカバーさせる（放送局ごとに、「その放送局を最寄りとする住民との距離の最大値」を電波強度に設定する）
各住民について、最寄りの放送局以外にその住民をカバーしている放送局があって、そちらに依存することで最寄りの放送局の電波強度を下げることができるところを愚直に探索し、各放送局の電波強度をなるべく下げる
ここまでで電波強度は確定
ケーブルの繋ぎ方は、ランダム性のあるクラスカル法（電波強度$${0}$$ の放送局の周りの辺は、一定確率で採用しない）で、電波強度が$${1}$$ 以上の放送局をすべて連結にした最小全域木に近いものを作る
作ったグラフで、葉が電波強度$${0}$$ の放送局だったら、その放送局のためのケーブルを切る（この操作は再帰的に、できるだけ繰り返す）
上記5.と6.を繰り返し、ケーブルコストの最も小さいものを採用して完成
ちなみにこの得点を取った上記の解法で、サンプルである"seed=0"のケースを解くと、$${1,459,970}$$ 点になるようです。
立ち回りの振り返り
最初の1時間で、じっくり問題文を読みつつ、「正の得点を得る」ことを目指しました。特に注目したのは得点計算の部分です。引用します。
$${10^6}$$ 点が一つの目安になることがわかります。すべての住民に電波を届けない限り、これを超える得点を得ることができません（あまりにコストを掛けすぎると、すべての住民に電波を届けても、$${10^6}$$ 点を下回ることは考えられます）。
ということで、まずは平均$${10^6}$$ 点を超えられるような方針を考えました。「正の得点を得る」だけなら、すべてのケーブルを使って、すべての放送局に強度$${5000}$$ を設定すればよいでしょう。しかし、それでは戦略も何もないので飛ばすことにしました。
とりあえず、住民はすべてカバーする必要があるので、各住民について最も近い放送局と、そこまでの距離を求め、その放送局にはその距離以上の電波強度を設定するようにしました。
また、ケーブルも使う放送局が放送局$${1}$$ と連結になるならばそれ以上はいらないので、まずは最小全域木（アルゴリズム部門では脱初心者くらいのレベルで学ぶアルゴリズムです）ですべての放送局をなるべく小さいコストで連結にするようにしました。
この方法で、いきなり$${411,520,772}$$ 点を取りました。平均$${1,371,736}$$ 点です。最初の目標は達成できました。
ここまで1時間ほど掛かりましたが、順位表を見ると、全く同じ点数の人がたくさんいました。ここまでは、全く同じ方針を取った人も多かったのではないかと思います。
ここからは、もっと良い方針を探すか、この方針をもとに改善するかの選択になりますが、他の方針が思いついていなかったので、改善で攻めることにしました。
しかし、次の1時間はほとんど停滞していました。
まず、最小全域木を作るときに、強度を$${0}$$ にした放送局を無視するようにしてみました。すると、平均$${2.3}$$%くらい点数が下がりました。これでこの方針は戻してしまいましたが、後から見ると、ここで下がったのは放送局$${1}$$ が強度$${0}$$ になっているときも無視してしまっていたからだと思います。
開始から2時間くらいで、住民を最寄り以外の放送局に乗り換えさせるフェーズを導入し、最初と比較して平均$${1.5}$$%くらい点数が上がりました。先に述べた手順の3番に当たるフェーズですが、このときは各住民1回ずつしかやっていませんでした。
ここからペースが上がり始めます。次に手順6を導入すると、また少し伸びました。電波の供給源である放送局$${1}$$ の電波強度が$${0}$$だった場合にケーブルを切断してしまい、大きく点を落とすバグを踏みましたが、すぐに気づくことができました。
次に、手順3を各住民について150周くらい試行するループを導入すると、かなり大きく伸びました。ここで$${4.4}$$ 億を突破しています。最初と比較して、およそ$${7.1}$$%くらいの改善です。
ここからいよいよ、ランダム性を入れることにしました。手順5のところです。使わない放送局の周りの辺を、一定確率で不採用にします。辺の不採用確率のチューニングは、提出制限（提出は5分以上の間を開けなければなりません）があるので詰め切れませんでしたが、とりあえず、$${1/11}$$にして、その後の手順6と合わせて$${10000}$$ 回繰り返したものが最も高い得点を出しました。数字に根拠はありません。強いて言えば勘です。
なお、ランダム性を入れるにあたっては、点数が下がったときにバグを埋め込んでいるかどうかをわかりやすくする目的で、最低保証を入れました。具体的には、繰り返しのうち1回は、ランダム要素を排した最小全域木を流すことにしました。
実装においてはフェーズを明確に分けるようにしました。つまり、あるフェーズを丸ごと入れたり外したりできるように意識しました。これは、フェーズを追加したときに、そのフェーズによる寄与がプラスなのかどうかを評価しやすくするためです。
最終的に点数への寄与が最も高かった改善は、手順3を入れたことです。この操作はヒューリスティックの言葉で言うと、「山登り法」に当たるのではないかと思います。
今回、終盤は手順5以降に力を入れましたが、ここも結局前半の電波強度の決め方に大きく左右されるので、どちらかと言えば電波強度の改善を優先すべきだったと思います。
なんというか、総じて「局所解の局所解」を突き詰めていた感じです。しかし今回はこれでもある程度通用したので、ラッキーだったかもしれません。
感想など
『鉄則本』でヒューリスティックは少し勉強していましたが、実践的な問題に挑戦するのは今回が初めてで、ほとんどぶっつけ本番でした。
今回が特別なのかもしれませんが、意外と最小全域木などのアルゴリズム部門でやっているようなアプローチが有効だったりして、取っ付きやすい問題だったと思います。また、「局所解の局所解」だったとはいえ、できることをできるだけやることができたという意味では満足しています。改善を重ねて、点数が徐々に伸びていくのを見るのは楽しかったです。
中の人はアルゴリズム部門で青コーダーを目指す水コーダーです。普段はアルゴリズム部門の精進などで忙しく、ヒューリスティックにまでは全然手が回りません。ヒューリスティック部門は何週間にも及ぶ長期コンテストもありますが、そちらに参加できるような余裕が出るのはまだ先のことになりそうです。
しかしながら、今回のような4時間の短期コンテストは、時間帯が早いこともあって気軽に参加できました。今月はもう一回短期コンテストが予定されているようなので、気が向いたらそちらにも参加してみたいと思います。
最後になりますが、運営のみなさまありがとうございました！
以上、霧しゃまでした！
この記事が気に入ったらサポートをしてみませんか？