AHC001

　こんばんは。島崎翔です。AHC001に参加したので記録をしておきます。括弧内の点数は暫定順位付け用の入力での点数です。

問題［A - AtCoder Ad］

　「$10000×10000$のマス目の中に格子点を頂点とする$n$個の長方形を重ならないように配置する。その際（$1 \leq i \leq n$として）$i$番目の長方形が内部に点$(x_{i}+0.5,y_{i}+0.5)$を含んだうえで面積が$r_{i}$に近ければ近いほど点数が高い。」みたいな感じです。

解法1（$8e5$点程度）

　とりあえず$k$番目の長方形を$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$の$4$点を頂点とする面積$1$の正方形として出力しました。全ての$i \neq j$に対し$(x_{i},y_{i})\neq(x_{j},y_{j})$であることは保証されているので、この出力では$1$番目から$n$番目までの全ての長方形が重ならずに内部に点$(x_{i}+0.5,y_{i}+0.5)$を含むのである程度の点数が得られます。
　この提出で暫定順位付け用の入力から得られる点数は$823090$点で、私が提出した時点では同点の方がそこそこな人数いらっしゃったので割と初めに試す解法なのかなと思いました。

解法2（$3e6$点程度）

　前述の解法1の処理に加えて、$4$点$(x_{k},y_{k}),(x_{k}+2,y_{k}),(x_{k},y_{k}+2),(x_{k}+2,y_{k}+2)$が$10000×10000$の領域内に収まり他の長方形と重なりもしない場合には$k$番目の長方形を前述の$4$点を頂点とする面積$4$の正方形とする処理をしました。
　ほとんどの長方形で面積が$4$倍になったので点数も解法1と比べてけっこう伸びました。

解法3（$7e6$点程度）

　前述の解法2の処理に加えて、$4$点$(x_{k}-1,y_{k}-1),(x_{k}+2,y_{k}-1),(x_{k}-1,y_{k}+2),(x_{k}+2,y_{k}+2)$が$10000×10000$の領域内に収まり他の長方形と重なりもしない場合には$k$番目の長方形を前述の$4$点を頂点とする面積$9$の正方形とする処理をしました。
　ほとんどの長方形で面積が更に$2$倍以上になったので点数も解法2よりも更に伸びました。正直な話ここまでは慣らしですね。

解法4（$4.18e10$点程度）

　前述の解法をベースにしながら本格的に$k$番目の長方形の面積を$r_{k}$に近付けるようにしました
　まず初期配置として$k$番目の長方形の$4$頂点は$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$に設定します。次に$n$個の長方形のなかで$10000×10000$のマス目の外周に接していないものについて、乱数を発生させてランダムに$4$方向のうちから$1$方向を選んで長方形をその方向に伸ばす、という処理をしました。

解法5（最終提出・$4.52e10$点程度）

　前述の解法をベースにしながら本格的に$k$番目の長方形の面積を$r_{k}$に近付けるようにしました
　まず初期配置として$k$番目の長方形の$4$頂点は$(x_{k},y_{k}),(x_{k}+1,y_{k}),(x_{k},y_{k}+1),(x_{k}+1,y_{k}+1)$に設定します。次に$n$個の長方形のなかで$10000×10000$のマス目の外周に接していないものについて、乱数を発生させてランダムに$4$方向のうちから$1$方向を選んでその先に他の長方形が無ければその方向に伸ばす、という処理をしました。

結果・感想

　初めてのヒューリスティックコンテストでしたが参加していてとても楽しかったです。しかし割と単純な方法を実装してある程度の点数を出した後、細かい工夫をしたものの点数が伸びなかったのが悔しいところではあります。また次回も参加してみたいです

　長いコンテストは時間を決めて取り組まないと延々続けてしまいますね。今日はこれで終わります。