AHC013お疲れ様でした。13,868,038点で18位でした。なんとか順位表1ページ目に残れて良かったです。

今回も解説を書きます。焼きなましです。

問題概要
方針
解説
日記
感想

問題概要

いい感じにコンピュータを動かしてから同じ種類のコンピュータをたくさん繋いでつよつよクラスタを作ってね。

方針

筋が良い解法かというと微妙なのですが、焼きなましをしました。

焼くときの注意点として、ただ単にコンピュータを移動させたり接続したり接続を切ったりするだけだとすぐに局所解にハマってしまい、より良い解を探すことができません。というのも、今回の問題では得点がクラスタのサイズの2乗和で決まるため、もしそのクラスタ内の接続を切ってしまうと得点が大きく下がってしまい、いくら焼きなましといえどそのような解を経由することは絶望的だからです。そのため、できるだけ接続を維持しつつ解空間が滑らかになるような近傍を作っていく必要があります。

貪欲・ビームサーチ系統で解くことも考えたのですが、1個目のクラスタは良いとして2個目のクラスタを作るときに1個目が邪魔になってくるため、そこは同時に焼いた方が良いかな……ということで今回は焼きなましを選択しています。上位陣でこれらの手法を使っている人はサーバー室の外周を空けたり、ランダム性を加えて何度も試行を繰り返したりと、2個目のクラスタを大きくする余地ができるよう何かしらの工夫を加えている印象でしたね。

解説

枠組み自体はシンプルな焼きなましです。*1 1種類目のコンピュータだけで焼いてから2種類目のコンピュータを焼いて……とか後処理を加えて……とかは一切なしで、ただ単に3秒間焼きました。

解の持ち方・近傍の指定・操作回数上限の取り扱いがキモになっていると思われるので、その辺りについて説明します。

解の持ち方

「各コンピュータの移動操作列」と「コンピュータ同士の接続」を解として持ちました。両者の整合性が取れるよう十分注意しながら近傍を作成します。

この時の注意点として、「コンピュータAを移動→コンピュータBを移動→コンピュータAの移動を元に戻す」といった操作を行った際、実現不可能な移動になってしまうことがあります。これを防ぐため、あるコンピュータが一度移動してきたマスはその後立入禁止という制約を付けました。これにより移動に関するコンピュータ間の依存関係がなくなり、独立に移動の追加・削除を行えるようになります。*2

近傍

近傍は以下の5つを採用しました。

あるコンピュータをランダムに選び、ランダムな方向に関する接続有無を反転する
あるコンピュータをランダムに選び、ランダムな方向に1マス移動させる
あるコンピュータをランダムに選び、最後に行った移動を削除する
あるコンピュータをランダムに選び、移動操作列を全てリセットした上で、ランダムな移動に変更する
あるコンピュータをランダムに選び、別のクラスタの同じ種類のコンピュータまでの接続経路を乱択BFSで探す

各近傍の採用確率はoptuna先生に決めてもらいました。この中だと近傍4が結構強かったです。

なお、各近傍を適用した際にどのコンピュータに変化が生じたかを覚えておいて、その部分だけスコアを計算することで高速化を図っています。

近傍1: あるコンピュータをランダムに選び、ランダムな方向に関する接続有無を反転する

指定された方向に接続されていない場合は接続を試み、接続済みの場合は接続を解除します。比較的分かりやすい近傍かなと思います。

接続を行う際、その線分上に他のコンピュータ間の接続が存在する場合は、接続を諦めるのではなくそのコンピュータ間の接続を切ってしまうようにしています。

近傍2: あるコンピュータをランダムに選び、ランダムな方向に1マス移動させる

移動操作列の末尾に新しい移動を追加する近傍です。右→左と動かすのは無駄なので*3、その場合は近傍3の処理を行います。

移動させるだけなら簡単ですが、接続を極力維持しつつ移動させようとすると結構大変です。

あるコンピュータを右に1マス移動させることを考えます。このとき、左右方向の接続はそのまま維持することができます。一方上下方向の接続は切れてしまうので、そのままだとスコアがガタ落ちしがちです。その場合は、上下方向の接続を繋ぎ直せるならつなぎ直すという処理を入れています。また移動先についても、一旦上下のコンピュータ間の接続を切った上でコンピュータを割り込ませ、改めて繋ぎ直すという処理を入れています。

近傍3: あるコンピュータをランダムに選び、最後に行った移動を削除する

操作列の要素を追加するか削除するかという違いだけで、ほぼ近傍2と同じです。

近傍4: あるコンピュータをランダムに選び、移動操作列を全てリセットした上で、ランダムな移動に変更する

近傍2, 3をまとめて一気にやるような近傍です。ここもつなぎ直しには十分注意します。本当に注意しないと一瞬でバグります。

新しい操作列は以下のようなアルゴリズムでランダムに生成しました。

moves = []
while True:
    # 0以上5以下の乱数を生成
    direction = random.randint(0, 5)
    if direction < 4:
        moves.add(direction)
    else:
        break

近傍5: あるコンピュータをランダムに選び、別のクラスタの同じ種類のコンピュータまでの接続経路を乱択BFSで探す

他の色のコンピュータを経由してでもやや遠くのコンピュータに繋ぐための近傍です。コンピュータ上でのみ方向転換可能な乱択BFSを行って別クラスタまでのパスを見付け、パス上の邪魔な接続を全て削除した上で繋ぎ直すということを行っています。*4

乱択BFSは以下の擬似コードのようなアルゴリズムで行っています。Dial's Algorithmの方が近いかも？

current_queue = []
next_queue = []

while len(current_queue) > 0:
    while len(current_queue) > 0:
        length = len(current_queue)
        i = random.nextint(0, length - 1)

        # 末尾要素とswapすることでO(1)で削除するテク
        swap(current_queue[i], current_queue[length - 1])
        current = current_queue.pop(length - 1)

        for direction in range(4):
            # なんやかんややる
            pass

    swap(current_queue, next_queue)

操作回数上限の取り扱い

疎なケースだと特に操作回数上限がキツいです。そこで焼きなまし中は操作回数上限を超えるものを許容し、その分ペナルティを与えることにしました。*5 操作回数上限を超えた数を $c$ 、焼きなましの進行度合いを $T\ (0\le T\le 1)$ として、ペナルティを $10^{-3}c\times {10}^{5T}$ と定める*6 ことで、時間経過ととも指数関数的にペナルティを大きくするようにしています。

最終的な解は当然制約を満たす必要があるため、操作回数が上限以下の解のなかで最も生スコアの高いものを出力するようにしています。

日記

コンテスト中の日記は別記事にまとめています。

上記解法に至るまでには紆余曲折があったので、ご興味あれば。

www.terry-u16.net

感想

シンプルな問題設定ながらめちゃくちゃ難しく、面白い問題でした。 $N,K$ といったパラメータによって全然違う問題になる点も面白かったですね。こういう問題はうまくスコア計算式を設定しないと一部のテストケースの寄与度が大きくなりすぎてしまう恐れがある *7 のですが、そのような偏りがほとんど存在しないような設定となっているのは流石といった感じでした。