AtCoder Heuristic Contest 011
暫定65位(37.2M点)、最終も65位(2.23B点)の者の思考過程と試行過程です。
問題概要
- の大きさのスライドパズルを完成させよ。
- 枚のタイルには種類のいずれかの線(方向のありなしの組み合わせで表されるもの)が描かれており、正しく揃えれば全体がつの木になる。
- つだけある空きマスを最大回移動させることができ、その移動方法を文字以内の"U", "D", "L", "R"からなる文字列で出力する。
- 出力の通りに動かした結果、最大の木の大きさが未満の場合は、その大きさに比例した得点(~)が得られる。
- サイズの木を完成させられた場合は、手数が短いほど高得点(~手 → ~点)。
1~2日目
- 問題だけ読んでから昼食。一瞬AHC010かと思った。
- 最初の分~時間くらいは何をしたらいいか全然わからなかった。
- その後、完成形を決めるパートとその通りに動かすパートに分けて考えることにする。
完成形を決めるパート
- 単純に現時点の最大連結成分のサイズとかで山登りや焼きなましをしたのでは、AHC010と同様に全然上手くいく気がしない。
- seed=0の内容でジグソーパズルのように埋めていくことを手作業で試していたら、最初に十字型を適当に真ん中に置いて線が繋がるように伸ばしていく方法を思い付く。
- 実装はBFSで、次のタイルとして可能なものかつ枝分かれの多いものから優先的に使用するようにした。
- 可能なものの判定は、遷移元と線が繋がり、遷移先がさらにその先と別の線で繋がらず、他の既存タイルや壁とは線のない辺で接するといったところ。
- これだけでおよそ~割の大きさを持った連結成分ができていた。
- あと、上記の配置可能判定ではNGでも、まだ露出している木の葉は何箇所か残っており、枚分伸ばせるような箇所もあったので、それらを適当に枚伸ばし、それでも埋まらない部分は余ったタイルを順番に埋めた。
- 完成率は平均割程度で、全部この通りに動かすことができればM点前後が期待できそう。
完成形まで動かすパート
- 決めるパートができても、動かすパートができなければ提出することもできない。とりあえず15パズルの解法を調べたりしてみる。
- A*を使った方法が出てきたりもしたが、多分かなり色々な工夫をしないと実行時間がいくらあっても足りない雰囲気を感じたので、上位は多分使ってくるんだろうけど自分のレベル感では端から順に揃えていくのが精々かなと判断。
- 「端から順に」の順番だが、これは完成形で空きマスがある行or列を避けて行or列ずつ埋めていくことにする。ABC232-H - King's Tourとほぼ同じように、行列になるまで行or列ずつ減らしていく形。
- 上記の問題とは違って全部一筆書きにする必要はないが、行を埋めるのに最後のマスが厄介。基本的にはまず以下の通りのどちらかの形を目指すことになるが、直感的に右の方が扱いやすそうな気がしたので、1~4を揃えた後は5, 6をそちらの位置に動かすことにした。
12346. 1234.5 ....5. .....6
- 上記の1~6に対応するタイルは、該当する形のタイルで最も近いもの(斜め、縦横な感じで計算)を選択し、既に移動を終えているマスを崩さないように移動させていく。
- 移動のさせ方は、タイルを次に移動させたいマスに空きマスを移動させればよいので、タイルの移動先マスまでBFSをして経路復元をする。だいたい移動させたいタイルを回り込む動きになる。
- 場合分けは大変になるが、遅くなるような気がしたので(実際どうかはわからないけど)、行処理する度に盤面を回転させるようなことはしないことにした。
- それで同じような実装がつになったのはともかくとしても、「123465」の順に並んでしまった場合など、細かいコーナーケースが色々あってなかなか上手くいかなかった。*1
- 結局日目が終わる頃になってようやく動くものができた。まだ最後のマスを揃える処理が未実装だけど心の平穏のために一旦提出。 →M点。
3日目
最後の4マス
- 最後のマスを揃える実装をする。手作業で試すと回動くと元に戻ったので、右回りに回動いて一致したら終了する。回以上動くなら左回りの方が早いが、それは煮詰まった時にでもやることにして一旦後回し。
完成形を決めるパート(案2)
- 最後のマスが逆になってしまう場合を除けばとりあえず完成形通りに動かせるようになったので、そうしたら次は木の完成率を上げないことには点数アップには繋がらない。
- 初日のBFS案を改善するか全く別の方法をするかを考え、ここで入力の生成方法が目に付く。
- 縦線と横線の本数は決まっているので、それだけ決め打ちして入力の生成方法と同じようなことをしてみる。seed=0であれば、縦線をランダムな順番に本引いた後に、閉路ができないように横線をランダムな順番に本引く。
- 縦線は各行に必ず本は必要であることから(横線も同じ)、最初に中央に大きく十字線を決め打ちしてから残りをランダムとした。
- 空きマスが作られないケースが多発したので、空きマスがつ残るように判定を頑張ろうとしたが、なかなか上手くいかないので一番左上を必ず空きマスとするようにした。
- これだけでものケースはそれなりに高い確率で木が完成していたが、のケースは全く駄目。
- とりあえずこの乱択案で完成すればそれで、完成しなければ初日のBFS案を使うようにした。 →M点。
4~6日目
平日真っ只中であまり時間が取れなくなってくる。
多点スタート
- 簡単にできることとして、BFS案の初期マスを外周以外全て試し、乱択案も十字を作る位置を両端行列以外でランダムに変更してみる。 →M点台に。
最後の2マスが逆
- そろそろ最後のマスが逆になってしまって完成しないケースをどうにかしたい。
- 確率はなので、動かすパートにちょっとランダム要素が加われば試行回数次第でクリアできるのではないか。
- 最も近いタイルを選ぶところを、最短距離を更新したら選ぶものを変えるようにしていたが、確率で同じ距離でも変更したり、確率くらいで距離が悪くても変更したりといったことをしてみたら、確実とは言えないまでもだいたいはいけそうな感じ。
手数オーバー
- 日目時点ではだいたい収まっていそうに思えたが、今度は出力が文字を超えるケースが無視できなくなってきた。
- とはいえ木の完成率を上げることの方が先なので、一旦は文字で切って出力する対応とする。
7日目
どうせいつかは取る必要がある有休をAHCのために取得し、金曜日だが昼間からやっていく。
手数削減案
- 木の完成率を上げる方が先と言いつつも、簡単にできそうな手数を減らす案をまず試してみる。
- 初期状態と完成形の各タイルを適当に貪欲にマッチングさせ、特にどこかのマスを揃えようとはせず適当に動かしてマッチングさせたタイルのマンハッタン距離が縮まるなら、その操作(以下「基本移動」と呼ぶ)を行ってから動かすパートをスタートさせる。
- 動かすパートは基本移動前スタートと後スタート両方を同じ回数くらい試す。
- 基本移動の条件が厳しくてほとんど移動できなかったが、改善することもあったので一応採用。 →M点台に。
完成形を決めるパート(案2)の改善
初期解の見直し(いらなかった)
- 3日目の乱択案は言わば山登りの初期解の時点で既に成功していることもあるような状態なので、もう少し初期解に条件を増やしたら確率が高まるのではないか?
- 線を増やしていく際、増やした後のタイルの形の残数に余裕があるかどうかを調べるようにしてみる。例えば3の形をしたタイルに下側の線を引こうとした時に、そのタイルが今後取り得る形のbとfが既に使い切られていたら引けないといった具合。
- 確率は若干高まった気がする程度。そもそも規定数の線を引き切れないケースも発生する。
初期解に変更を加える(当たり方針)
- 縦線と横線の数は変更したくないので、まず縦線を向きを変えずに本移動させることを試す。
- 縦線を本移動させると、移動元の上下タイルと移動先の上下タイルのタイルの形が変化する。
- 移動元としては上下とも目的の数より多くなっている形のタイルで構成されている部分を選択し、移動先としては木構造が保たれることを必須条件として、線を追加する前の形が過多、線を追加した後の形が過少であることにポイントを付け(最大ポイント)、ポイントが最も高い箇所に移動させる。
- 例えば下図の状態で仮に形bとfが共に過多であったとすると、赤丸部分の縦線を木構造が保たれる青線のいずれかの位置に移動させる。
- 移動先の評価例としては、仮に2と5が過多でaが過少、7が同数であったとすると、真ん中の青線がポイントとなる。
- 縦線を移動させるようにしただけでも割以上は完成するようになった感じ。
調整等
- 横線の移動も実装し、移動元としてタイルとも過多の部分が存在しなければ片方のみ過多でも許容したりして、どんどん確率が高まっていく。
- 初期解が完成しない割合が大きいので初期解作成時の残数チェックを外したら、完成形が見つかるまでの時間が縮まった。
- あとは移動を何回試して完成しなかったら諦めて最初からやり直すかといったパラメータ調整をした。
- この時点で(最終的にも変わっていないが)、seed=0~99の中ではseed=42だけ極端に成功率が低く、ms以内に見つかる確率が半々~甘く見て割といったところ。
- とはいえこれで木の完成率が以上にはなった感じ。 →一気にM点に。
- 完成しなかった時の保険にBFS案は残してあるが、もうこちらの改善は考えないことにして、あとは手数を削減する方法を考えることに集中する。
8日目
より良い完成形の選択
- 完成形はseed=42のようにつ得られるかどうかなケースもあれば、数百個も得られているケースもある状態。
- 日目で基本移動をしようとしているくらいなら、そもそも最初からマンハッタン距離の総和が最も小さいものを完成形として選ぶようにすればよい。 →M点台に。
細かい改善
- 完成形を何百個も得ても仕方ないので、総距離がより短い解を得られない状態が数十回続いたら打ち切り、動かすパートに使える時間を増やすようにする。
- 総距離が最小のものだけ動かすパートを試すのももったいないので、良いものから最大個程度の完成形を残しておいて全部試すようにする。
- 基本移動が、手で総距離の時しか移動できないようになっていたが、奇数手で(成功の度リセット)である限り続け、偶数手でなら終了させる。
- 基本移動が手以上とか長く続く場合があったため、最大回程度に抑える。
- 動かすパートで、空きマスをタイルの移動先マスまで動かすルート(タイルのどちら側から回り込むか)を決める要素に他のタイルがマッチング先に近付くかも盛り込み、BFSからダイクストラ法に変更する。
- 日目から放置していた最後のマスの左回りを実装する。 →何かする度にM点ずつくらい上がってM点台に。
ビームサーチ
- 完成形の候補に限らず、動かすパートの中でも行揃えるごととか、タイル枚を揃えるごととか、タイル枚をマス移動させるごととかに上位何パターンかを残していくの、この問題では有効なのではないかとふと思い付く。というか、試さずに捨てているようなところをなるべく全部試すようなことくらいしか、できそうなことがなかった。
- ビームサーチをまともに実装したことがないのでどうするのがいいのかは全然わかっていないが、以下のことをするくらいでなんとなくそれらしいものはできそう?
- 盤面状態を再現できる情報と優劣を判断できる情報を持ったオブジェクトを作る。
- 次の手が枝分かれする際にはディープコピーで新しいオブジェクトを作る。
- 盤面状態が悪い順に取り出せるPriorityQueueを用意し、ビーム幅を超える数が格納されたらその分捨てる。
- とりあえず今できている実装の中で簡単に変えられそうなところで、まず最も近いタイルを選ぶところで近いタイル最大枚を試すようにする。まだ結果は最良のものしか保持しないが、手始めとして。
TLE対策
- ビームサーチを取り入れていこうと決めてからまだ大した変更をしていないと思われるのに急にTLEが発生。しかもmsなのでぎりぎりmsを超えたわけでもなさそう。
- 手元ではケース試しても全てmsくらいに収まっているのに、ケース中ケースも。
- どうやら日目に作った行の最後の枚を揃える部分にまだ穴があり、最も近いタイルのみなら基本的に問題なかったのが、番目も調べると動かしようがなくなってしまったりするようだった。
- 最終日はそれを解消したつもりで、さらに完成形探索パートや動かすパートの打ち切り時間を~ms早めたりしても何故かほとんど変わらずms台の提出が続くことになる。
9日目(最終日)
ビームサーチ等の続き
- 動かすパート中の行揃えたタイミング、タイル枚を揃えたタイミングで上位数件(変更できるようにしておく)を保持するように変更。
- 動かし始める前に決めた初期状態と完成形とのマッチングは、動かし始めるとマッチングした通りに揃えているとは限らないため、行揃えるごとくらいで適当にやり直す。
- 今度は手元でもmsとかかかっているケースが出てくる。
- 普通に動かすパートの試行回で秒以上かかっているようなので、時間を計測して打ち切る処理を行揃えるごとのタイミングにも入れておく。ただし、TLEになろうとも回は完遂させる。 →M点。
- 打ち切り判定のタイミングを細かくして、手元ではms以上がつもないくらいなのに、提出するとまだms台ばかり。原因さっぱりわからないが、せめてms台にはしておかないとシステムテストが心配すぎる。でも打ち切りを少し早めただけでも明らかに点数下がっている。
高速化?
- とりあえず思い付くところで、二次元配列を一次元にした。
- 二次元のboolean型配列は、一次元のint型配列のビット演算にしてみた。
- 実際に早くなったかどうかはちゃんと確認していない。多分あまり変わっていない。
パラメータ調整
- ビームサーチで上位何件残すかと、日目の細かい改善点目で何回連続上位件に入れ替わりがなかったら打ち切るかについて色々試した。
- ビームサーチの保持件数は~程度までは増やすほど明らかに得点上がりそうだったが、特にでは増やすだけでも結構TLEリスクが増しそうな動きをしていて、最終的に~に対して~くらいになった。*2
- 最終日の午後はほぼ分置きに提出していたが、この段階に入ってからは提出する度に点数が下がっていった。TLEへの恐怖から甘めにならざるを得なかった。
- M→Mと徐々に下がっていく中で、残り時間切ったところでMと少し上向き、かつmsと調整段階に入って初めてのms切りが出たので、あともう回再提出のチャンスはあったがこれを最終提出とする。
暫定結果:37,227,820点、65位(最終提出のものだと68位)
最終結果:2,231,713,503点、65位、パフォーマンス2100相当
レート変動:1830→1882(+52)
終了後、その他
後回しにしていた実装をつ忘れていたことに気付く。
主に行の最後の枚を揃える辺りで、場合によっては左に動かした直後に右に戻すような手順が発生することが考えられたので、最後に"LR"他種類を空文字列に一括置換しようと思っていた。
AHC終了時間後からABCとかがなかったので、溜まった録画でものんびり消化しようと思っていたが、こんな記事を時間以上かけて書いてしまっていた。
あとはとりあえずシステムテストでTLEが出ないことを祈るのみ。
最終結果等の記載は判明し次第更新する予定。
⇒最終提出の倍(B)よりは大きく、暫定最高点の倍(B)よりはわずかに小さかった。
実行時間はmsでTLEは出なかったので、TLE回避の面では良い判断をしたと思う。
今回使ったものはだいたいこんな感じ?
- BFSやダイクストラに毛が生えたものと経路復元
- 完成形を作るパートや得点計算での連結判定にUnionFind(閉路検出はサボった)
- 行or列揃えてより小さい部分問題に帰着させるという実装方法
- 完成形を作るパートで山登りもどき(下がったら戻すのではなく登れなかったら終了しているだけ)
- ビームサーチ(ちゃんとできているのか怪しい)
あとは、ちょっと条件付けて乱択するだけで意外と簡単に完成形が見つかるものだったということを発見できるかどうかが、この問題最大の肝だったのではないかと思う。
AHCではそれぞれの問題で重要なところを外さなければ、なんかよくわからない数学や統計学などの知識がなくても、青上位~黄下位くらいまでは狙える感じ。