マラソン初心者のAHC001参加記
つい先日終了したAHC001に参加しましたので、参加記を書きます。AtCoderで初めてレーティング対象のヒューリスティック型のコンテストでした。最終順位は881位で764,972,517,923点でした。（暫定順位は869位で39,273,784,564点）山登り法や焼き鈍しはできていないので、伸び代はあると信じています。いろいろがんばった記録です。
他のつよつよ競プロerの方の記事がちょっと辛いよ、ムズイよって方向けに参考になれば幸いです。
問題
大きい広告スペースにたくさん企業から広告掲示依頼が来るので位置や大きさ
の要求をできるだけ叶えてあげるような掲示方法を探します。
思考過程
点数が低い方から解法を挙げていきます。
1. 一番簡単解法
823,090点
コメント
とりあえず点数が欲しい、早めに順位表に乗りたい大体の人が通していた方法。
来た広告依頼に対して、の正方形の広告を出す方法。制約上、広告が被ることはないので一番簡単に思いつく方法ですね。めっちゃちっちゃい広告を出してあげます。これは企業からクレームが来そうですね。
2. 縦細長広告
27,266,837,345点
広告版を縦に区切って、その区間に細長広告を出す方法。広告依頼をの値でソートし、順番に横幅を決めていく。
注意点
の値が同じ場合は
の正方形の広告にする。（これはよくないけど、とりあえず提出するため）
3. 縦横細長広告
28,147,006,780点
基本の考え方は2と同じだけど、横にも同じことをして縦と比較して点数の稼げる方を採用。ここでコスト関数（スコア計算用の関数）を実装。
マラソンコンテストはコスト関数の実装絶対いるのはわかってるけど、最初はやる気が起きないです笑
長いのでとりあえず低めの点数取ってアップが終わってから実装したいお気持ち。
4. 縦横細長広告 改良ver
28,346,239,854点
3の解法のや
の同じ値が来るときの広告の形を
から長方形の短冊状に変更。微増ですね。
5. 縦横細長広告 広告のサイズ最適化
39,273,784,564点
ここで大幅に点数が上がります。スコア関数を作って一つ一つの広告の満足度を見ていたところ依頼サイズの小さい広告であれば、広告のサイズを小さくしていくことで満足度が上がることに気づきました。（遅い！！）面積に応じて広告の長さを変化させます。小さいサイズの広告であれば満足度100％に簡単にできます。が、しかし、この細長形状でやっているせいで、面積を小さくする方にしか最適化できません。
見た目はこんな感じ
ここまでで終了でした。もうちょっとうまくやれば400億点台にも乗せれそうでしたが、その後の伸びがイマイチそうです。
簡単な工夫でここまではなんとかなります。おそらく誰でも到達できるのでは？
解法5のソースコードです。REしてるのがいくつかあってこれが最終順位がちょっと落ちた原因ですね
最後に
つよつよな方々が素晴らしい参加記を書いているので恐縮ですが、弱いなりに色々まとめてみました。つよつよな方々はエンジニアとしても素晴らしく、TypeScriptとかで自作ビジュアライザを作っている方もいらして、マラソンの世界の深淵を覗き込んでしまった気分です。山登りや焼き鈍しはAHC002までになんとかがんばって勉強したいと思います。
