AtCoder Heuristic Contest 001 備忘録

AtCoder Heuristic Contest 001 の備忘録です。

問題はこちら↓

AtCoder Heuristic Contest 001 - AtCoder

・A問題:AtCoder Ad

まず各 xi+0.5 , yi+0.5 を内包するように 1 * 1 で配置する事を考える。xi , yi が重複することはないので、全ての広告で確実に条件を満たすことができる。これにより、823,090 点を獲得することができる。
次に、各広告の角の座標の xi , yi が数直線上での隣になる値にした。これにより、2,899,766,617 点獲得できた。
次はビジュアライザ上で左上方向に正方形の状態で拡張する。拡張したマスが他の正方形と重複してはいけないので、各広告が設置されている範囲を管理できるように配列を持つ。左上方向に1マスづつ拡張し、増えたマス目に他の広告がなければその範囲を現在見ている広告の範囲として、答えの座標を更新する。ただし、広告の面積が Ri を越えると満足度が下がっていくので、可能な限り満足度が高い状態の時にのみ、答えを更新するようにする。同様に右下方向にも拡張する。これにより 32,466,502,990 点獲得できた(解答例)。
ここまでは正方形の状態で満足度を最大化しようとしていたが、まだ希望する面積に満たない広告も多いので、上下左右方向にそれぞれ範囲を拡張していく。判定方法は上記と同様でよい。これにより 44,123,955,953 点獲得できた。
ここまでは各 xi , yi が原点に近いものから処理していたが、処理する順番を変更することで満足度を上げられないか考える。そこで考えたのが、Ri と S(各広告の面積) がより小さい方が、その差1当たりの満足度の変化が大きいことに注目し、Ri の小さいものから処理することにした。それぞれの範囲の拡張を一から行っても計算時間に余裕があったことから、両方を調べてより満足度の高い答えを選んで出力するようにした。これにより 44,149,135,290　点獲得できた。これが最終的な提出となった。