見出し画像

ALGO ARTIS プロコン(AHC020)参加記～algo的アプローチでも意外と伸びるよって話を添えて～

そこらへんのキノコ

はじめに

こんにちは、そこらへんのキノコです。
（twitter: Kinoko_kyoupro  atcoder:Kinoko_Sokora）
二本目の記事です。記事書く書く詐欺をしていたので今回は予告せずに書いてみました。
ちなみにAHCは2回目の参加です。algoは青です。
何をやったかを時系列順に書いてみようと思います。
ちなみにseed=2の例で載せてます
後めんどいから以下常態

①問題文読解

問題文をひととおり読む。全ての住民に届けないとだいぶ減ることを理解。
入力生成方法をみてそっ閉じする。集落とかあるんだすげぇなぁ～の気持ち

問題文要約

家と放送局が$${|x|,|y|<=10000}$$の範囲にある。放送局同士はケーブルで繋がってる（連結無向グラフとして与えられる）放送局1と連結だと放送が可能で、放送範囲は円形で、半径を0~5000の範囲で決められる
ケーブルを使うにはコストがかかる。放送にも半径の二乗のコストがかかる。すべての家に放送をするコストを最小化したい

②自明解作成

とりあえず最小全域木が見えたので書く。強さはめんどいので全部5000で。311M。みんな同じ点数取ってて笑った。

順位表一ページ目に滑り込めて嬉しかったので記念撮影

③放送範囲を減らしていく

なんか計算式見てもよく分からんから直感でやっていく。ついでに焼きなましとかもよくわからんからルールベースでやっていこうと思う。
範囲となる正方形全部を9つの円で覆えばいいんじゃね？となる。だいぶ被ってるし結構高確率で全部覆えるやろの気持ち。
問題文ちゃんと読んでなくて4つで覆おうとしたのは内緒

ざっくりイメージ

この9つの中心座標を埋め込んで最も近い放送局から5000の電波を出す。363M。思ったより伸びない
ここで辺の影響がでかいんじゃね？と思う。今考えるとこれだけでコスト5000^2*9だからそりゃまあ伸びない。
ここまで1時間。そんなかかる？
まあ色々ミスったりなんだりしてたからしょうがないね。

④全ての人に届いてるかチェック

点数を見ると全員に届かせた方が明らかに大きくなるので届けるようにする。入らなくなってるのは少ないと思うので、一番近い放送局から最低限の強さで届くようにする。396M

赤いのが増えたところ

⑤いらない辺を消す

使ってる放送局は一部なので、必要ない辺を消す。木DP的な感じで実装。
412M。400M超えてうれしい。ちなみにいまだに実行時間は13msぐらい。

⑥もっと全体的に円のサイズを小さくしようとする（なんか減った）

円が無駄にでかい気がしたので小さくしようとする。
すべての住民から「今放送してる局の中で一番近い局」を求めて
→その局に距離を送って
→局ごとに送られてきた距離の最大を求めてその大きさに直す
ってやる。411M。なんか減った。

⑦理由の考察

なんでだろう？と思ってdouble型の誤差で必要なサイズよりも小さくなって一部が放送範囲から漏れているのかと思う。いくらか大きくしてみるも特に変わらず。時間は溶けた。

今ビジュアライザ見てみると④のところで追加したやつもまとめて処理したせいで大きくなってるっぽい。（赤いやつ）
大きさが5000の9個に限るべきだった。(改善ポイント①)

⑧乱択要素を入れる

⑦でなんで下がったのかを考えたりなんだりしてたら残り1時間ぐらいになる。ヒューリスティックといえばやはり乱択なので乱択要素を入れたくなる。
でっかい9個の円の位置をずらしていきたいなと思う。
全域木構築以降の「でっかい円を作る→入ってない家を入れる→いらない辺を消す→放送範囲を小さくする」を一セットとして、毎回違う円を作っていきたい。
というわけでループごとにでかい円の中心に選ばれた点を一つランダムにバンしていくことにする。
バグらせたりコードを整理したりしているうちに終了間際。提出は間に合った。442M。

今考えるとバンされた数が多すぎると無駄だから0.25秒ごとにリセットとかしてよかったかもしれない（改善ポイント②）

⑨最終結果＆感想

442.5Mで326位/966　水パフォで入茶
⑦まではヒュールスティックスっぽいアプローチ全くしてないけど412Mぐらいまで伸びているから今回はalgoっぽいアプローチだけでぼちぼちの点数はとれる。
なんなら⑩のところのをやれば432Mまで増える。
TERRYさんの作問力の高さが分かりますね！！！
（「初心者でも手が止まらない」ことを目指したとおっしゃっていた）
今回は問題だけ見ようかなと思っていたけども
全域木が見える→書く→改善ポイントが見える→書く→…
ってやってたら結局4時間フルでやっちまった。時間が溶ける溶ける…
見事にTERRYさんの策にはまっている。
作問ありがとうございました！！！
他の開催に関わった方々もありがとうございした！！楽しかったです！！！

⑩おまけ　改善ポイントをやる

改善ポイント①(⑦のところ）

放送範囲を小さくするところで、住民から大きさが5000のやつだけを対象にするようにする。432M。だいぶ増えるなぁ
（これは乱択してない）

改善ポイント②(⑧のところ)

頂点のバン状況を0.25秒ごとにリセットする。
448M。ぴったり100位順位が上がる（すごい）

改善ポイント①②両方やる

両方やってみる
これやるとき手元でやると入力待ち時間も時間計測に含めちゃって1回も回らないということにだいぶはまった。
結果は…447M。減るんかい。
改善ポイント②だけやるのが最良みたい。5000を基本にしちゃうとでかすぎるのかな...？

最後までお読みいただきありがとうございました！！！
思ったより記事書くの楽しいな。

この記事が気に入ったらサポートをしてみませんか？