[JOI] UFO の飛行場（2011 年春合宿）

概要

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

JOI の output only の問題です。

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

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

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

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

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

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

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

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

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

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

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

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