[JOI] broadcasting – テレビ放送（2012 年春合宿）

概要

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

JOI の output only の問題です。

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

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

$N$ 個の町を、小さい円 $K$ 個で被覆したいという問題です。近い領域にある町どうしを何となく固めてしまって、各々について最小包含円を求めれば、そこそこ良い解が得られそうです。

「 $R^{d}$ 内の $N$ 個の点を、いい感じに $K$ グループに分けよ」というのはクラスタリングと呼ばれる問題です。「良い解を得る方法」どころか「解の良さをどう定義するか」というところからちょっとふわふわした問題設定ですね。

このクラスタリングという問題についての定跡のひとつに、K平均法というアルゴリズムがあります。「解の良さ」を、各クラスタ中心点との平均 $2$ 乗誤差といった感じで定義して、適当な意味での局所最適解を出力してくれます。

私は Python の、sklearn.cluster.KMeans を使いましたが、K平均法はアルゴリズムがかなり簡単なので、フルスクラッチで書いてもすぐに実装できるはずです。

K平均法により町をクラスタリングして、それぞれのクラスタに対して最小包含円を求めます。最小包含円の中心の座標は一般に整数とは限らないので、前後の格子点を試します。これで、解の候補が作れました。

ところで、K平均法は、あるランダム「初期状態」からの反復によりクラスタリングを行います。ランダム要素があるということは、この方法を反復試行して当たり待ちをするだけで、もっと良い解が手に入る可能性があります。

なんと、この方法で、 $5$ ケース中 $4$ ケースにおいて、 $20$ 点を獲得することができました。のこりのひとつ（[broadcasting2]）は $19$ 点でした。

惜しいことに、ひとつだけ $20$ 点にならなかったので、初期解からの局所改善を試みます。次のようにしました。

「 $1$ 点変更」という近傍を考えることは、とても自然だと思います。また、既にクラスタに対する円の内部に収まっている町については、クラスタを変更しても改善する可能性が全くありません。よって、 $1$ 点変更について自明な枝狩りを入れて、改善パターンを引きやすくしています。

上述の K 平均法で作った初期解から、この山登り法を適用することで、全ケースで $20$ 点を獲得することができました。初期解の時点で満点間際でしたし、実行時間はほとんどかけずに達成できます。

今回の近傍のとり方では山登りをしても大きく結果が改善することはなく、どちらかというと「初期解」の質にかなり左右するように思われました。そこである程度多くの「初期解」を作り、最優秀付近の「初期解」に対してのみ山登り法を試みることで、さらにスコアが上がりました。

ひとつあたり実行時間が数分という感じで調整。

$20$ 点をとるのに必要なスコアよりも、1～2 割くらいは良くなっているっぽい？