概要
問題文 → ■
公式解説 → ■
自分の提出 → ■ （54153 点）
Heuristic contest タイプの問題で、厳密解が得られなくともそこそこ良い解を出力することが要求されています。
本番時間内の順位表基準で、トップスコア以上になりました。公式解説とも少し違いましたし、折角なので書いておきます。
リプレイ動画
解法はこれを見ると、大体イメージできると思います。
解法
基本方針
次の $3$ つのフェーズからなります。
- $0, 1$ の $2$ 種のタイルを上半分、$2, 3$ の $2$ 種のタイルを下半分に運ぶ
- 上半分の中で、$0$ を左半分、$1$ を右半分に運ぶ
- 下半分の中で、$2$ を左半分、$3$ を右半分に運ぶ
まずは $1$ 色注目で評価するのが簡単そうだと思い、そこから発想しました。$1$ 色注目パズルを $3$ 回行います。
「まず $0$ のタイルを確定」というような「$1$ 色注目」もできそうですが、$0$ を正しい位置に運んだあとの残り盤面の形が扱いづらそうに思ったので、このような方針を採用しました。
$3$ 回同じことをやるだけなので、はじめの部分のアルゴリズムについて述べます。
ビームサーチ・評価関数
ビームサーチ を使います。適当な評価関数を設定します。 $t$ 回操作後の盤面を、$t$ 昇順に生成しますが、そのうち評価関数の値が良いもの $n$ 件のみ以外は捨てていきます。$n$ は調整可能なパラメータで、時間やメモリの制限に合わせて設定します。
評価関数としては、ある色のタイルを $x$ 座標の小さい側に寄せたいとして、「その色のタイルの $x$ 座標の総和」を用いました。
「盤面の生成」は、遷移前の盤面からの全回転（$1$ 回から $3$ 回まで）を対象としています。$3$ 回回す場合には、時刻 $t+3$ の priority queue に入れるというような実装になります。
評価の高速化
ある盤面に対してあらゆる回転を列挙して、評価関数の値（対象色のマスの $x$ 座標の総和）がどのように変化するかを計算したいです。
領域 $a\leq x < a + s, b\leq y < b+s$ 内に対する回転操作をすると、座標は $(x,y)\mapsto (y+a-b,-x+a+b+s-1)$ などと変化することを考慮すると、
- 長方形領域内の、回転前の対象マスの個数を $s_1$、$x$ 座標の総和を $s_x$、$y$ 座標の総和を $s_y$ とする
- このとき、回転後のそれらは、$s_1$, $s_y + (a-b)s_1$, $-s_x+(a+b+s-1)s_1$ となる
ことが確かめられます。
遷移前の盤面を固定し、$O(N^2)$ 時間の前計算を行うことで、遷移後の評価値はどの回転に対しても $O(1)$ で取得できることが分かりました。
評価関数を手の込んだものにするような工夫もありえましたが、例えば座標 $x$ にある対象色のマスのコストを $2^x$ などと割り当てると、ここの高速化ができなくなると思ったので、今回はこれを実装しました。
感想
まだまだ Heuristic Contest は勉強し始めたばかりですし、多くの問題に触れて慣れていくことを優先したいので、これ以上の詰めはやらないかな？
リプレイを見ると、自明に下手なところはあって、各フェーズの終盤がひどいです。評価値が悪化しないなかで、ランダムな $1$ ～ $3$ 回転を試行錯誤しているのですが、 「$3$ 回転してひとつだけ運ぶ」ような効率の悪い動きが多発しています。ふたつまとめて評価値を落とさずに運ぶような遷移を全く考えていないことが問題ですね。
うーん、評価値が下がる動きもランダムに採用するとか、ここだけ専用ロジックを追加とか、そういうことをやる感じなのでしょうか？
こういう明確な「時系列」に基づく解の構築って、良い解の中間時刻をちょっと取り換えてもまた良い解であるという性質がなくて、山登り / 焼きなまし 等と比べてビームサーチになりやすいのかな。
