鉄則本こと競技プログラミングの鉄則の力試し問題のラストを飾るヒューリスティック型課題、Mayor's Challengeの解説です。100ケースで9693万点くらい出ました。

上級者向け解説ですので、初中級者の方はまず先に公式解説pdfをご一読されることをオススメします。*1 また、まだ解いていない人は是非自力で解いてみてください。ヒューリスティック問題は自力でいろいろ工夫してみる過程がとても楽しいですよ。

競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ)

作者:米田優峻
マイナビ出版

Amazon

問題概要

地区をいい感じに合併して、格差が小さくなるように特別区を作ってね。

atcoder.jp

選挙区割り問題に近いでしょうか。名前は聞いたことがあるのですが、実際に自分で解いてみるのは初めてです。この辺あまり詳しくないので、有識者の方の知見もお待ちしております。

方針

焼きなませるので、焼きなまします。地区ごとの連結性を保ったまま少しずつ特別区の割り当てを変更していきます。

焼きなましの近傍としては、「特別区 $X$ の地区 $x$ を特別区 $Y$ に変更する」「特別区 $X$ の地区 $x$ と特別区 $Y$ の地区 $y$ の割り当てを交換する」の2つを採用しました。2つ目の近傍を入れるかどうかでかなり性能が変わってきた印象です。

解法

前処理

グリッドのままだと扱いづらいので、グラフに変換します。詳しいやり方は公式解説pdfをご参照ください。

評価関数

この問題のスコアはざっくり以下のように決まります。

人口の最も多い特別区と人口の最も少ない特別区の人口比を取る
職員の最も多い特別区と職員の最も少ない特別区の職員比を取る
両者のうち悪い方に定数をかけてスコアとする

このスコアをそのまま焼きなましの評価関数にしても良いのですが、このスコア関数はやや取り扱いづらいです。*2 というのも、人口または職員数が最大・最小となる2つの特別区しかスコアに寄与せず、他の特別区の割り当てを変更してもスコア関数の値が変化しないためです。イメージとしては、スコア関数のあちこちに平坦な領域ができてしまうような感じでしょうか。

このスコア関数が最大となる条件は、各特別区の人口および職員数が全て等しくなることです。そのため、平均人口 $\bar A=\sum_{k=1}^KA_k/L$ および平均職員数 $\bar B=\sum_{k=1}^KB_k/L$ を求め、各特別区の人口 $a_l$ および職員数 $b_l$ について、平均との誤差を小さくしたい気持ちになります。ということで、今回はその誤差の二乗和を使った $f=\sum_{l=1}^L(a_l-\bar A)^2+50^2\times\sum_{l=1}^L(b_l-\bar B)^2$ *3を評価関数として採用することにし、これを最小化することにしました。このようにすることで、評価関数から平坦な領域をなくし、滑らかで焼きなましやすい関数にすることができます。

注意点として、当然ながら生のスコア関数の値と今回作成した評価関数 $f$ の形は異なっています。そのため、

焼きなましの解の更新時に生スコアも計算し、生スコアが最も良い解を別途保持しておく
生のスコア関数と評価関数 $f$ を線形結合し、時間とともに生スコアの重みを増やす

等の対策を行うと良いでしょう。今回は前者のみ採用しました。

初期解作成

焼きなましでは完全なランダム初期解を選んでも良い解が得られることも多いのですが、今回の問題では初期解の良し悪しの影響が結構大きかった印象です。というわけで、ある程度真面目に初期解を作ります。

今回は、

$K$ 個の地区からランダムに $L$ 個を選び、それぞれ特別区 $1, 2, \cdots, L$ に割り当てる
未割り当ての地区 $k$ とそれに隣接する特別区 $l$ の全てのペア $(k, l)$ について、地区 $k$ を特別区 $l$ に割り当てたときに評価関数 $f$ がどれだけ変化するか計算し、最も良かった割り当てを採用する
2.を未割り当ての地区がなくなるまで繰り返す