[JOI] election 選挙 （2008 年春合宿）

概要

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

JOI の output only の問題です。

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

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

解法

山登り法

次の山登り法により、全問題の $20$ 点が得られました。

• 適当な $M$ 個の町を選んで、初期状態とする。
• 選択中のランダムな町を外して、未選択のランダムな町を使ってみる。スコアが悪くならなかったら採用する

「election 1, 2, 3, 4」では初期状態 $\{1,2,\dots ,M\}$ から始めて $20$ 点が出ました。

「election 5」のみ、

• 山登り法において、ある程度のステップ数改善が見られなければ、打ち切る。
• 新しい初期状態をランダムに作り、山登り法を再開する。

としました。$M$ が小さく、局所最適解に陥りやすいようです。

スコア更新の高速化

工夫なしに毎回スコアを計算しなおすと、山登り法の 1 試行に対して、$O(N^2)$ 時間の計算量が必要です。次の要領で、スコアの増減のみ計算するようにすれば、$O(N)$ 時間でスコアが更新できます。

• 各町がいくつの円でおおわれているかのカウンタを持つ。
• 山登り法のステップでは、$1$ つの円を消し、$1$ つの円を書き込むことになる。これに合わせて合計 $O(N)$ 回、カウンタを増減させる。
• カウンタが $0$, $1$ の境界をまたぐときにのみ、スコアの増減が生じる。

結果

どのケースも、手元計算時間 $10$ 分かからないくらいで、$20$ 点スコアが得られています。$20$ 点スコアが出たらそれ以上計算していないので、また伸びる余地はあると思います。

• [election1] 78100
• [election2] 32203804
• [election3] 50522701
• [election4] 49860631
• [election5] 42626365

コメント

Heuristic contest は本当に初心者で、初めて山登り法を実装しきった感じでしたが、ちゃんとスコアが出てくれてよかったです。

おそらく古い問題ということで、参加者にとってもノウハウの蓄積が少ない時代だったと思うので、$20$ 点の基準が最近のよりも低めなのかな？まだ詰められる要素はあるのでしょうが、満点がもらえると嬉しくなりますね。