AHC001参加記
問題設定の整理
10000×10000の正方形に$ 50\leq n \leqq 200個の長方形を配置する。
$ n個の長方形の面積の和は$ 10^8として与えられる。
入力$ (x_i, y_i, r_i)について、任意に配置していたと仮定すると,
$ (x_i+0.5, y_i+0.5)を含んでいなければスコアは$ 0
含んでいる場合、配置した長方形の面積を$ s_iとして$ (1-(1-\frac{\text{min}(r_i, s_i)}{\text{max}(r_i, s_i)})^2) \times 10^9 \div nを追加する
考えたコト1:自明な解を探す
各入力について$ (x_i, y_i, x_i+1, y_i+1)を出力する。これらは重なり合うことなく、自明に成立する解である。
結果として823,090点
考えたコト2:smallな操作の繰り返しに分解できないか
長方形は左上と右下の2点(ないし、対角線上にある2点)の位置が固定されたとき、一意に定まる。
このため、この2点をそれぞれ1ずつ動かすような操作に分割することを考えた。
このとき注意するべきことは広がっていく内に自分以外の長方形と領域を共有してしまう可能性があるということである。
これはどの方向に広がるかを見ることで計算はそこまでフクザツにならない。
大事なことなのに書き忘れていたが、選択するindexの確率の比は面積の比とした。二分探索と合わせてイイカンジに求めた。
この結果として1e6回のランダムウォークをしたところ、31,591,338,419点だった。
考えたコト3:sizeはオーバーしないほうがいい
考えたコト4:相手を縮めた方が得なら凹ませたほうがいい
ここでサイズ制約を考えることにした。1回の拡張操作のあと、大きさが$ r_iより大きいものは再び縮め直すことにした。
また、相手が縮むことで自分が広がり、スコア的にお得なら広げることにした。
先程と同様、1e6回のランダムウォークをしたところ、45,281,071,065点だった。
考えたコト5:極端な配置を出来るようにする
いままでのランダムウォークでは、確率的に考えても基準点を中心にした正方形になることが予想され、実際にビジュアライザを観てもそのようになっているものがおおかった。
そのため、長方形全体を上下左右に$ [0, 50)のランダムな分だけ移動することとした。
イイカンジにループを修正すると、46.89G点になった。
考えたコト6:こんにゃくゼリーってぽよんってするじゃん
上に拡張しようとして詰まったら下に拡張するなど弾力をもたせることにしてみた。
イイカンジにループを修正すると、47.89G点になった。
乱数ガチャを引いて47.92G点まで上げた。
考えても上手く行かなかったこと1:破壊したくないか?
一つの図形を完全に破壊したりしたが、結局いびつな図形が生まれるだけだった。
隣り合う2つの図形を破壊した後卍イイカンジ卍に配置する方法があるらしいが、そこまで当然思いつかないのでこの方法は取らなかった。
考えても上手く行かなかったこと2:焼きなましっていうのがあるらしい
序盤に冒険して終盤に手堅くいくやつ。
ただ適切にスコア関数を配置することができなかった。結局ただの山登りになったのでNG
考えたけど手が動かなかったこと1:広がる順番を考慮してみる
端係数を導入して端のものは端に伸びやすいようにしてみたらどうだろうかとおもった。
適切に設定すればブレークスルーがあったかもしれない。
総評
たのしかった(こなみ)。アルゴみたいにいそいそとやる必要がなく気が向いた時に好きなだけ考えることが出来たので僕に向いていたのかもしれない。向いているのにこの程度の点数か?って煽られると困るが初参加なので、許して。
48の壁は厚かった。そこそこ悔しいので次回までにそこそこ勉強する必要がありそうですね。