- 0.はじめに
- 1.問題の概要
- 2.放送局1のみを使用し、出力強度を最大にする
- 3.全部のケーブルをつなぎ全部の放送局の出力を最大にする
- 4.複数の放送局から受信している家を調べ、電波強度を下げていく
- 5.電波強度が0の辺を削除する（迷走中）
- 6.電波強度が0の辺を削除し、放送局1とつながっていないときは再度辺をつなぐ（迷走中）
- 7.全部のケーブルのつなぎ方を最小全域木にする
- 8.その先に出力が0より大きい放送局がない不要なケーブルを削除する
- 9.出力強度を山登りで決定する（迷走中）
- 10.chokudaiさんに質問してみました（見てほしいところ！）
- 11.放送局の出力強度を山登りできた！
- 12.山登りの改善
- 13.ケーブルの改善
- 14.初期解の改善。
- 15.終わりに
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴3年半のかえでです。
先日、ALGO ARTIS プログラミングコンテスト2023（AtCoder Heuristic Contest 020）に参加しました。開催期間は2023年6月11日(日)15:00から19:00までの4時間、短期コンテストでした。結果は994人中802位。何もできずに終わってしまったなあと残念に思っているところです。
seed0のビジュアライザはこんな感じです。
問題の説明をしていないので、きれいな絵だなあと思うかもしれませんが、最後まで読んでいただければ、改善する点がたくさんあるとわかると思います。
4時間という長さをどう思うでしょうか。通常は時間はたくさんあると思うのかもしれません。でもコンテストのときは、あれこれと試したり、実装をバグらせたりしているうちに、あっという間に過ぎてしまいました。というわけで、コンテスト中に難しく感じた点を振り返りながら、復習を始めたいと思います。
1.問題の概要
- 放送局N頂点、通信ケーブルM辺およびコスト、各住民の家の座標K個が与えられる。
- 座標（0,0）の放送局1（AtCoderオフィス）から生放送を行う。
- 放送局1、および放送局1と通信ケーブルがつながった放送局からは放送用電波を発信できる。
- 通信ケーブルM辺はON、OFFができる。ONにするとコストが発生する。
- 放送用電波は0以上5000以下の出力強度を自由に設定できる。
- 放送局から設定された出力強度とユークリッド距離以内にある住民は、放送局1もしくは放送局1とONになった通信ケーブルで繋がっている場合、視聴可能になる。（つながっていない場合はコストのみが発生する。）
- 放送用電波の発信には出力強度の2乗のコストが発生する。
- 全ての家に放送用電波が届くようにすること、通信ケーブルの使用コストと放送用電波の発信のコストを抑えた放送網を構築することを目指す。
- コストの総和をSとすると以下の得点が得られる。
（問題文より引用）
2.放送局1のみを使用し、出力強度を最大にする
問題文を読んだだけではわからないので、ビジュアライザを使用します。放送局1の出力強度を最大の5000に設定し、ケーブルの使用は0にします。
これを提出すると得点 84,929,009を得ることができます。
白丸が視聴できない家、黄色の丸が視聴できる家なので、全ての丸を黄色にすることを目指します。
3.全部のケーブルをつなぎ全部の放送局の出力を最大にする
全員が見られないと極端にスコアが下がるので、全員が必ず見られる状態を考えます。全部のケーブルを使用し、全部の放送局を最大出力強度にします。これを提出すると得点 309,165,227を得ることができます。
4.複数の放送局から受信している家を調べ、電波強度を下げていく
現在各放送局の電波強度を最大の5000にしているので、これをできるだけ下げます。
各放送局には、放送局から近い家とその距離をペアで持ち、距離が近い順にソートします。各家ごとに、何個の放送局からの電波を受信しているかをカウントします。
電波強度はその放送局の電波が届かなくても見られるかどうか（複数の放送局がカウントされているかどうか）で決定します。
各放送局から重なりが少なくなったので、青色が薄くなりました。
5.電波強度が0の辺を削除する（迷走中）
両方の端点の電波強度が0の辺を削除します。放送局1とつながっていない頂点ができたためにスコアが下がってしまいました。
6.電波強度が0の辺を削除し、放送局1とつながっていないときは再度辺をつなぐ（迷走中）
放送局1となぎます。
7.全部のケーブルのつなぎ方を最小全域木にする
6のやり方がイマイチだと思ったので、最小全域木にしてみます。プリム法を使いました。
8.その先に出力が0より大きい放送局がない不要なケーブルを削除する
余計な頂点があるので、いらない辺を削除します。出力強度が0の頂点を含む辺があったとき、その辺を削除します。削除しても放送局1と残りの全ての頂点が連結されているなら、辺を削除することにします。
提出をします。得点は415,767,169でした。これは本番571位相当になります。
9.出力強度を山登りで決定する（迷走中）
4.の電波強度を変えることにします。各家の電波を受信できる放送局数を見ます。今は2や3の家が複数あるので、できるだけ多くの家が1になるようにしたいと思います。
seed0のビジュアライザを見ながら、重なりの多そうな放送局81の電波強度を0にしてみます。すると、電波が届かない家が2つ現れました。
いちばん近い放送局の電波強度を変更して、それぞれの家が電波を受け取れるように修正してみたいと思います（青い円を追加する）。
これを時間いっぱい繰り返し、山登りをしてみます。最後に最小全域木を作り、余計な頂点と辺を削除します。
＜やることの手順＞
・各放送局の電波を受け取る家の「受け取ることのできる放送局のカウント」を降順に並び替え、複数のカウントがある家の数が多い放送局を選択する。
・出力強度を複数カウントが現れるところで0にする。
・電波が届かない家の最寄りの放送局の電波強度を修正。
・各家の「受け取ることのできる放送局のカウント」を更新する。
上記の手順でやってみたのですが、ループは2回しか回らないし、消してほしいという放送局を0にできないので、とりあえずビジュアライザで挙動を確認するために直接放送局81を指定して出力を0にします。
うん、イメージ通りにはなっています。選ぶところをカウントではなく、もうちょっと良い指標にしたいものです。重なり具合を表すにはどうしたらよいのかな…。
割合にしてみよう。
家が9割複数の放送局から受信できるとき、放送局の電波を0にします。0になった家は、近い放送局から受信するようにします。制限時間内に1、2個しか変えられないのですが、それでも少しスコアがアップしました。
うーん、ゴチャゴチャして訳が分からなくなってしまいました。
10.chokudaiさんに質問してみました（見てほしいところ！）
「4.複数の放送局から受信している家を調べ、電波強度を下げていく」の時点で、一回質問をしていました。しかし、思ったようにいきません。そこで出社時にもう一度chokudaiさんに質問をしました。説明がとてもわかりやすかったので、共有したいと思います。
- どんなデータ構造を持てば良いのか
必要なデータ構造 - 複数の放送局が重なったときどうすればよいのか
１．ランダムに放送局を選び、電波強度を上げる
図では放送局１の出力強度を上げます。現在のBより大きい境界はE、Dどちらかになり、ランダムでEを選択した状態です。
２．カウントを更新する
放送局２では、CFEのカウントがそれぞれ２になりました。
３．他のすべての放送局を調べ、出力が下げられたら下げる
放送局２では、CFEのカウントが２になったので、Dのところまで電波強度を下げることができます。（外側から調べてカウントが２以上ある家は出力を下げられる）
４．スコアが良くなっていれば採用する（山登り）
この方法の利点は大きく２つあります。
一つはどこの放送局からも電波を受信できない家が発生しないこと。もう一つは、放送局の電波強度を0から5000の間からランダムに選ぶのではなく、放送局から各家までの距離を選択することで効率が良くなることです。
また他にもこんなアドバイスをもらいました。
11.放送局の出力強度を山登りできた！
やることはわかったものの、バグらせ続けること3日。やっと修正できました。山登りの回数は4～10万回ほど。seed0のスコアは1561731になりました（ランダムなので毎回違う結果が出ます）。
100テストケースの結果も良くなっていたので提出をします。しかし、提出した結果は421496877点でした。
あれ？
100テストケースを実行させた結果を見るとバグらせているケースがあったので確認します。ダメな原因は境界部分にある家がカバーされていないことでした。最初の頃から距離の計算と一致しないので、ぎりぎりの家を作らないように修正しました。もう一度提出します。
ついに、上がりました！
得点は475,940,607点になり、コンテスト中だったら92位くらいの得点です。
うれしい。
実行時間を100秒にして、スコアが良くなるかを見ます。
100秒にしてもseed0の結果は良くなりませんでした。
うーん...。
12.山登りの改善
1回に1つの放送局を出力を変更するのではなく、複数の放送局を変更してみる？
- 1回に2つの放送局の出力を変更してみました。
seed0ではほとんど変わらないものの、100テストケースを回した結果は良くなっていました。
- 1回に3つの放送局の出力を変更してみました。
2つの場合とほとんど変わらなかったので、2つ同時に変更することにします。
13.ケーブルの改善
放送局の出力強度の改善はここまでにして、次はケーブルの改善をしたいと思います。つなぐ辺を最小シュタイナー木っぽくできればと思うものの、実装方法がわかりません。
- 最小全域木の重みに放送局の出力が0の端点を持つ辺の場合、1e10を足してみました。
そうすれば、出力0の頂点を含んだ辺が後から使われるのではないかと思ったからです。
seed0のビジュアライザを見ると、使っている辺の数が少なくなったように感じます。スコアも1590226になりました。
提出をすると得点は487,825,637になりました。本番だと36位相当、延長戦順位表でも100位になりました。
14.初期解の改善。
初期解を放送局のID順序ではなく、電波が届く家の数が少ない順に作るようにしてみます。いちばんよかったseed69のスコアは1902014になりました。
提出した結果、得点はついに490,014,907になりました。
ローカルでは5万回ほどでしたが、コードテストでは30万回ほどの試行回数になっていました（なぜ？）。
15.終わりに
コンテストから12日。やっと復習を終了しても良いかなと思えるようになりました。延長順位表では、83位になりました（2023年6月22日現在）。81位には本番で23位だったchokudaiさんがいました。
この頃ABCでもAHCでもCodinGameでも良い結果を残せていなくて自信を喪失していたので、とてもうれしかった！
やっぱりヒューリスティック・コンテストは楽しいなと思います。
次こそコンテストで結果が出せますように。（2023/6/30追記：AHC021もダメでした。）
それでは、この辺で復習記を終了したいと思います。
今回の問題ですが、解説放送もありますので、そちらもぜひご覧ください。
ALGO ARTIS プログラミングコンテスト2023（AHC 020）解説 - YouTube
私ががんばっていたのは30分辺りの説明にあった、これかな（黄色枠内）。
いちばん得点のよかったseed0のビジュアライザも載せておきます。
