AHC011でやったことの解説

この記事を書いた背景

こんにちは。競技プログラミングのコンテストに参加しているyunix (https://atcoder.jp/users/yunix )です。 最近行われたAtCoderAHC011に参加して33位でした。 マラソン初心者なりに色々やってみて学びが多かったので、それについて備忘録として記事を書きました。

また、長期のマラソンマッチに時間をかけて参加するのは初めてだったのですが(と思ったけれどHTTFは割とちゃんとやってたな...)、コンテスト中に色々な方法を試して挙動がどう変わるかを調べたり、処理速度を改善したり試行錯誤することが本当に面白かったです。 試行錯誤してプログラムを書くことが面白かったということを伝えたい、AHCのようなマラソンマッチのコンテストに興味をもつ人が増えてほしいという気持ちで記事を書きました。

この記事の内容

  • AHC011の概要
  • 解法の解説
  • 学びを得たこと

AHC011の概要

AHC011の概要

上図のように正方形の盤面の上に、タイルが敷き詰められています(左図)。 そのうち一つのマスは空になっていて、そこに隣接するタイルをスライドさせて、中央の図のようにすることができます。 空きマスにスライドさせる操作を繰り返して、最終的にマス同士が連結した木を作ります。

このようなパズルを与えられた手数以内で解くようなプログラムを書くことがコンテストの目的です。 なお、木を作ることができることは保証されており、逆に木構造になっていればどのようなものでも大丈夫です。

コンテストの採点基準は

  • 盤面のタイル全てを使う木を作ることができなかった場合
    • 問題の制約として、手数以内に木を作るようにタイルをスライドさせることができることは保証されています
    • とはいえ、うまくタイルをスライドさせないと木の状態になりません。手数以内に木にならなかったら、盤面にある最大の木の大きさが点数になります。
  • 盤面のタイル全てを使う木を作ることができた場合
    • この場合には木を完成させるのにかかった手数が短いほど高得点になります

問題で与えられる盤面のサイズ(N)は6~10の5通りで、それぞれが等頻度で出題されます。 また、最終的な評価は3000問をプログラムに解かせて、得られたスコアの合計で決まります。

上図のようにN=3と小さければ全探索などをして簡単に解くことができるのですが、N>=6くらいになってくると色々と工夫をする必要が出てきます。 いかにいい感じに工夫をして、短い手数で木を完成させることができるかがコンテストの焦点でした。

N=6の時は以下のような感じです:

解法の解説

要約

  • 山登り法で完成予定図の木を作りました
  • A*探索を使って上から1行ずつ完成させました
    • 1行完成させる際に完成予定図の方の木をいじって、作りやすいような盤面に並び替えました
    • 最後の下の2行はまとめて完成させました

詳細な解説

大きく分けて2つのステップからなっています:

  • 完成予定図の木を作る
  • 完成予定図を完成させるようにタイルを動かす

最初に問題を見たときに思ったことは、「タイルを動かす」「木を作る」この「両方」を同時にやるのはかなり困難そうということです*1。 15パズルのように完成図が明らかであっても難しいのに、どう作ればいいかわからないままタイルを動かして行って完成させるイメージができませんでした。

そこで、まずは完成予定図を作って、それに向けてパズルを解く、という感じに一つずつ各個撃破していくことを思いつきました。 以下ではそれぞれのステップでどのような処理をしたかを書いていこうと思います。

完成予定図の木を作る

完成予定図を作るにあたって2つの方針が考えられました:

  • 初期図面にあるタイルを好き勝手に並び替えて、木を作る
  • 適当な木を作り、そこから変形していく(詳細は後述)

前者の方針は難しそうに感じたので、後者を採用しました。 (ただし、良い感じに工夫をすると前者の方針で木を作ることができるそうです。コンテスト後に知ってとても驚きました)

手順は上の図のような感じです:

  • まず適当な全域木を作ります(この最初の盤面は本当に適当でいい)
    • 当然この適当な全域木には初期盤面から到達することはできません。適当に木を用意したので、盤面に存在する各タイルの数が異なるためです
    • 逆に考えると、各タイルの枚数が初期盤面と同じ木を作ることができれば、それは完成予定図にすることができます
  • この全域木に対して、タイルの間の辺を切ったり繋いだりして、木を徐々に変形させていきます
  • 最終的に初期盤面とタイルの種類の数が同じになるまで変形操作を繰り返します

手順の途中で、「タイルの間の辺を切ったり繋いだりして」という操作が出てきましたが、以下の図のような感じです:

  • まず、木でつながっている適当なタイルのペアの間の辺を切断します
  • そうすると木が二つに分かれます
  • 二つの木が隣接しているタイルのペアのどこかをつなぐと、元の木とは異なる新しい木ができます
    • ちなみに、辺を繋いでからループを切る方法でも結果は同じです。

このようにして全域木の状態を保ったまま、盤面に存在するタイルの種類の数を変更することができます。

もちろん、行き当たりばったりに辺を切ったり繋いだりしても、なかなか目的の状態(タイルの数が初期盤面と同じ)にはなりません。 そこで、辺を切ったり繋いだりする際に以下のような工夫をしました

  • (山登り法) 操作後の全域木のタイル数が、元の全域木の状態よりも目標に遠かったら操作をリジェクトする
  • 上記のリジェクト率を下げるために、以下のようにして切ったり繋いだりするタイルのペアを選択しました:
    • 辺を切ったり繋いだりするタイルのペアに選ばれると、操作後にはそのますは別の種類のタイルになります。 従って、辺を切ったり繋いだりするタイルのペアは、元の全域木では過剰な種類のタイルだと望ましいことになります。
    • こういう考えのもと、候補に選ばれるタイルのペアは過剰な種類のタイルを選びやすいようにしました。

ただ、袋小路にはまってしまうと抜け出せないことがあったので、適当な回数(300回とか)の操作で改善がなければ、木を切ったり繋いだりする操作を50回適当に行って盤面をリセットし、もう一度探索を開始させました。

以上のようなやり方で、早い時には一瞬で、悪い時でも数百ms程度で目標となる全域木が手に入りました。

完成予定図に合うようにタイルを動かす

タイルを動かしてパズルを解く際には以下の2つの方法を試しました:

  • ルールベースで完成予定図に合わせてタイルを動かしていく
    • ルールベースの方法はけんちょんさんの最近出た本(https://gihyo.jp/book/2022/978-4-297-12679-7)の15パズルの人間的解法を参考にしました。面白い本なので興味がある人はぜひ!
    • 上の方から一行ずつパズルを完成させる方法です
  • A*探索で上の方から一行ずつ完成させる

両方試したところ後者の方が良い点数を出せたのでそちらを採用しました。 ちなみにルールベースで解いていた時代の動画は以下のような感じです。端の2列を揃える方法が人間っぽくて可愛いですね。

以下では採用したA*探索の方法についてざっくり書いていこうと思います。

A*探索を使う

A*探索(エースター)を初めて知ったのはAtCoderの大昔の問題を解いていたときでした(https://atcoder.jp/contests/indeednow-quala/tasks/indeednow_2015_quala_4)。 これは15パズル(H*W-1パズル)を解けという直球の問題です。 24手以内に解けることが保証されているので、双方向探索によって解くと2*312 = 106くらいの計算回数で正解を見つけることができます(解説を参照)。twitterで誰かが言っていましたが、半分全列挙の親戚という表現がとてもわかりやすいです。 この公式解説の別解でA*探索について言及があって、こんな方法があるのかと印象に残っていました。

話がそれましたが、A*探索については他に優れた解説がたくさんあるのでこの記事では解説しません。 大雑把な理解では、ゴールに近そう(実際に近いかは必ずしもわからない)なところから優先して探索できるようにする方法です。 よくABCで使うDijkstra法は手数が小さいところから優先して探索する方法ですね。

A*探索で解く手順は以下のように行いました:

  • まず完成予定図に沿って、一番上の行から完成させていきます。
  • 左図のような完成予定図があったときに、中央図のように盤面のタイルの最終到達地点を決めて番号を振ります。
    • この際に移動距離が小さくなるように最小費用流を使いました
  • あとはタイルをランダムにスライドさせます。完成図に近い方から探索させるために、
(各タイルの到達予定地点からの距離の合計)*1.5 + それまでの手数

という指標を作り、これが小さい盤面から探索させました。このようにすることで、完成に近い盤面から集中して探索することができます。

  • 同じ状況を探索しないように盤面のhash値を計算して管理していました
  • なお、このスライドさせて探索させる時には右図のように関係のあるタイルだけを気にして動かしました。完成予定図の一番上の行に使われるタイル以外は全て同一視しています。このようにすることで出現する盤面の種類を減らすことができます。
  • また、上から5行目以降には空白のタイルをスライドさせないようにしました(つまり必要なタイルの揃っている行より下にはいかないようにしました)

また、探索の速度を上げるためのヒューリスティクスとして「各タイルの到達予定地点からの距離の合計」(以下距離)に関して

  • 探索する盤面は距離が(それまでに出た最小の距離 + 2)の盤面のみを探索する

ということをしていました。 こうすることで探索する盤面の候補が大きく減り、探索を高速に行うことができました。 当然、探索する盤面が減ると解の性能も落ちるので、探索時間とのトレードオフになります。

このような制限を入れたのは、A*探索では盤面を探索するたびに盤面のコピーが生じてコストが高く、極力探索する盤面を減らす必要があったためです。

盤面を捏造する

さて、1行ずつA*探索で盤面を完成させていくのですが、元の完成予定図通りに木を作る必要がないことに気が付きます。 このことを使って効率よく木を作ることができないでしょうか?

具体的には、上の図で②、④のタイルは一番上の行から離れたところにあって、一番上まで持っていくのが大変そうです。 本当は上の方に集まっているタイルだけで一番上の行を作りたいです。

そこで、完成図の方を改変して、実際の盤面の都合の良いように並び替えましょう。 具体的には、以下のような操作を行いました:

  • 完成予定図の一番上の行のタイルは、現在の盤面の上から3行だけのタイルを作って作れるようにしたい
  • 完成予定図の一番上の行のタイルで、現在の盤面の上の3行に存在しない種類のタイルを選択して、木の状態と周りと辺を繋いだり切ったりする
    • 一番上の行のタイルが、現在の盤面の上3行に存在しているタイルだけで構成できるようになるまで繰り返す
  • 前の操作が終わったら、各種類のタイルの数が盤面に存在しているタイルの種類と乖離しているので、2行目以降のタイルを切ったり繋いだりしてタイルの種類の数を合わせる(全域木を作るときと同様の操作)
    • この際に1行目と2行目の間に辺を作ったり切ったりしないように気をつける

最終的に以下のような感じになればOKです。 元の盤面に似ていますが、上から3行のタイルだけを使って一番上の行を構成できるようになっていることがわかると思います。

多くの場合にはこの操作が成功するのですが、たまに失敗することがあります。 そのような時には制限を緩めて4行、5行、...というような形で候補になるタイルの数を増やしました。

盤面を捏造するという表現はterryさんの表現が面白かったので借りてきました(https://www.terry-u16.net/entry/ahc011)。

上記の操作を繰り返して下から3行目までを完成させる。その後に下から2行をまとめて完成させる。

説明の都合上順番が逆になりましたが、

  • 完成予定の図を都合が良いように捏造する
  • A*探索で上の1行を完成させる

という操作を上から順番に行って、下から3行目までを完成させます。

残りの2行は同時に完成させないといけないのですが、これは2行を同時にA*探索で完成させました。 実際にはN=10の時などには探索時間の関係で左の4列を完成 -> 右の6列を完成というような手順を踏ませました。

なお、15パズルに特有のパリティの問題は、最後の2行まで行った時に辻褄を合わせられたらそれでOK、辻褄が合わなかったら諦めて最初からやり直させました。 多くの場合にはタイルの移動先をスワップすれば解決するので、実用上これで問題なさそうでした。

学びを得たこと

コンテスト中にいくつか学びを得たことを列挙していきます(多分色々な人が色々なところで言っていることですが...)。

問題を小さくして対処するといいことがある

複雑な問題をいくつかの小さい問題に分解してそれぞれを解けば良い、というデカルト以来の還元主義的な考え方がとてもうまくいきました。

今回では

  • 問題を全域木を作るパートと、盤面をそれに向かって合わせるパートに分解したこと
  • A*探索をするときに解く対象を1行に制限したこと

などがありました。 小さな問題はそもそも解きやすかったり、処理がモジュール化できて開発がしやすいということもあります。 難しい問題は小さく分割して各個撃破しましょう。

バグらせた時のために再現性を確保しよう

複雑なヒューリスティクスアルゴリズムを書いていると、数十回に一回だけバグるみたいなことがよく起きました。 どこの処理がまずいかを調べるために数十回プログラムを走らせてバグる乱数を引く、というようなことをやっていると日が暮れてしまいます。

これを避けるために、乱数の種は固定したり記録に残したりして、バグった時の状況を再現できるようにしましょう。 また、探索などの打ち切りを実行時間で制御していると、計算を走らせた時の負荷の状況で、乱数の種が同じでも処理結果が変わったりします。 このような状況を防ぐために、処理の打ち切りは実行回数で制御するようにしましょう(といってもそうはいかないかも...)。

探索をするときにはなんかうまくいくように条件をつけたり探索の方向を決めたりする

漠然とした話ですが、探索をするときに、探索がうまくいくようなイメージを条件としてつけて探索を実行させるとうまくいくことがありました。

例えば、全域木を作るパートで、

  • 辺を切ったり繋いだりするペアは過剰な種類のタイルを選ぶ

ということをやっていましたが、これで探索が早く進みました。

また、A*探索をする際に計算速度が遅くて困っていたのですが、探索する盤面を制限するために

  • 最小の距離 + 2の盤面だけを探索する

というような条件を入れました(あんまり性能が良いとは思っていませんが...)。 このことによって目論見通り計算が早く終わるようになりました。

何を当たり前のことを言っているんだという感じですが、試行錯誤しながらこうやったらうまくいくんじゃないかというアイデアを実装するというプロセスが大事なんだなあということを実感しました。

ぼんやりしているときに重要なアイデアが出てきた

最終的な解法のうち重要なアイデアはパソコンに向かっているときではなく、寝ようとしているときやシャワーを浴びているときに思い浮かびました。 これはどういう脳みそのメカニズムかわかりませんが、ぼんやりと考え事をしていると良いアイデアが浮かびました。

いつもそうではないと思うのですが、今回のコンテストの中で重要だった

はそういうときに浮かんだのでなんとなく印象に残っています。不思議なものですね。

アルゴリズムのコンテストの知識は有用でした

今回は

  • 最小費用流
  • hashで盤面の重複を管理
  • A*探索

などABCの知識がとても役に立ちました。 水色くらいまでの知識はダイレクトに効いてくる感じはあるような気がします。

改善できたなあと思うところ

上位の人たちと大筋の解法が似ているようなところはあったんですが、細かいところの詰めが甘く点数が上がり切りませんでした。 例えば(割とterryさんのアイデアが多いけど)

  • A*探索をするところはIDA*探索を使った方がよかったかも。双方向探索にしている人もいた。
  • 目標の木の候補をたくさんあらかじめ作っておいて、現在の盤面に近いものを採用する
  • 木を捏造する際に最小費用流ベースで良い目標を探す
  • 盤面を完成させていくのを上と横を繰り返す

というような感じです。 時間が足りなかったというのもあるけど、実装が複雑になってあまり多くのことを試せなかったというのもあると思います。この辺りがマラソンの実力という気がしています。 そういう点では単体テストをたくさん入れた方がよかったかもしれません。1週間のコンテストならTDDをやってもペイするような気がします。

また、時間管理が適当でやり方をもうちょっと考えなければいけませんでした。平均が2.5msくらいで、システスの3000問のうち2問でTLEが起きていました... これも時間計測を最初のうちに考えずに実装していて、後から指定するのが難しくなった(というかめんどくさくなった)という状況でした。

感想

とてもシンプルな問題でしたが、さまざまな改善方法が思いついて、それを試していくのがとても楽しかったです! 上に書いたこと以外にも色々やってみてうまくいかなかったんですが、その過程も結構楽しかったです。 また、割と理詰めの発想で良さそうな方針に辿り着けたのは自信につながりました。

今回参加してとても楽しかったので次回以降も出れるように頑張りたいと思います。AHCがもっと盛んになりますように!

*1:だから「両方」やってしまうブチャラティはかっこいい