AtCoder Heuristic Contest 011

暫定65位(37.2M点)、最終も65位(2.23B点)の者の思考過程と試行過程です。

問題概要

A - Sliding Tree Puzzle

  • N \times N (6 \leq N \leq 10)の大きさのスライドパズルを完成させよ。
  • N^2-1枚のタイルには15種類のいずれかの線(4方向のありなしの組み合わせで表されるもの)が描かれており、正しく揃えれば全体が1つの木になる。
  • 1つだけある空きマスを最大T=2 \times N^3回移動させることができ、その移動方法をT文字以内の"U", "D", "L", "R"からなる文字列で出力する。
  • 出力の通りに動かした結果、最大の木の大きさがN^2-1未満の場合は、その大きさに比例した得点(0500000)が得られる。
  • サイズN^2-1の木を完成させられた場合は、手数が短いほど高得点(T0手 → 5000001000000点)。

1~2日目

  • 問題だけ読んでから昼食。一瞬AHC010かと思った。
  • 最初の30分~1時間くらいは何をしたらいいか全然わからなかった。
  • その後、完成形を決めるパートとその通りに動かすパートに分けて考えることにする。

完成形を決めるパート

  • 単純に現時点の最大連結成分のサイズとかで山登りや焼きなましをしたのでは、AHC010と同様に全然上手くいく気がしない。
  • seed=0の内容でジグソーパズルのように埋めていくことを手作業で試していたら、最初に十字型を適当に真ん中に置いて線が繋がるように伸ばしていく方法を思い付く。
  • 実装はBFSで、次のタイルとして可能なものかつ枝分かれの多いものから優先的に使用するようにした。
  • 可能なものの判定は、遷移元と線が繋がり、遷移先がさらにその先と別の線で繋がらず、他の既存タイルや壁とは線のない辺で接するといったところ。
  • これだけでおよそ89割の大きさを持った連結成分ができていた。
     
  • あと、上記の配置可能判定ではNGでも、まだ露出している木の葉は何箇所か残っており、1枚分伸ばせるような箇所もあったので、それらを適当に1枚伸ばし、それでも埋まらない部分は余ったタイルを順番に埋めた。
  • 完成率は平均9割程度で、全部この通りに動かすことができれば22.5M点前後が期待できそう。

完成形まで動かすパート

  • 決めるパートができても、動かすパートができなければ提出することもできない。とりあえず15パズルの解法を調べたりしてみる。
  • A*を使った方法が出てきたりもしたが、多分かなり色々な工夫をしないと実行時間がいくらあっても足りない雰囲気を感じたので、上位は多分使ってくるんだろうけど自分のレベル感では端から順に揃えていくのが精々かなと判断。
  • 「端から順に」の順番だが、これは完成形で空きマスがある行or列を避けて1行or1列ずつ埋めていくことにする。ABC232-H - King's Tourとほぼ同じように、2\times 2列になるまで1行or1列ずつ減らしていく形。
  • 上記の問題とは違って全部一筆書きにする必要はないが、1行を埋めるのに最後の2マスが厄介。基本的にはまず以下の2通りのどちらかの形を目指すことになるが、直感的に右の方が扱いやすそうな気がしたので、1~4を揃えた後は5, 6をそちらの位置に動かすことにした。
12346.    1234.5
....5.    .....6
  • 上記の1~6に対応するタイルは、該当する形のタイルで最も近いもの(斜め\times 3、縦横\times 5な感じで計算)を選択し、既に移動を終えているマスを崩さないように移動させていく。
  • 移動のさせ方は、タイルを次に移動させたいマスに空きマスを移動させればよいので、タイルの移動先マスまでBFSをして経路復元をする。だいたい移動させたいタイルを回り込む動きになる。
     
  • 場合分けは大変になるが、遅くなるような気がしたので(実際どうかはわからないけど)、1行処理する度に盤面を回転させるようなことはしないことにした。
  • それで同じような実装が2つになったのはともかくとしても、「123465」の順に並んでしまった場合など、細かいコーナーケースが色々あってなかなか上手くいかなかった。*1
  • 結局2日目が終わる頃になってようやく動くものができた。まだ最後の4マスを揃える処理が未実装だけど心の平穏のために一旦提出。 →21.9M点。

 

3日目

最後の4マス

  • 最後の4マスを揃える実装をする。手作業で試すと12回動くと元に戻ったので、右回りに12回動いて一致したら終了する。7回以上動くなら左回りの方が早いが、それは煮詰まった時にでもやることにして一旦後回し。

完成形を決めるパート(案2)

  • 最後の2マスが逆になってしまう場合を除けばとりあえず完成形通りに動かせるようになったので、そうしたら次は木の完成率を上げないことには点数アップには繋がらない。
  • 初日のBFS案を改善するか全く別の方法をするかを考え、ここで入力の生成方法が目に付く。
  • 縦線と横線の本数は決まっているので、それだけ決め打ちして入力の生成方法と同じようなことをしてみる。seed=0であれば、縦線をランダムな順番に19本引いた後に、閉路ができないように横線をランダムな順番に15本引く。
  • 縦線は各行に必ず1本は必要であることから(横線も同じ)、最初に中央に大きく十字線を決め打ちしてから残りをランダムとした。
  • 空きマスが作られないケースが多発したので、空きマスが1つ残るように判定を頑張ろうとしたが、なかなか上手くいかないので一番左上を必ず空きマスとするようにした。
  • これだけでもN=6のケースはそれなりに高い確率で木が完成していたが、N=10のケースは全く駄目。
  • とりあえずこの乱択案で完成すればそれで、完成しなければ初日のBFS案を使うようにした。 →23.4M点。

 

4~6日目

平日真っ只中であまり時間が取れなくなってくる。

多点スタート

  • 簡単にできることとして、BFS案の初期マスを外周以外全て試し、乱択案も十字を作る位置を両端22列以外でランダムに変更してみる。 →24M点台に。

最後の2マスが逆

  • そろそろ最後の2マスが逆になってしまって完成しないケースをどうにかしたい。
  • 確率は\frac{1}{2}なので、動かすパートにちょっとランダム要素が加われば試行回数次第でクリアできるのではないか。
  • 最も近いタイルを選ぶところを、最短距離を更新したら選ぶものを変えるようにしていたが、確率\frac{1}{2}で同じ距離でも変更したり、確率\frac{1}{5}くらいで距離が1悪くても変更したりといったことをしてみたら、確実とは言えないまでもだいたいはいけそうな感じ。

手数オーバー

  • 2日目時点ではだいたい収まっていそうに思えたが、今度は出力がT文字を超えるケースが無視できなくなってきた。
  • とはいえ木の完成率を上げることの方が先なので、一旦はT文字で切って出力する対応とする。

 

7日目

どうせいつかは取る必要がある有休をAHCのために取得し、金曜日だが昼間からやっていく。

手数削減案

  • 木の完成率を上げる方が先と言いつつも、簡単にできそうな手数を減らす案をまず試してみる。
  • 初期状態と完成形の各タイルを適当に貪欲にマッチングさせ、特にどこかのマスを揃えようとはせず適当に動かしてマッチングさせたタイルのマンハッタン距離が縮まるなら、その操作(以下「基本移動」と呼ぶ)を行ってから動かすパートをスタートさせる。
  • 動かすパートは基本移動前スタートと後スタート両方を同じ回数くらい試す。
  • 基本移動の条件が厳しくてほとんど移動できなかったが、改善することもあったので一応採用。 →25M点台に。

完成形を決めるパート(案2)の改善

初期解の見直し(いらなかった)
  • 3日目の乱択案は言わば山登りの初期解の時点で既に成功していることもあるような状態なので、もう少し初期解に条件を増やしたら確率が高まるのではないか?
  • 線を増やしていく際、増やした後のタイルの形の残数に余裕があるかどうかを調べるようにしてみる。例えば3の形をしたタイルに下側の線を引こうとした時に、そのタイルが今後取り得る形のbとfが既に使い切られていたら引けないといった具合。
  • 確率は若干高まった気がする程度。そもそも規定数の線を引き切れないケースも発生する。
初期解に変更を加える(当たり方針)
  • 縦線と横線の数は変更したくないので、まず縦線を向きを変えずに1本移動させることを試す。
  • 縦線を1本移動させると、移動元の上下2タイルと移動先の上下2タイルの4タイルの形が変化する。
  • 移動元としては上下とも目的の数より多くなっている形のタイルで構成されている部分を選択し、移動先としては木構造が保たれることを必須条件として、線を追加する前の形が過多、線を追加した後の形が過少であることにポイントを付け(最大4ポイント)、ポイントが最も高い箇所に移動させる。
  • 例えば下図の状態で仮に形bとfが共に過多であったとすると、赤丸部分の縦線を木構造が保たれる青線のいずれかの位置に移動させる。
  • 移動先の評価例としては、仮に2と5が過多でaが過少、7が同数であったとすると、真ん中の青線が3ポイントとなる。

  • 縦線を移動させるようにしただけでも8割以上は完成するようになった感じ。
調整等
  • 横線の移動も実装し、移動元として2タイルとも過多の部分が存在しなければ片方のみ過多でも許容したりして、どんどん確率が高まっていく。
  • 初期解が完成しない割合が大きいので初期解作成時の残数チェックを外したら、完成形が見つかるまでの時間が縮まった。
  • あとは移動を何回試して完成しなかったら諦めて最初からやり直すかといったパラメータ調整をした。
  • この時点で(最終的にも変わっていないが)、seed=0~99の中ではseed=42だけ極端に成功率が低く、2500ms以内に見つかる確率が半々~甘く見て7割といったところ。
  • とはいえこれで木の完成率が99\%以上にはなった感じ。 →一気に33.0M点に。
     
  • 完成しなかった時の保険にBFS案は残してあるが、もうこちらの改善は考えないことにして、あとは手数を削減する方法を考えることに集中する。

 

8日目

より良い完成形の選択

  • 完成形はseed=42のように1つ得られるかどうかなケースもあれば、数百個も得られているケースもある状態。
  • 7日目で基本移動をしようとしているくらいなら、そもそも最初からマンハッタン距離の総和が最も小さいものを完成形として選ぶようにすればよい。 →34M点台に。

細かい改善

  • 完成形を何百個も得ても仕方ないので、総距離がより短い解を得られない状態が数十回続いたら打ち切り、動かすパートに使える時間を増やすようにする。
  • 総距離が最小のものだけ動かすパートを試すのももったいないので、良いものから最大10個程度の完成形を残しておいて全部試すようにする。
  • 基本移動が、1手で総距離-1の時しか移動できないようになっていたが、奇数手で-1(成功の度リセット)である限り続け、偶数手で+2なら終了させる。
  • 基本移動が50手以上とか長く続く場合があったため、最大N回程度に抑える。
  • 動かすパートで、空きマスをタイルの移動先マスまで動かすルート(タイルのどちら側から回り込むか)を決める要素に他のタイルがマッチング先に近付くかも盛り込み、BFSからダイクストラ法に変更する。
  • 3日目から放置していた最後の4マスの左回りを実装する。 →何かする度に0.2M点ずつくらい上がって35M点台に。

ビームサーチ

  • 完成形の候補に限らず、動かすパートの中でも1行揃えるごととか、タイル1枚を揃えるごととか、タイル1枚を1マス移動させるごととかに上位何パターンかを残していくの、この問題では有効なのではないかとふと思い付く。というか、試さずに捨てているようなところをなるべく全部試すようなことくらいしか、できそうなことがなかった。
  • ビームサーチをまともに実装したことがないのでどうするのがいいのかは全然わかっていないが、以下のことをするくらいでなんとなくそれらしいものはできそう?
    • 盤面状態を再現できる情報と優劣を判断できる情報を持ったオブジェクトを作る。
    • 次の手が枝分かれする際にはディープコピーで新しいオブジェクトを作る。
    • 盤面状態が悪い順に取り出せるPriorityQueueを用意し、ビーム幅を超える数が格納されたらその分捨てる。
  • とりあえず今できている実装の中で簡単に変えられそうなところで、まず最も近いタイルを選ぶところで近いタイル最大3枚を試すようにする。まだ結果は最良のものしか保持しないが、手始めとして。

TLE対策

  • ビームサーチを取り入れていこうと決めてからまだ大した変更をしていないと思われるのに急にTLEが発生。しかも3310msなのでぎりぎり3000msを超えたわけでもなさそう。
  • 手元では200ケース試しても全て2800msくらいに収まっているのに、50ケース中10ケースも。
  • どうやら2日目に作った1行の最後の2枚を揃える部分にまだ穴があり、最も近いタイルのみなら基本的に問題なかったのが、2, 3番目も調べると動かしようがなくなってしまったりするようだった。
  • 最終日はそれを解消したつもりで、さらに完成形探索パートや動かすパートの打ち切り時間を100200ms早めたりしても何故かほとんど変わらず2900ms台の提出が続くことになる。

 

9日目(最終日)

ビームサーチ等の続き

  • 動かすパート中の1行揃えたタイミング、タイル1枚を揃えたタイミングで上位数件(変更できるようにしておく)を保持するように変更。
  • 動かし始める前に決めた初期状態と完成形とのマッチングは、動かし始めるとマッチングした通りに揃えているとは限らないため、1行揃えるごとくらいで適当にやり直す。
  • 今度は手元でも4000msとかかかっているケースが出てくる。
  • 普通に動かすパートの試行1回で1秒以上かかっているようなので、時間を計測して打ち切る処理を1行揃えるごとのタイミングにも入れておく。ただし、TLEになろうとも1回は完遂させる。 →37.2M点。
  • 打ち切り判定のタイミングを細かくして、手元では2700ms以上が1つもないくらいなのに、提出するとまだ2900ms台ばかり。原因さっぱりわからないが、せめて2800ms台にはしておかないとシステムテストが心配すぎる。でも打ち切りを少し早めただけでも明らかに点数下がっている。

高速化?

  • とりあえず思い付くところで、二次元配列を一次元にした。
  • 二次元のboolean型配列は、一次元のint型配列のビット演算にしてみた。
  • 実際に早くなったかどうかはちゃんと確認していない。多分あまり変わっていない。

パラメータ調整

  • ビームサーチで上位何件残すかと、8日目の細かい改善1点目で何回連続上位X件に入れ替わりがなかったら打ち切るかについて色々試した。
  • ビームサーチの保持件数は1015程度までは増やすほど明らかに得点上がりそうだったが、特にN=10では1増やすだけでも結構TLEリスクが増しそうな動きをしていて、最終的にN=610に対して104くらいになった。*2
  • 最終日の午後はほぼ30分置きに提出していたが、この段階に入ってからは提出する度に点数が下がっていった。TLEへの恐怖から甘めにならざるを得なかった。
  • 37.2M→36.6Mと徐々に下がっていく中で、残り1時間切ったところで36.9Mと少し上向き、かつ2893msと調整段階に入って初めての2900ms切りが出たので、あともう1回再提出のチャンスはあったがこれを最終提出とする。

最終提出(36,923,047点)
 


暫定結果:37,227,820点、65位(最終提出のものだと68位)
終結果:2,231,713,503点、65位、パフォーマンス2100相当
レート変動:1830→1882(+52)
 

終了後、その他

後回しにしていた実装を1つ忘れていたことに気付く。
主に1行の最後の2枚を揃える辺りで、場合によっては左に動かした直後に右に戻すような手順が発生することが考えられたので、最後に"LR"他3種類を空文字列に一括置換しようと思っていた。
 

AHC終了2時間後からABCとかがなかったので、溜まった録画でものんびり消化しようと思っていたが、こんな記事を5時間以上かけて書いてしまっていた。

あとはとりあえずシステムテストでTLEが出ないことを祈るのみ。
終結果等の記載は判明し次第更新する予定。

⇒最終提出の60倍(2.215B)よりは大きく、暫定最高点の60倍(2.233B)よりはわずかに小さかった。
実行時間は2980msでTLEは出なかったので、TLE回避の面では良い判断をしたと思う。
 

今回使ったものはだいたいこんな感じ?

  • BFSやダイクストラに毛が生えたものと経路復元
  • 完成形を作るパートや得点計算での連結判定にUnionFind(閉路検出はサボった)
  • 1行or1列揃えてより小さい部分問題に帰着させるという実装方法
  • 完成形を作るパートで山登りもどき(下がったら戻すのではなく登れなかったら終了しているだけ)
  • ビームサーチ(ちゃんとできているのか怪しい)

あとは、ちょっと条件付けて乱択するだけで意外と簡単に完成形が見つかるものだったということを発見できるかどうかが、この問題最大の肝だったのではないかと思う。

AHCではそれぞれの問題で重要なところを外さなければ、なんかよくわからない数学や統計学などの知識がなくても、青上位~黄下位くらいまでは狙える感じ。

*1:後から思えば、5と6を先に動かした後に1~4を動かせばハマらなかったかも。

*2:ビーム幅1000とか言っている人がいて、自分がやっているのはビームサーチではないのではないかと思えて仕方ない。まあ初心者だけど。