RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）に参加しました。
1位でした！
問題
はじめに
「コンピュータ」だと長いので「PC」と呼びます。
解法
PCの移動経路を変更する焼きなまし法で、PCの接続はBFSで行いました。
処理の流れ
- 状態の初期化
- 焼きなましループ：(a)～(c)を時間いっぱい繰り返す
(a)状態を少し変更してみる
(b)状態を評価する＝評価値算出
(c)状態の採用判定 - 一番スコアの高かった状態の移動と接続を出力
1.状態の初期化
プログラムに入力された情報で状態を初期化します。
状態は以下の情報を持ちます。
- 各セルにどの種類のPCがあるか
- 各セルにどのPCがあるか
- 各セルを通ったPCの履歴
- 各PCの現在のセル
- 各PCの移動経路
- 移動可能なPCリスト
- 巻き戻し可能なPCリスト
- 種類の優先度
- BFS起点PC（種類ごと）
- PCの移動回数合計
PCの接続に関する情報は持ちません。
2.焼きなましループ
(a)状態を少し変更してみる
以下の操作からランダムに1つ選び実行します（操作によって選択確率は変えてます）
- PCをランダムに1個選び、1～3マスランダムな方向に移動させる
- PCをランダムに1個選び、1～3マス巻き戻す
- PCをランダムに1個選び、1～3マス巻き戻してから1～3マスランダムな方向に移動させる
- PCをランダムに1個選び、1～2マスランダムな方向に移動させる、移動先に別なPCがあったらランダムな方向にどかしてから移動させる
- 種類の優先度をランダムに変える（低確率）
- PCの種類をランダムに1個選び、その種類のBFS起点PCをランダムに変える（低確率）
PCを「巻き戻す」とは、移動させたPCを1つ前のセルに戻し、移動させなかったことにする操作です。移動回数＋接続回数には上限があり、移動を巻き戻すことで接続回数が増やせるので重要な操作です。
ただし、操作の順序によっては巻き戻しができないケースがあります。
この図は、1番PCが下に1マス動いた後に、2番PCが左に2マス動いた状態です。
この状態から1番PCを巻き戻すことはできません。巻き戻してしまうと、2番PCが1番PCをすり抜けて移動したことになり、不正な操作になってしまいます。
これを判定するために、状態として「各セルを通ったPCの履歴」を記録しています。1番PCが元居たセルには1番PC→2番PCという履歴が記録されていて、巻き戻す場合はこの逆順にしなければならないという制限をかけています。
よって、この図では1番PCは元居た場所への「移動」は可能だが「巻き戻し」は不可能という状態になっています。
上記の制限や、周りが別なPCに囲まれていたりなどの理由で「移動」「巻き戻し」操作ができないPCがあります。状態として「移動可能なPCリスト」「巻き戻し可能なPCリスト」を持つことで、操作可能なPCを素早く選べるようにしています。
(b)状態を評価する＝評価値算出
起点となるPCから上下左右の直線上に調べていって、同一種類のPCがあったら接続、ということをBFSで行い、クラスタを作成します。
クラスタを作る順序は、状態として持っている「種類の優先度」「BFS起点PC」を使って次のようにします。
- 1番優先度の高い種類のBFS起点PCからクラスタを1個作成
- 2番目の優先度の種類のBFS起点PCからクラスタを1個作成
- 優先度高い2種類について、それまでに作成したクラスタの累計スコアを比較し、スコアが低い方の種類のクラスタを1つ作成（起点PCはid順）
これを2種類のクラスタが作成できなくなるまで繰り返す - 残り処理時間が少ない（10%以下）であれば、優先度3番以降の種類のPCも優先度順にクラスタを作成していく（起点PCはid順）
☆上記手順中に操作回数上限に達したらその時点で終了させます。
3番目の手順は、できるだけ2種類のクラスタを均等に大きくしようとしています。1種類のクラスタを大きくしてから2種類目を大きくしようとすると、1種類目のクラスタが邪魔になって2種類目のクラスタが大きくなりにくいためです。*1
4番目の手順は、2種類のクラスタをできるだけ大きくするのが高スコアにつながるため、優先度の低いPCは終盤にだけ計算することで処理時間をカットしています。
作られたクラスタからスコアを計算します。
このスコアに、以下のペナルティをかけたものが最終的な評価値となります。ペナルティ量は時間で減衰させ最終的に0にします。
- 行動回数が多いほど減点
- 移動回数が多いほど減点
- コネクタ長が長いほど減点
クラスタの結合
クラスタを1つ作成するごとに、それまでに作成したクラスタとの結合を試みます。
まず、クラスタ作成のBFS中に、他の種類のPCが見つかればそれをハブとして記憶しておきます。*2
BFS後、ハブとして記憶したPCを確認し、既存クラスタからもハブとして登録されているのであれば、そのハブを経由して既存クラスタと結合します。
複数ハブがあるのなら、結合できるものがなくなるまで結合処理を行います（スコアが減少するような結合は除く）
ハブを複数個経由して結合することは考慮していません。*3
(c)状態の採用判定
一般的な焼きなましと同様です。
評価値が上がっていればその状態を採用、評価値が下がっていても確率で採用。
採用しない場合は直前の変更操作の前の状態に戻します。
3.一番スコアの高かった状態の移動と接続を出力
状態として記録している「各PCの移動経路」をもとにPCの移動を決めていきます。
このPCを動かすには別なPCを先に動かさなければいけない、といった依存関係がありますが、状態として記録している「各セルを通ったPCの履歴」の通りになるような順序で移動させれば不整合はおきません。
接続は評価値算出に使用したものと同様の接続を行います。
その他効果のあったもの
各PCは3マスまでしか移動させない
パラメータを偶然いじったらスコアが上がったので採用しました（はじめは10マスまで移動を許可していた）
PCの初期位置には偏りがなく良い感じの間隔なので、それほど多く動かさなくてもいいということだと思います。巻き戻し制限の関係で、遠くに移動しすぎたPCがあると他PCが移動しにくくなるという理由もあると思います。
状態を複数持つ
スコアが安定しないため、状態を複数更新していって、うまくいった状態に絞り込んでいくということを行っています。
一定時間最高スコア更新しないなら最高スコア時点の状態に戻す
スコア更新が見込めないような状態に陥っている可能性が高いため、最大スコアを出した時点の状態に戻します。
焼きなましの様子
seed=2
seed=7
コンテスト中に考えたこと
※覚えてないところをは若干の嘘があるかもしれません
1日目～2日目
移動と接続両方考えないといけない。
移動を確定させた時点で接続方法が定まるかどうか？簡単には定まらなそう。
移動と接続を同時に焼きなませる？接続された状態で移動させると切断される？
移動させるだけだとスコア変わらないから、移動～接続までを行う近傍を考えないといけないよね。
移動と接続どっちかを貪欲にできないか。
あーケーブルの交差って駄目なんだ。接続する順番も重要になってくるし焼きなまししにくくなってきた。
既に提出した人のスコアを見るに1ケース5000点は出ている。1種類のPCはほぼ全部繋げてるのかな。
分からんのでとりあえず実装してみる。
まずBFSで接続処理を実装。手動でPCを移動させてみる。少し移動させるだけで結構つながる。
接続はBFSでするものとして、移動と巻き戻しの2つの近傍で焼きなましてみよう。移動順によっては巻き戻しで不整合が起きる。各セルに履歴を持たせれば回避できる気がする。大丈夫そう。
とりあえず動くようになったし提出する。
252,421点（2位）
思ったより高得点出た。この方針で行けるのでは。
3～5日目
提出すると順位表気になっちゃうからあんまり提出しないでいこう（後で一気に高得点出してびっくりさせたろ）
毎回BFSするのは遅いけど後で差分計算とかできるでしょ。*4
状態の変更操作をいろいろ思いついたものを試す。PC移動時に他のPCをどかすのは良さそう。あとBFS時のPCの種類の順番も変えられた方が良さそう。
他いろいろ試したけどほとんど没。
違う種類のPCを経由してでもクラスターを大きくするのはやったほうが良さそう。実装大変だぞ。頑張って実装したけどスコア減った。
バグってただけだった。直したらわずかにスコア上がった。しかし処理速度1/10ぐらいまで落ちている。高速化したらスコアも上がってよくなった。
焼きなまし変更操作の集計を出してみる。操作に失敗して無駄にループが回っていることが多い。操作可能なPCリストを作っておけば回避できそう。ちょっと高速化になった。
やりたいことはやれたのでそろそろ提出しよう。
355,702点（2位）
届かなかった……
6～7日目
パラメータ調整する。Optuna君頑張ってね。
焼きなましの変更操作の「移動」と「巻き戻し」を1マスじゃなく複数マスにしたらスコア上がった。それはそうだよね。
優先度高いPCほど焼きなましの操作対象にしたほうが良いのでは→スコア上がらず。
スコアが低いケースの焼きなましの過程をビジュアライザで見てみると1種類のクラスターが邪魔で2種類目のクラスターが大きくなれない状態になっている。2種類のクラスターを同じぐらいの大きさで広げてくのが良いのでは？
クラスターの作る順序を工夫した。そして2種類つのクラスター以外はあまり重要じゃないから接続処理はスキップだ。
Optunaで調整したパラメータでテストしてみたらスコアが大幅に下がる。結果をグラフにしてみると、スコアのばらつきが大きすぎてうまく探索できてなさそう。
過去最高スコアと比べた70%ほどしか出ていないケースも多いし、このスコアが安定させるのが良さそう。
評価値工夫するも良くならず。状態を複数開始にするのと、一定期間スコア更新なしでロールバックするするのを入れた。これで多少ましに…?
後はパラメータ調整ぐらいしかできなさそうだし提出しておく。
387,912点（1位）
やっと届いたが、もう少し上げないとだめそう。
最終日
Optunaはまたも失敗。スコアやはり安定しない。
手動でパラメータを調整。高速化。焼きなまし操作も思いついたのを試す。
PCの移動量最大を16マス→3マスにしたらスコア上がった。そんなに動かさなくてよかったんだ。
焼きなましの操作で、「巻き戻してから移動させる」という操作を追加してみるとスコア上がった。山登りたいなら必要やつだよね。
終了が近づいてきたので提出。
404,444点（1位）
うおーー
2000ケースでテストしつつ高速化できたので最後の提出。あとはお祈り。
402,264点
感想
問題はシンプルだけど、どこから手を付けていいかわからないような難しめの問題だったと思います。seed=7とかははじめはスコアほぼ取れないと思っていたのに、最後には5000点ぐらい取れるようになってうまく調整されてたんだなあと。
焼きなましにうまく落とし込めたのは良かったです。評価値はもうちょっと頑張ったほうが良かったかな。
自己ベストスコアと比べると70%のスコアしか出てないケースも多いので、まだまだ改善の余地はある気がします。
おしまい
