E8さんが出版した『競技プログラミングの鉄則』の中に収録されているMayor's Challengeというマラソンの問題をやってみました。あまり包括的な解説にはなっていなくて、twitterに書きたかったことを書き殴ったような感じです(twitterではネタバレになってしまうかと思って...)。

ネタバレだらけなので問題を解いていない人は注意してください。

参考文献など
解法の概要
感想
疑問

参考文献など

自力でやった時には91.3M点くらいで、他の人のブログやtwitterを参考にしながら解き直して97.3M点くらいになりました。いきなり参考文献はどうなんだという気はするんですが、最終的な解法は他の方のものをだいぶ参考にしたので先に出典を書いておきます。

terryさんの解説とtwitter

www.terry-u16.net 2つの特別区の間で1つずつ区を出し合って交換する近傍を参考にしました。

最初にやった時にこの近傍を実装しようとは思いませんでした。この操作は区を移籍させる操作2回で実現できるからいらないだろ、と考えたためです。

しかしこの考えは良くなくて、terryさんの解説にあるように中間状態(1個の区だけが移った状態)ではエネルギーの高い状態になるので、区を交換する状況がなかなか実現しません。

ダイレクトに区を交換することで、 tsukammoさんの記事の絵のような感じにできているという理解をしています。勉強になりました。

また、tomerunさんの解法由来とのことですが、焼きなましの近傍操作をする際に、先にスコアとacceptされるかの判定だけをして、その近傍操作が有効かどうかを調べる処理は後回しにする工夫も有効でした。体感で2割くらい遷移が増えた気がします。

鉄則本マラソン、97.2Mに乗りました pic.twitter.com/FxxGv61Xuq
— TERRY (@terry_u16) 2022年10月12日

発想はこちらの記事に近いのかなという気がします(こっちは評価関数の打ち切りだけど...)。 qiita.com

tomerunさんのブログ

特別区に所属している区をランダムで選択して削除したり追加する、みたいな操作が多かったので、このデータ構造がとても役に立ちました。

takumiさんの解説

fusetter.com terryさんの解説で『今回の問題では初期解の良し悪しの影響が結構大きかった印象です』という記述があります。 takumiさんの解説ではその問題に対する解決策が示唆されています。僕も(初回に解いた時から)この方針を採って初期解の良し悪しの問題に対応しました。

公式解説

github.com 丁寧に考え方を書いていて参考になります。すごい...

解法の概要

焼きなましです。以下では、

初期解の生成
近傍
評価関数

について書いていきます。

初期解の生成

20の区を選択して、1~20の特別区に一つずつ割り当てる
特別区の中でmin(特別区の人口/市の総人口, 特別区の職員数/市の全職員数)が最小のものを選び、隣接する区でまだ特別区に割り当てられていない区をランダムに選択して特別区に編入する
上の操作を全ての区が特別区に所属するまで繰り返す

これで確か20M点くらいでした。

近傍

3つの近傍を作りました

(1) ランダムに区を選択して、その区を隣接する特別区に移籍させる。この時に元にいた特別区の連結性を壊さないようにする。
(2) ランダムに区を選択して、その区を隣接する特別区に移籍させる。元にいた特別区の連結性が壊れてしまう時には、最大の連結成分を除いて全部まとめて移籍させる。
(3) 二つの隣接する特別区を選択して、それぞれ一つずつ区を相手に移籍させる(区を交換する)

(1), (3)はterryさんの解説の近傍1, 2と同じです(詳細は割愛)。

(2)の近傍は以下のような問題に対応するために作りました:

赤の特別区から青の特別区に区を移籍させると、元いた赤の特別区の連結性がなくなってしまいます。このような事態を避けるために、近傍(1), (3)では特別区の連結性が壊れてしまうような区が選択された時には近傍操作を失敗させています。

一方で、下の図のように、(1), (3)だけでは特別区を大きくしにくい状況が生じ得ます。

ベージュ色の特別区を広げるにはピンクの特別区から移籍させないといけないが、ピンクの区の連結性を壊してしまう

(2)の近傍はこのような時に有効で、特別区が連結でなくなった時には、最大の連結成分以外を一緒に移籍させるようにしています。

(書いていて自信がなくなってきたのですが)terryさんの解説にあった『今回の問題では初期解の良し悪しの影響が結構大きかった印象です』という記述はこのような状況に起因するのではないかという気がしています。

初期解が適当だと盤面の端のほうでこのような状況が生じてしまい、解消しにくい配置になってしまう
初期回を丁寧に作ると、各特別区は割と均等な大きさになって、他の特別区との接する箇所が増えて、近傍(1), (3)だけでも大丈夫

近傍(2)を入れたことで初期解を雑に作っても大丈夫になったと思っています(信じています...)。

ただし、この近傍は遷移がかなり大きめで、盤面が整ってきた状況ではacceptされる可能性が非常に低いです*1。最初のおよそ10%の時間でだけこの遷移を有効にしました(この割合はoptunaが決めた)。

評価関数

生のスコア + 特別区の人口・職員の数のばらつきに対するペナルティです(スケールを合わせるためにそれぞれの標準偏差を平均値で割って、和をとったものをばらつきのペナルティにしました)。ペナルティは時間と共に線形に減らしていきました。

考え方はterryさんの解説と全く同じです。生のスコアには人口・職員の数が最大・最小の特別区しか寄与しないので、評価関数が平坦な感じになってしまいます。全体として人口・職員の数が均一な方が嬉しいので(多分...)、ばらつきが小さい状況を好むようにしました。

optuna

optunaがとても便利でした。なんでもっと早く使わなかったんだろう。各種ハイパーパラメータをチューニングすることで95.5Mから97.3Mくらいまで点数が上がりました。すごい。

optunaのチュートリアルを参考にしてスクリプトを書いてみました。 Tutorial — Optuna 3.0.3 documentation

import os
import optuna

def exec(T0, nr1, nr2, dispersion_ratio, nr3) -> int:
    # 並列でテストケースを実行して、トータルのスコアを読み込んで出力する
    os.system(f"python parallel.py {T0} {nr1} {nr2} {dispersion_ratio} {nr3} > score")
    with open("score", "r") as f:
        return int(f.read())

def objective(trial):
    # 以下はハイパーパラメータたち
    T0 = trial.suggest_float("T0", 100, 20000)
    nr1 = trial.suggest_float("nr1", 0.0, 1.)
    nr2 = trial.suggest_float("nr2", 0.0, 1.)
    dispersion_ratio = trial.suggest_float("dispersion_ratio", 0.0, 2.)
    nr3 = trial.suggest_float("nr3", 0.0, 1.)
    return exec(T0, nr1, nr2, dispersion_ratio, nr3)

study = optuna.create_study(direction='maximize')
study.optimize(objective, n_trials=1000)

best_params = study.best_params
print(best_params)

from multiprocessing import Pool
import os
import sys

a = sys.argv[1]
b = sys.argv[2]
c = sys.argv[3]
d = sys.argv[4]
e = sys.argv[4]
params = f"{a} {b} {c} {d} {e}"

def f(x):
    # x番目のテストケースを実行
    with open(f"in/in{x:03}.txt", "r") as f:
        txt = f.read()
        txt += "\n"
        txt += params # 元のテストケースにハイパーパラメータを書き込んで保存
    with open(f"scores/test{x:03}.txt", "w") as f:
        f.write(txt)

    os.system(f"./a.out < scores/test{x:03}.txt > out 2>scores/score{x:03}.txt")

 
if __name__ == '__main__':
    # 手元のPCで5並列までは性能が落ちなかった
    with Pool(5) as p:
        p.map(f, [i for i in range(100)])
    
    tot = 0
    for i in range(100):
        with open(f"scores/score{i:03}.txt", "r") as f:
            tot += int(f.read())
    
    print(tot)

    // C++でハイパーパラメータを受け取るところ
    // 環境変数OPTUNAが"true"の時だけ余分に標準入力からパラメータを受け取る
    if (getenv("OPTUNA")!=NULL&&string(getenv("OPTUNA"))=="true")
    {

        cin >> T0 >> neighbor_ratio1 >> neighbor_ratio2 >> dispersion_ratio >> neighbor_ratio3;
    }

感想

実装もほどほどにあり、いくつか重要な考察もあり、とても面白い問題でした。 AHCの入門としても良い感じの問題だったと思います。

また、鉄則本の他のパートもとても丁寧に書かれていて、AtCoderの入門として素晴らしい内容だと思います*2。入門向けの選択肢が増えることはとても良いことですね。

続刊(嘘)の『競技プログラミングマラソンマッチの鉄則』お待ちしています*3。

疑問

区が関節点にあたるかを判定するのを常にO(1)でできるようにする方法ってないのでしょうか? ノードを追加していく状況ではunion-find木を使えば連結性の判定ができるのに、ノードを削除していく状況では同様のことが難しいのはどうしてでしょうか? 初歩的な疑問すぎて勉強しろという感じかもしれませんが...

*1:正確には関節点を選んでしまった時にacceptされる可能性が低いと言った方がいいかも。関節点でない時には近傍(1)と同じになります。ただし上で書いたtomerunさんの工夫が使えなくなるので(acceptされないときに打ち切り)、近傍(1)を使った方が基本的には良いです。

*2:むしろマラソンパート以外の方が本筋だと思うのですが...

*3:誰か書いて...

yunix_kyopro’s blog

鉄則本マラソン Mayor's Challenge 感想