ソフトウェアエンジニアの杉江（AtCoder ID: tsutaj）です。
2 年ほど前から、プログラミングコンテストサイト「AtCoder」でヒューリスティックコンテスト（通称：AHC）が開催されています。どんなコンテストなのか簡単に説明すると、最適解を出すことが難しい問題に対して、できるだけ良い解を出すプログラムを期間内に作成するコンテストです。
先日 MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019） に参加して、結果は 89 位（正の得点を得た 737 人中）でした。どんな解法になったのか書いていきます。
この記事を読んでヒューリスティックコンテストに興味が出ましたら、ぜひコンテストにも参加してみてください！
問題概要
三次元物体を正面から見たシルエット・右から見たシルエットが 2 組与えられます。 の立方体を面同士でくっつけてできるポリキューブ状のブロックの集合をひとつ決め、それらのブロックを使って正面・右シルエットが完全一致するようなポリキューブの配置を求めてください。同じブロックの集合を使って 2 組のシルエット両方について完全一致できる必要があります。
（ざっくり言うと）できるだけ大きく、できるだけ少ない数のブロックの組み合わせで実現できると高い評価が得られます。片方のシルエットの組でしか使われず、もう片方では使われないブロックが存在しても良いですが、そうするとスコアが減点されてしまいます。
自分の解法
一言で言うと「力まかせに答えを見つける」という解法で、条件を満たすまでランダムにポリキューブを決めて配置することを繰り返します。ですが、闇雲に探索をしても良いスコアにはならないため、いろいろ工夫しました。
配置するポリキューブのサイズを制限する
個の立方体からなるポリキューブは何種類あるか考えてみます。以下の表は Wikipedia の記事 から引用したものですが、
が大きくなると爆発的に増えるようです。（今回は鏡像を区別するので左側の列が参考になります）
このことから、サイズ 5 までのポリキューブに限定して探索することにしました。適当にはめていくだけで本当に解が作れるの？と思われるかもしれませんが、意外と作れます。
しかしこれに限定して探索しただけだと、当然ですが得られる解にはサイズ 5 までのポリキューブしか登場しません。より大きなポリキューブも欲しいので、シルエットの条件をある程度満たしたらポリキューブをマージしたり伸ばしたりすることで、より大きなポリキューブになるようにしました。その操作をしたあとに、解として正当な状態になっていれば OK です。
ちなみに、上位陣の解法を見ていると、ポリキューブの形状と位置を決めてから配置できるか試すのではなく、各シルエットについて適当に始点を決めて、始点から伸ばせるだけ伸ばしている方がちらほらいました。私は「この方針だったらブロックの大きさのバランスが取れないだろう」と思って捨ててしまいましたが、うまくやるとできるんですね。。。
条件を満たしたら、解を部分的に破壊する
最終日の前日まで、私の解法は「正当な解を求めることを繰り返す」ものでしたが、正当な解がひとつ得られたあと、それを完全に忘れてまっさらな状態でもう一度探索を始めていました。解が得られるまでに割と時間がかかることもあってこれでは非効率的です。
そこで、正当な解が得られたあとは部分的に破壊して、途中から再度探索するようにしました。ポリキューブのサイズが最も小さいもの（複数ある場合はどれか 1 つ）を選んで、それ自身とその周囲にあるものを消すことで部分的破壊をしました。サイズの小さいポリキューブを除去した状態からまた探索できるので、これを実装するだけで順位表上のスコアが約 1.25 倍になりました。
解を部分的に破壊しているため、状態の近傍（少し変化させた状態）を取っています。上位の解法を見ていると、ざっと見ただけでも他に以下のような近傍のとり方があるようです。とても勉強になりました。
- ポリキューブの平行移動
- セルの譲渡（一方で使用していた領域を、隣接している他方のポリキューブに譲る）
- 取り除いても解の条件を満たすようなセルの削除
高速化
探索がどれくらい回るのかは解法の性能に直結します。多く回れば回るほど良いです。そのため、どのコンテストでも高速化は重要になります。今回もたびたび高速化に迫られました。
私は Rust でコンテストに参加していますが、flamegraph でボトルネックを見つけるのをよくやります。処理時間全体に対して各処理がどれくらいの割合で行われているかがわかるので、幅の大きい部分を重点的に直していきました。
高速化にたびたび効いたのは Zobrist Hashing でした。各座標に乱数を事前に割り振っておき、ポリキューブ（の位置を正規化したもの）が占める座標に対応する乱数の XOR を取ることで、ポリキューブ同士が同型かどうか判定しました。Zobrist Hashing については以下の記事を参考にしました。
同型なポリキューブのペアについて、座標と回転方向のマッピングができればハッシュを使わなくても処理が出来るかとは思いますが、複数の方向で同型になる場合があったり、ペアの入れ替えをしたくなったりしてどうも納得いくものができず、結局ハッシュにずっと甘える形になりました。。。どこかで表現度を落としてでも高速化に振り切ってもよかったかもしれません。
解法まとめ
自分の解法を簡潔にまとめると次のようになります。やっていること自体はシンプルですが、実装はそこそこ大変でした。
焼きなまし法の適用
コンテスト後に「解を部分的破壊しているところは近傍選択っぽいし、焼きなまし法にできるのでは？」とふと思ったので、やってみました。
今までの解法は「常に解を採用し、それを部分的破壊して次の探索に進む」というもので、貪欲に解の生成を繰り返しているだけでした。これを次のように変えてみました。
- 解が良くなったら常に、解が悪くなったら確率的に採用したのち、それを部分的破壊して再開する。採用しない場合は最後に部分的破壊を行った状態から再開する。
- 不採用が一定回数続いた場合、何も置いていない状態から再度探索する。
こうすることで、手元で 1000 ケース回したときのスコア平均が 6% ほど改善しました。近傍を増やしたり、温度を調整したりするとさらに伸びるかもしれません。焼きなまし法にもっと慣れていきたいですね。
さいごに
この問題の答えを人力で見つけるのはかなり大変だと思います（というか自分には無理です）。ですが、自分が書いたプログラムに任せればいい感じの答えが見つかります。自分の書いたプログラムで、自分には不可能なことが可能になる点が、ヒューリスティックコンテストの面白さのひとつだと感じています。
最終日の前日までスコアが思うように伸びず挫けそうにもなりましたが、粘り強く考えて最後にいい手法が思いつけてよかったです。とはいえまだまだ伸びしろは十分なので復習したいですね。
モノグサでは、記憶のプラットフォーム「Monoxer」を全人類に届けることを諦めない、粘り強いエンジニアを募集しています！！
