# AHC001 参加記 ## 3/6 - とりあえず正の得点を得るために(x[i], y[i], x[i]+1, y[i]+1)を提出。**823,090点** - 次に、上下左右4方向についてその方向に最も近い点との中間地点まで伸ばすみたいなコードを提出。**3,351,527,140点** - ここからさらにランダムに点と方向を選択してその長方形を伸ばすコードを書いて**4,373,187,337点** - 上位陣と10倍ぐらいスコアが違うので、もう少しちゃんと考察したほうがいい - 今こんな感じ ![](https://i.imgur.com/bPB8SlH.png) - ビジュアライザを見るとスッカスカ... - どうして??? ランダムに時間いっぱい伸ばすコードを書いてるんだからもうちょい伸びてもいいような... - とりあえず自明な高速化をした 投げたが駄目 - 自明なバグを発見した。(overlap判定でi == idをcontinueしてなかった)しかし手元だとなぜかoverlap判定に失敗してるので TODO:後で直す(たぶんis_overlap()がバグっている) - これ成功したら結構点が伸びそう - バグみつけた - 直した - 伸びた!**34,338,729,388点**!!! ## 3/7 - ビジュアライザの実装にoverlap判定関数があることに気づいた。読むと、幾何ライブラリ使わなくてもめっちゃ簡潔かつ定数倍の軽い実装ができることに気づいた。パクって書き換えると**45,037,988,795点**になった。やった~~~ - 今こんな感じ ![](https://i.imgur.com/rFHyMAR.png) - ちょっと手元で動かした感じとこの画像を見ると、乱択を時間精一杯までやるのはあんまり意味がなくて、割と早い段階で広告がギチギチになる。(つまりすぐ収束してしまう) - つまり割と根本的な改善が必要。小手先の高速化はもうあんまり意味がないな - 今の上の方の順位表がこれなんだけど、この問題満点が50,000,000,000点だから49,000,000,000点台ってほぼ正解みたいなものでは... ![](https://i.imgur.com/dXte6po.png) - 今のコードはランダムに広告を選択して、上下左右どの方向に伸ばすかを乱択して、伸ばせるなら伸ばすコード(ただしもう既に面積がr[i]以上なら伸ばしても意味がないのでcontinueする) - どうせみんな同じことやってる気がするなぁ、もうすこしアルゴリズム的に改善したい - 各広告の満足度の計算は$1 - (1 - min(r_i, s_i) / max(r_i, s_i))^2$で行われる。ということは面積の小さい広告を優先的に選択した方が得。 - 面積の大きい広告から選択したほうがいいかも、面積が大きい広告の方が満足度を高くするのが難しいので - r[i] - s[i]の大きいものから選択するのもあり - 優先度を付けて乱択するには選択確率を決めて、累積和を取って二分探索するのがいいらしい - スコア下がった だめそう... - あと、差を二乗したものを1から引くということはr[i]以上を目指さずある程度妥協しても割と満点近くなるかもな。例えば1 - (1 - 0.9)^2 = 0.99とかだし... - これ多分局所最適解に陥ってるから焼きなまし的なことがしたいけど、どうやってやるんだろう... ## 3/14 - いろいろ忙しくてこの日まで手を付けられていなかった。 - 一応、これ以上どの広告も伸ばせなくなったらランダムに広告を選んでリセット((x[i], y[i], x[i]+1, y[i]+1)にする)してみて、また再度ランダムに伸ばしてみる、ということをしてみたがスコアは伸びなかった。 - [最終提出](https://atcoder.jp/contests/ahc001/submissions/20919214) ## 感想 初日でパッと思いついたのを実装したら、結局そこからスコアが伸びずに終わってしまった。 手詰まりになってどうしたらいいのかわからなくなってしまったので、そういう時にどうすればいいのか知見が欲しいと思った(アルゴならこういう時はこうだったりしないか?みたいなのがある程度あるけどマラソンはどうしたらいいか分からない、みたいな) フローっぽいなぁと思ったりもしたが、知識がなくてよく分からず(こういう風に上手いこと配置できるか?みたいな問題はフローっぽい気がするが、制約条件が複雑すぎるので違うのかも) 49G点台の人たちは何をしているんだろう、とても気になります。