[JOI] UFO の飛行場(2011 年春合宿)

スポンサーリンク

概要

問題文 → ,
公式解説 → なさそう?
自分の提出 → ,  など

JOI の output only の問題です。

Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。また、手元実行でよいため実行時間制限はあまり気にしないでよく、例えば数十分の実行時間を前提とすることもできます。

出力に対する評価方法は、当時参加者による相対評価です。全ケースで、当時参加者ベスト水準である $20$ 点を得られたので、書いておきます。

問題のグラフによる言い換え

グラフの言葉に言い換えると、本問題は、(最大) 独立集合に関する問題と見なすことができます。具体的には、次のようにグラフを構築します。

  • UFO の 左上隅としてありうる場所を、グラフの頂点とする。
  • $2$ 頂点 $v, w$ の間に、同時にそこを左上隅として UFO を配置すると衝突が起きるようなときに、辺を張る。

問題 1, 2

[ufo1], [ufo2] においては、UFO が $1$ マスからなる場合です。この場合には、対応するグラフは二部グラフになります。

二部グラフにおいて、最大独立集合は、最大流問題を利用して、多項式時間で計算できます。例えば、アリ本 p.198 などを参照してください。

この方法により、問題 1, 2 は厳密解を求めることが可能です。

問題 3, 4, 5

貪欲アルゴリズム

最大独立集合問題をそこそこ良い精度で解く方法として、次の貪欲アルゴリズムがあります。

  • 最も次数の頂点を、独立集合の要素として採用する
  • 採用した頂点、およびそれに接続する辺を、グラフから削除する
  • この手順を、グラフが空になるまで繰り返す

次数が等しい頂点は、ランダムな優先度に従って選ぶことにします。貪欲アルゴリズムでも幅が生まれて、実行するたびに少し異なる結果が得られるようになります。

適当な試行回数、貪欲アルゴリズムによる極大独立集合の構成を行って当たり待ちをすると、$5$ ~ $10$ 点程度が得られます。私は「次数昇順」に注目しましたが、「$x$ 座標昇順に見て、置けるならば置く」というような貪欲法も良いかもしれません。

山登りアルゴリズム

ひとつの解を局所的に変形して、良くなったら採用することを繰り返します。「局所的な変形」は次のように定義しました。

  • 適当な大きさの正方形領域に注目する
  • 正方形内で独立集合として採用している頂点を、不採用に戻す
  • その状態の独立集合から、上記の [貪欲アルゴリズム] を用いて、新たな独立集合を得る
  • もとの状態以上のスコアになっていれば、採用する

「大きさ」としては、$10$ 以上 $30$ 未満の整数を乱択してみました。「ひとつの UFO を外す」くらいではインパクトが少ないと思ったため、ある程度まとめて破壊して再生してみました。

結果

どのケースでも、数分で $20$ 点の解が出力されるようになりました。$20$ 点スコアが出たらそれ以上計算していないので、また伸びる余地はあると思います。

  • [ufo3] 542
  • [ufo4] 1370
  • [ufo5] 1159
タイトルとURLをコピーしました