AHC001参戦記

随分と時間が経ってしまいましたが、AHC001に参加した記録を書いていこうと思います。

マラソン型のコンテストは何度か参加しましたが、改善の案はあってもコードが書けなくて諦める。ということが多かったです。
今回もそうなるかな。と思いつつも、とりあえずやってみようと思い、はじめてみました。

ビジュアライザは用意していただいているものの、Rustだということもあり、ちょっと面倒くさいな。と思っていたところ、kenkooooさんがwebサイトで見れるようにしていただいたのはありがたかったです。

この記事の中で出てくるビジュアライザはkenkooooさんが公開してくれたサイトをキャプチャしたものです。
また、断りがない限り、入力例1の入力で出力した結果を掲載しています。

なお、私は、AtCoderのアルゴリズムのレートは茶色下位から中位くらいで、ABCのCが解けなかったり稀にDが解けたりする程度の実力です。
使用言語はPython3です。

問題概要
Day1
Day2
Day3
Day4
Day5
Day6
Day7
Day8
システムテスト
感想

問題概要

大雑把に書くと以下のような感じです。

10000×10000のエリアに広告をN個作る。
各広告には、希望位置と希望面積がある。希望する位置を含む広告で、希望面積に近いほど満足度が高い。
満足度が高くなるような各広告の位置を決めてください。

Day1

この日は問題だけ見て終わりました。

Day2

まずは正の得点を得られるようにすることから始めました。
希望位置に最小のサイズの広告を作成して出力します。

これで得点は823090 / 50000000000 です。
何とかして広告サイズを大きくできないかを考えながら眠りにつきました。

Day3

広告の希望位置は被らないことがわかったので、希望位置の高さが同じ組がなければ「広告を横に伸ばしてみよう。」と考えました。

得点は、4246856211 / 50000000000 とぐんっと伸びました！

しかし、高さがないので、高さを出せるようにコードを書いていきます。
実際、自分が広告主ならこんな広告枠だったら怒りますしね。(笑)
この高さを出すのが結構苦労しました。i番目の広告主の情報をもとに、高さでソートした情報も組み合わせた値を取得するのが難しかったです。
出来上がったコードから出力した結果はこんな感じ。

なんか広告枠っぽい感じが出てきたんじゃないでしょうか！？
得点も 27355084645 / 50000000000 と、さらに大幅に更新しました！
依然、線のような広告枠が多いのも気になりますが、とりあえず高さが出せたので良しとします。

次は横縞模様じゃなくて、縦縞模様の広告にしたらどうかな？と考えて、高さを幅に変えてみます。

得点は、27266837345 / 50000000000 大体同じですが、ちょっと下がりました。

与えられた入力によって、横長の広告にするほうが満足度が高いか、縦長の広告にするほうが満足度が高いかがわかれるように考えました。
縦と横のそれぞれのパターンの満足度を計算しておき、満足度が高いほうを出力するようにすると、得点は、28137530735 / 50000000000 前回よりも少し上がりました。

入力によって縦長の広告と横長の広告のどちらが好ましいかがわかれる。ということから、広告の枠全体ではなく、この枠を上で２つ、下で1つの計３つに区切って、それぞれで各広告を縦に作るか、横に作るかを決めていくようにしました。
おまけで、各広告枠の最後にあまりがあるのがもったいないので、枠の最後に近い広告は、枠いっぱいまで広げるように改造しました。

得点は、28054549870 / 50000000000 です。
あれ？おかしいな。。。点数下がってしまいました。

ここでようやく、広告が希望面積よりも大きくてもダメなことに気づきました。(遅い。
上で書いた、おまけ部分が蛇足でした。
おまけ部分を削除して提出しました。

得点は、29640600949 / 50000000000 です。今までの自己ベストを更新しました。

Day4

これまでに気づいたことは以下のようなことです。

広告サイズは大きすぎても小さくてもダメ。
広告枠全部で考えるのではなく、区切ったほうが得点が高くなることが多い。
実行時間は結構余裕ある。

広告サイズは大きい場合は、削る処理を書きました。
広告サイズが希望面積の2倍以上の場合、高さ/幅を半分にしても得点が得られるなら、半分にしていくという処理を追加します。

得点は、37660314623 / 50000000000 となり、大幅に点数アップしました。

次に、広告枠の分割を考えます。今までは左上、右上、下半分という分け方をしていましたが、4分割することを考えます。
また、4分割する中心点のx座標とy座標を二重のfor文でそれぞれ500ずつ移動させながら計算していき、一番スコアの良いものを出力するようにします。
入力例だとわかりにくいので、seed1の例だとこのような感じで区切ります。
点線が区切り線です。

得点は、39261523429 / 50000000000 となり、記録更新です！

ここでもう一度サイズの適正化を考えます。
今まではサイズが半分にできれば半分にしていきましたが、希望面積と現在の広告サイズがわかっているため、幅を削って希望面積になるように調整していきます。縦長広告の場合は、高さを削っていきます。

得点は、40638942348 / 50000000000 となり、ついに40,000,000,000に乗りました！

Day5

この日は、終日、今まで書いたプログラムのリファクタリングをしていました。

コードが散らかっていて、コードの修正がつらくなってきたからです。

docstringも書きましたが、そこまでやる必要はなかった気もします。そのような気もしますが、これを書いたから後にコードが書きやすくなった気もします。
実際にdocstringに助けられたというよりも、いつ、どのような目的で、どのような変数を扱うのかをdocstringを書きながら整理したために、コードや変数が頭に入っていった。という意味合いが大きかったように思います。

Day6

広告エリアを4分割にして、それぞれのエリアで最適な各広告サイズを決定していくのがうまくいったので、そのパターンを増やしていこうと考えました。

今までは機械的に、区切る座標はx,yともに500の倍数でしたが、入力で受け取った値を利用してみることにします。

試行回数が増えれば、得点は上がると考え提出しました。

得点は、41015056178 / 50000000000 となり、少し上がっています。

ここで、今までは、横長の広告に対して、幅から調整していたのですが、高さから調整するように変更しました。空いたスペースに直近で、希望面積に至っていない広告のエリアを拡大させようとしました。
矢印を付けた部分が今回処理を追加して面積が拡大した部分です。

得点は、44325415664 / 50000000000 点となり、順調に改善を重ねられているように思えます。

Day7

実行時間に余裕があること、また、PyPy3に変更してもPython3と同じコードで動くのであれば、より計算量を増やせることに気づき、PyPy3へ変更しました。
これにより計算量を増やせるため、広告枠の区切りのパターンを増やしてみたいと思います。今度は左上と左下、真ん中と、右上、右下という5つに区切ります。使用するのは、広告希望の位置2つを使用して、区切るx,y座標を200組ほど生成しています。