ながめも

競技プログラミングについて

AtCoder Heuristic Contest 001 AHC001に参加しました

AHC001に参加しました。

結果は、システムテスト前最終118位、489億6千万点でした。簡単にですが、採用したアルゴリズムに関して記します。

アルゴリズム

  1. 各企業の初期位置に1x1の正方形を割り当てる(初期化)
  2. 各企業に長方形を割り当てる。(貪欲)
  3. ランダムに領域を移動し、ランダム要素を追加した貪欲を加え、解がよくなるなら採用する(山登り)
  4. ランダムの中である確率で、1x1の正方形にリセットする摂動を入れる(kick)

初期化

1x1の正方形を割り当てます

貪欲な長方形

まず、x, yともに両方向に同じ距離ずつ広げる正方形を割り当て、その後x, yそれぞれに関して乱数を用いてランダムに伸ばす方向を設定し割り当てる。面積は、目標を超えないように、また他の長方形と交差しないように貪欲に割り当てる。

ランダム山登り

ランダムに長方形を選び、3 ~ 200だけ移動させる。方向もランダム。これを20回繰り返す。

kick

20%の確率で、長方形をリセットする。状態を壊して局所解に落ちないようにするため。

パラメータ

パラメータは勘で選んだ。本当は検証するべき。いくつか試して、解の上昇が最もよさそうなのを採用した。

実装

貪欲の実装は、二分探索で行ったが、交差判定でO(N)かかるので、全体でO(NlogH)かかる。logがついて遅い。高速化するには、Dynamic AABB Treeというものを用いるといいらしいです。

何が最も改善に効いたか

  • 貪欲時にランダム要素を含ませたこと
  • kick(長方形リセット)

貪欲は決定的なアルゴリズムになってしまいがちなので、その中にもランダム要素を生やすことで、局所解から脱出しやすくなると思います。また、kickも同様で、長方形の辺の比が偏ってる場合他を邪魔する可能性があるので、高確率でリセットを行うようにしました。

改善したい点

  • Dynamic AABB Treeで交差判定を高速化する
  • パラメータを勘で設定しない

コード

提出へのリンク