「RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)」に参加した

一週間コンテスト「RECRUIT 日本橋ハーフマラソン」に参加しました。

問題概要

リンク

$N \times N$のグリッドにマシンが置かれている。マシンは$K$種類存在し、各種類ごとに 100 台のマシンが存在する。

あなたには、以下の 2 種類の行動が許されている。

• 移動: １つのマシンを、隣接する 最大 4 マスのうち一つに移動させる。ただし、移動するマスにマシンがあってはいけない。
• 接続: 同じ行か同じ列に存在する 2 つのマシンを接続する。ただし、2 つのマスの間のマスに何かがあってはいけない。接続した場合、接続に使われたマスはケーブルで埋められる。マシン、ケーブルが存在するマスは接続に利用できない。

得点は、以下のように計算する。

あるマシン$x$からケーブルを辿ってマシン$y$に到達できる時、$x$と$y$は同一のクラスタに属する。 最終的に作られた各クラスタごとに、以下を計算し、その総和をスコアとする。

クラスタ内の全てのマシンの組$(x,y)$について、

• $x$と$y$の種類が同一なら+1
• $x$と$y$の種類が異なるなら-1

移動と接続は$100 \times K$回まで行うことができる。

自分の解法

暫定テストは 235,165(100 位/948)、最終スコアは 9,594,901(104 位/948)でした。

seed0000

seed0005

seed0007

貪欲法でやりました。 具体的には以下のような流れです。

種類$k$のマシンに関する貪欲 (以下、$k$ファースト法とする)

1. あるマシンの種類$k$をターゲットとして、現在の盤面から、全ての遷移可能な盤面 を 1 つずつ調べる。
2. 移動対象のマシンについて、移動前と移動後のそれぞれでマシンの上下左右の最近接マシンを調べておき、種類$k$のマシンの個数を調べておく。移動前の最近接の$k$の個数を$x$、移動後の最近接の$k$の個数を$x^{\prime}$とする。

3. 明らかな改善の移動を見つけたら、即座にその移動を行う。明らかな改善の移動とは、

   • 移動対象のマシンの種類が$k$で、$x=0$かつ$x^{\prime}>0$
   • 移動対象のマシンの種類が$k$以外で、$x-x^{\prime} \geq 2$ ($k$のタイプのマシンの接続を遮るマシンをどかすイメージ)

   に該当するもの。

4. 明らかな改善の移動が見つからない場合、以下に当てはまる移動から一つを採用する。

   • 移動対象のマシンの種類が$k$で、$x^{\prime}-x>0$
   • 移動対象のマシンの種類が$k$以外で、$x-x^{\prime}>0$
5. 移動後に、移動回数が $100 \times K-100$ に達していない、もしくはまだ 3., 4.に該当する移動が残っていれば 1.に戻る。
6. 種類$k$のマシンについて、 最近接の$k$の個数が多いマシンから順に BFS で接続を行なっていく。まだ行動回数が残っていれば、他のマシンでも同様に接続を行う。

解法の全体の流れ

まずは、全てのマシンの種類で$k$-ファースト法を行います。 ここまでで得られた最高スコアの盤面について、残り行動回数が 余っているかどうかで分岐があり、

• 行動回数が余っていない: 最高スコアを得たマシンの種類$k$について、$k$-ファースト法を時間いっぱいまで繰り返す。($k$-ファースト法は、手順 1 の調べる順序を変えることで別の結果が得られる)
• 行動回数が余っている: 怪しいことをやる。

という方針を取りました。怪しいことについては、説明が難しい割にそこまで効果が出ていなかったので、後の時系列の項目で軽く触れるにとどめます。

考えたことと時系列

2022.08.09(火)

最初に、移動回数は考えずに理論上の最大スコアがどうなるのかを考えた。最大スコアになるのは全ての種類について最大クラスタを形成できるケースなので、$\frac{k \times 100 \times 99}{2}$となるはず。全ての$k$について繋げるのは問題例を見た時点で無理そうな感じだったので、まずは 1 つのマシンでできる限りデカいクラスタを作ろうと考えた。

とりあえず何も移動せず適当に繋げるやつを提出し、スコアは26kだった。

2022.08.12(金)

とりあえず今より良くなる移動をひたすら採用していこうと考え、種類 1 のマシンを移動後に最近接の種類 1 のマシンの個数が増えるか、種類 1 以外のマシンを移動後に最近接の種類 1 のマシンの個数が減る場合はその移動を採用し、その後適当に接続した。 スコアは117k。

接続を行うときに無駄な接続を行わないように UnionFind を使うようにした。さらに、種類 1 でしか試していなかったところを全ての種類で試すようにした。スコアは186k。

2022.08.13(土)

移動回数が多くなってしまうことが多かったので、最後の移動を消した後繋ぎ直し、スコアが上がれば採用という処理を追加した。スコアは199kになった。

seed0、seed7 など移動回数が全く稼げない問題が見られたので、こういった問題の対策を考えた。 そこで、行動回数が上限に達していない場合に以下の処理を行うようにした。 マシンの種類$k$について現時点の最大クラスタを探し、そのクラスタをだんだん大きくしていきたい、という考えで、クラスタの個数＋クラスタに隣接する空白の個数(以下、テリトリーの面積と呼ぶ)が増えるような移動なら採用するようにした。スコアは204kになった。

2022.08.15(日)

上述の移動を加えてもまだ移動回数が少ないままだったので、テリトリーの面積を増やす移動がない場合は、テリトリーに隣接しない最も近い空白マスをテリトリーに近づける処理を入れてみた。やや効果があり、スコアは210kになった。

マスの移動候補が少ないなら DFS やればいいのではと思い軽く実装してみたが、なんの成果も得られませんでした。

最初に行うマシンを移動させる操作で、$k$の接続を遮るマシンをどかす、$k$を他の$k$に繋げる操作を優先したらスコアが上がったので、そのような移動を最優先するようにした。(ここで$k$ファースト法が完成)スコアは223kになった。

2022.08.15(月)

行動回数が上限に達する問題では 150ms 程度の時間しか使っていなかったので、時間いっぱい$k$ファースト法を試すようにした。232kまで上がった。

行動回数が上限に達さない問題でも乱択風の操作を入れ、時間いっぱいまで計算を回すようにした。234kになった。

2022.08.16(火)

計算打ち切りの時間を増やすなどして、235kになった。

感想

最終結果は予想以上に良かったのですが、seed0、seed7 のようなキツキツの問題では怪しいことしかできず、もうちょっと何かできたんじゃないかという悔しさがありました。

seed0 を見た瞬間に AHC011 のスライドパズルがよぎりましたが、他のシードを見ると別ゲーと分かってホッとしました。

結局 1 つの完全クラスタを安定して作るところまではいけなかったので、これが達成できるかどうかが上位陣との差だったなと思います。

焼きなまし・局所探索などは無理っぽいと思って最初から諦めていたのですが、1 位の bowwowforeach さんをはじめ、結構使っている人がいてびっくりしました。もっと鍛治の腕を磨いていきたいです。