問題

www.topcoder.com

コード

MM150 last submission · GitHub

戦略

以下の処理を高速に繰り返して一番スコアが良くなるものを採用します。

なるべくクイーン同士が取り合わないような配置を焼きなまし法で求める
求めた配置に対して最小費用流を用いて位置の割当を行う
割り当てた配置にダイクストラ法を用いて移動させる

クイーンの配置を焼きなまし法で求める

まず最初に焼きなまし法によってクイーンの配置を探索します。近傍としては以下の 1つです

任意のクイーンの中から一番他のクイーンと取り合っている数が多いものを選択して、任意の空白地点の中から一番他のクイーンと取り合う数が少ない場所に移動する

操作後にスコアを評価して近傍を採用するかどうかを判断します。制限時間を超えるかクイーン同士の衝突がなくなるまで (Errors == 0) この処理を繰り返していきます。

衝突判定の高速化

クイーン同士が衝突しているかどうかの判定を高速化するためにクイーンの影響範囲をカウントしてその値をチェックすることで衝突判定の高速化を行いました。

この情報は各色毎に持たせており、書かれた値の数だけ他のクイーンと衝突していることを表しています。

最小費用流を用いて位置を割り当てる

求めた盤面に対して、どのクイーンがどの位置に移動するのかを最小費用流を用いて求めます。コストとしては生スコアを基本としてクイーンを通過するときに余計なコストが発生するようにしました。

割り当てた位置に移動させる

割当が完了したらその位置にダイクストラ法を使用してクイーンを移動させます。移動の際には他のクイーンを動かせないものとして処理します。移動できるクイーンの中からコストが一番小さいものを移動させていき最終的に移動できるクイーンが無くなるまで繰り返します。

移動させる順番をランダムに変える

コストが小さい順に移動させると移動させるクイーンの順番が固定されますが、コストにランダムな値を追加することで移動の順番が固定化されないようにしました。この移動させる処理を複数回行って一番コストが小さくなるものを採用しています。

感想

問題と見たときに AHC013 の bowwow さんの解法が有効かなと思ったけど実装が面倒そうなのでスルーして自分の考えた方針でそのまま実装した。Nクイーン問題自体はかなり高速で解けたけど結局移動させるときに他のクイーンを動かさない前提の操作にすると余計な遠回りをしてコストが余分にかかってしまうのをどうにも出来なかった。