estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）に参加しました。暫定6位、最終4位でした。久しぶりに上位に入った気がする。

解法の中でやったこと

初期解

貪欲法で初期解を作る。以下の 5 通りの評価値それぞれで解を作って一番スコアの高いものを選ぶ。

d(q, p1)² / (周長) (d はユークリッド距離、q = (-1, -1), (-1, N), (N, -1), (N, N) の 4 通り)
p1 の重み（スコア計算に使うやつ）

焼き鈍しの温度

初期温度: N <= 37 のときは 20000、N >= 39 のときは区間 [39, 61] で 30000 から 10000 に減少する N の一次関数
最終温度は初期温度の 1/10
温度は経過時間に対して線形に減らす

近傍

適当に選んだいくつかの長方形とそれに依存するものを削除して、貪欲法で作り直す。ただし、依存するものを削除したときに削除した長方形の合計が min(解の長さ/2, 2N) を超えたときは作り直しをしないで棄却する。

試行回数は大きいケースで4万回（作り直しをしないで打ち切ったときも数えると5万回）、小さいケースで50万回ぐらい。

削除する長方形の選び方は以下のいずれかをランダム（一様ではない）に使う。

依存関係を DAG にして後ろから適当な数だけ削る
ランダムに選んだ長方形とそれに依存するものを削除、を適当な数削除されるまで繰り返す
ランダムに選んだ長方形とその p1 に隣接する4点または8点(どちらにするかは等確率で選ぶ)を頂点にもつ長方形、およびそれらに依存するものを削除

長方形を作り直すときは、焼き鈍しの試行ごとに以下の選択方法の中から一つ選んでおく。その方法で長方形を候補から選択して盤面に追加し、候補の差分を計算する、という処理を候補がなくなるまで繰り返す。

初期解を作るときと同じ評価値を使い、最大のものを選ぶ（5 種類）
- ただし、削除した長方形のうち一つをタブーとして一様ランダムに選んでおく。タブー長方形の評価値は他のどれよりも低くする
p1 からマンハッタン距離 2 以下の範囲にいくつ使われている点があるかを数え、それが最大なものの中から一様ランダムに選ぶ
- この場合にタブー長方形を選ばないようにするのを忘れていた（これを書いていて気付いた）
候補全体から一様ランダムに選ぶ
- この場合にもタブー長方形を選ばないようにするのを忘れていた（これを書いていて気付いた）

その他

候補の列挙をなるべく高速にできるように頑張る。傾いた長方形同士が辺を共有するかどうかの判定は45度回転して座標軸に並行な場合に帰着すると速い、とか。
N <= 37 のとき、一定回数最適解が更新されてなくて、残り時間が 500ms 以上あるならそこで打ち切って初期解からやり直す。やり直すまでの回数は、 p = (M - N) / (floor(N² / 12) - N) として p <= 0.51 なら 20000 回、p > 0.51 なら 10000 回。

解法以外でやったこと

N, M, seed を渡してテストケースを生成する generator を書き、N, M がいい感じに均等に分布してるテストセットを生成した。これで N, M の大小による傾向の違いを調べやすくしようとした。
EC2 のインスタンスを立ち上げてそっちで 880 個のテストケースを実行できるようにして、パラメータの調整やテストに使った
ローカル実行のとき、main の最後で経過時間を見て上限を超えていたら異常終了する（実行時間の制御に失敗していたら検出するため）

コンテスト中の経過

やったことのうちそれなりに重要だったり細かすぎないことをメモから抜粋してみます。2日目から始まりますが、初日はほとんど何も記録が残ってなくて、問題文を読んでビジュアライザを少し触った記憶しかないのであまり取り組んでなかったのだと思います。

22-09-18 (Sun)

2日目。とりあえず貪欲法で作れるだけ作ってスコアを得ました。評価値として追加する頂点の重み / 向かいあう頂点間のマンハッタン距離が大きいものを優先しようとしてみたのですが、実はバグがあってそうなってませんでした。この日のスコアは 33320470。

次にどの長方形を選ぶのがいいかをどうやって評価するかがかなり非自明ということがなんとなくわかりました。問題の見た目からビームサーチを検討したい気がしていました。

22-09-19 (Mon)

3日目。祝日だったのでけっこう時間を使いました。

昨日のコードで重みと思っていたものが重みになってなくて、中心ではなく原点からの距離を使っていたことに気がつきました。ただし、この部分を直すとスコアが下がったので、原点から遠いものを優先的に選ぶとなぜかうまくいくらしいことがわかりました。つまり、端の方からきっちり埋めていった方がスコアがよくなる？

すぐに思いつくこととして、途中の長方形とそれに依存するものをすべて削除して貪欲を途中からやり直す山登りまたは焼き鈍しがあります。一つの長方形に依存するものを連鎖的に消していったときに、ほとんど残らなかったりするとあまり意味がなさそうだと思ったのですが、実際に依存関係がどうなっているか確認してみたら、そんなにたくさん削除しなくても済みそうだったのでやってみました。

とりあえず山登りしたら 47126345 で、焼き鈍しに変えたら 53218433 になりました。でも途中の様子を見てる感じだと、うまく探索しきれてないような気がします。

同じ盤面が何度も出現しているのかもしれないと考えて、最近見た盤面とか最近使った長方形を禁止する tabu list を作って重複を回避しようとしてみましたが、スコア上がりませんでした。（でもこのアイデアを最終日に部分的に復活させて「直前に削除した長方形のうち一つを選んで優先度を最低にする」としたらちょっとスコアが伸びたので、ここの考察は無駄ではなかった）

22-09-20 (Tue)

4日目。解の表現を変えたらどうかななどと実験をしたけどスコア上は進展なし。

この時点では、多様性が低いことが一番の問題で、次に計算速度が課題という認識でした。

22-09-21 (Wed)

5日目。パラメータがいい感じに分布したテストセットを作りたいと思ったので generator を書きました。

def generate(n, m, seed):
    random.seed(seed)
    lb = n // 4
    ub = 3 * n // 4
    points = set()
    while len(points) < m:
        x = random.randint(lb, ub)
        y = random.randint(lb, ub)
        points.add((x, y))
    return sorted(list(points))

実装がこれで済むのなら最初に書けばよかった。

22-09-22 (Thu)

6日目。スコアがばらつくときにレプリカ交換法を使うと安定しやすいという話があるので試してみました。

seed = 0 の入力で解法に渡す seed を変えて走らせた結果は以下のようになりました。

焼き鈍し
902477 807067 890458 749102 898790 819738 807067 883187 900870 877892
std = 50878

レプリカ交換法
887537 888294 913446 888294 906638 910326 907205 924132 907205 907205
std = 11561

この入力では安定していい結果が出ていますが、大きいケースだと試行回数が足りてなくて安定して悪い結果が出るようでした。上に書いた generate で N = 61, M = 285, seed = 1 としたテストケースで同じことをやってみた結果は以下のようになりました。

焼き鈍し
1303088 1128350 1305274 1265825 1116739 1261079 1185880 1264542 1116061 1252784
std = 72146

レプリカ交換法
1110614 1047230 1062909 1135390 1064429 1013849 1110354 1055146 1054999 1048891
std = 34923

最終的には 2000 ケースの合計で評価されるのだから、分散が小さいかどうかより平均が大きいことが重要なはず、ということで使うとしても小さいケースだけかなという感じです。（結局最終提出では使わないで、温度を高めにしました）

22-09-23 (Fri)

7日目。ちょっと高速化をしてみたり近傍の調整をしたりしていました。

asprocon2 のときにやった方針（割り当てを2割ぐらい解除して貪欲法で割り当て直す）が今やってることと似ている気がします。asprocon2 ではいい貪欲法を作って貪欲法のパラメータを焼き鈍しで改善するという方針がよかったのですが、今回の問題にはそんなにいい貪欲法がなさそうなのでこの知見は適用できないかもしれません。

22-09-24 (Sat)

8日目。長方形を追加したときに、次に追加できる長方形のリストを毎回一から作っていたのですが、追加前のリストとの差分だけ計算するようにしました。以下の処理をすればよくて、地道に場合分けなどを頑張るとできます。

追加した長方形と重なっているものをリストから削除
追加した長方形の p1 を使ってできる長方形をリストに追加

これで 67444080 に。

22-09-25 (Sun)

9日目。一年半ぐらい停止していた EC2 のインスタンスを起動して使い方を思い出したり、レプリカ交換法の方がよくなるケースがどういうのかを調べたり、プロファイルを細かく見てみたりしていました。

それから焼き鈍しの途中で best がしばらく更新されなかったら何かした方がいいんだろうなとずっと思っていたのですが、温度を上げてみるとかしてもいまいちうまくいってる感じがなくて、とりあえず 10000 回連続で best が更新されなかったら初期解に戻るという処理を入れたりしていました。best に戻すのではなく初期解に戻したのは、best が局所最適に近くてその周りからうまく脱出できない状態になっているだろうと予想したためです。（結局最後までほぼこのままになった）

22-09-26 (Mon)〜22-09-30 (Fri)

ずっと高速化したり削除する長方形の選び方をちょっと変えたりしてました。あとテストケースを 880 個作って評価するようにしました。

880 個は擬似コードを書くとこんな感じで作っています。

for n in [31, 33, ..., 61]: # 16 通り
    for p in [0, 0.1, 0.2, ..., 1]: # 11 通り
        m = round((1 - p) * n + p * (n * n // 12))
        for s in [1, 2, 3, 4, 5]: # 5 通り
            generate(n, m, s)

30日の夜中に温度調整などのための実験を回していました。

22-10-01 (Sat)

最終日。夜中に回してた実験の結果とかこの日に行った追加実験の結果を見て温度などのパラメータをそれっぽく決めました。

29 日に 100 ケースで予備実験して大幅に改善した変更を明らかに上がってるから大丈夫だろうと思って 880 ケースで試さずに commit したら実は 880 ケース回したときには悪化することがこの日に判明して revert したりしました。スコアが安定してないとこういうことが起きるのか。

あといくつか細かいことを思いついて改造して実験したら、よくなったのは以下の二つでした。

貪欲法で次の長方形を選ぶとき、評価関数は複数ある中から一つ選んで使うのですが、その中にチェビシェフ距離 2 以下で既に印の付いているものが多い方がよいという評価関数がありました。これをマンハッタン距離に変えたらよくなりました。（880 ケースの平均が +14000 ぐらい）
削除して作り直したときに完全に元に戻ってしまうことがあったので、それを避けるために削除した長方形のうち一つを選び、作り直しのときにそれをなるべく使わないようにしました。（880 ケースの平均が +7000 ぐらい）

これらを入れて提出したら暫定スコアが下がりましたが、880 ケース自分で回して上がっているのでそっちを信じることにしました。

反省など

ほとんどの時間は細かい調整をしていました。それはそれで退屈ではないのですが、もっと問題そのものの性質をよく見て気付きを得られたらより楽しめたのではないかとも思います。コンテスト中も問題の性質についてほとんど考えていないことが気にはなっていましたが、具体的に何を見たいというのがなかなか浮かばなかったので、とっかかりがつかめないままでした。解説放送を聞いた感じだと、外側に広がるときにどういう仕組みで広がっていくのか、という疑問を持ってよく観察すれば、そこから視界が広がるきっかけを見つけられたのかもしれません。

コンテスト中に難しく感じたのは以下の二点で、こういうのはある程度一般的な話だと思うので、対処法のバリエーションを増やしていきたいところです。

スコアが不安定すぎて改善できたかどうかの評価がどの程度正確にできているのかが分からなかった。
温度を高くしても、かなり早い段階で出たスコアがその後全く更新されないということが起こりがちだった。今回は強制的に初期状態からやり直すようにしたが、もっと上手い方法がありそうにも思う。