AHC011日記
はじめに
AHC011お疲れさまでした
僕は二度目のRated長期AHCでAHC008の時に思うように点が取れず悔しい思いをしていたのでリベンジだと思ってやっていたのですが暫定88位程度となりました
やりたいことはほぼほぼできていたのですが思うように点が伸びず結果は35Mどまりとなってしまいました
今回は毎日日記的なものをつけていたのでそれをもとにどのように解いていったのかを解説していきたいと思います
問題文の概要
木のスライドパズルをできるだけ少ない手で大きく作る！
一日目
最初の提出
まずは自明な解を提出しました
何の操作もしないことです
得点は2869199点でした
この時点でとりあえず入力の受け取りからの盤面の整数値への変換を作っておいて今後何かするときにすぐ取り掛かれるようにしておきました
実行環境の整備
ローカルテストを何ケースか同時に使用できるようにしました。
作り方自体はAHC008の時と変わらずpython からsubprocessを使って同時に実行できるようにするものです
方針決め
この時点では二つの候補で考えてました
1 . 完成図を作る→移動方法を考える
2 . 現在の盤面から木が大きくなるように移動していって木を作る
点数が伸びやすそうなのは1の方ですが完成図が作り終わる前に実行時間が終わってしまうことも考えとりあえず木を時間制限内に確実に作れるのか試していくことに決めました
考察
完成図を作るときに愚直に埋めていってしまうと計算量が莫大になってしまうのでdfsで途中の詰んだところで打ち切ったりすることで計算量を出来るだけ落とすことを考えました。制約より右下に空白のパネルを置いていいので右下からdfsを回すことにしました
2日目
実装
とりあえず昨日の考察をもとに完成図を作り出そうと実装していきました
木ができるとき連結できていないものはないので各マスごとに隣とつなげられるものだけを置いていき完成図が作られるようにしました
結果として6*6の場合ですがかなり高速に一つ目の解を見つけることができていたので10*10でもまぁ何とかなると思っていました
考察
完成図が作り終えたとき今回の問題はスライドパズルをいかに短い手で解くことができるのかという問題に置き換わるので今日はスライドパズルの解法について考えていきます
まず最終的に空白は右下の方に来るのでマスは右上から順に埋めていくのがいいと考えました
また、一般的なスライドパズル（15パズルなど）には詰みの盤面というのがあり奇置換の時そのパズルは完成させることができないのですが今回のパズルでは同じ模様のマスが確実に存在するので番号を振っていき詰むのであれば同じ模様のものの番号を一つ入れ替えるという風にすればいいと考察しました。（番号は完成型をもとに上から順につけていく）
3日目
学校のスタート
平日は学校があり、パソコンと向き合える時間も減るので考察に力を入れました
今日は高速に木を作る方法について考えました
まずますを置いていく方法は右下から縦に行き次に横のマスに行くという順にしました
すると、下の図の地点Aについて考えるときには下と右からのびているのでその方向には確定で伸ばし、左と上は自由に伸ばせます
また、地点Bについて考えると下には連結せず右のみと連結すればいいことになります。そして一つ上に伸ばすとしたら一つ上のマスに置くときに確実にサイクルが誕生してしまうので上には伸ばせません
このようにして枝刈りをしていくことによって高速に木を作り出すことができます
4日目
今日は完成図を作り終えるところまでやりました。またそれを使えば何通りの全域木を作れるかを調べられると思ったのですが60秒間動かしても終わらずそのタイミングで45000個はあることを確認しました(こんな多いことある？)
間に合わないケースもあるもののほとんどのケースで間に合わせることができているのでかなり満足です
高速化を進めたりすることで作り切れない量を減らしていくのがへ実の課題かなと思ってます
また、移動方法なども実装してないのでまだまだやることは山積みです
とりあえず完成図だけ出力しました
平均20msで見つかってる感じですが遅いやつはとことん遅いのでそこを改善していきたいです
5日目
考察
nが大きいとき探索の初めの方に選んだものが重要になってきていてはじめに選んだのが良ければ速くてそうじゃなければ遅いと顕著に表れていました
なので一定時間たっても見つからなかったら初めの方を変えるという機構を加えました
この方法で10000ケース試したところ一番遅いものが2.5sのタイミングでの発見だったのでシステムテストがちょっと怖いです
6日目
ここにきてまだ移動の方法について一切実装していないことに気が付きました
このタイミングでスライドパズルについていろいろと調べIDA*やA*などのスライドパズルで使えるアルゴリズムがあることを知りました
なので移動方法についてはこの方法で行こうと考えました
7日目
A*など調べてみたものの今回のものに落とし込み間に合わせることができなかったのでとりあえず一個一個貪欲に並べていく方法にしました
左上から順に並べていく途中でまだ提出を自明解の一つしかしてないことに気づき下二段の実装してないけどとりあえずこれでいったん提出
予定としては明日下の段の完成と作成途中の操作の一括化などをするなどをしてあっさてに微調整で終わるという予定です
8-9日目
土曜に学校があり帰った後爆睡して徹夜をしてしまったので時間だけはしっかりとれました（頭が回らん）
今日は下二段を埋める方法を実装しましたが30Mほどで止まってしまいここから上がる未来がみえなかったので置く順番を変えてみました
上から順番に置いて行くと最後の方になっても移動に時間がかかってしまうので上に横に置いたら左に縦に並べるという風にしました
また、最後のところは大きくても高々4*2なので全探索することにしました
最終的にこれに誤差レベルの工夫を加えて35M程度で終わりました
また、最後4000ケースほどバグがないか回していたら最後の方に1回だけバグが出てきて直してから提出できたのでやはりローカルテストはできる限り数をこなした方がいいと思いました
感想
最初は木を作るのは上位に入る前提ではあると思っていたもののここまで上位が高くなると思っておらず40M出してる人を見て驚愕してました
また、木を探す部分に時間をとられすぎてしまい移動のところに力を入れられてないので次回以降の長期コンは時間配分にも注意していきたいと思いました
また後半の方は何も考えず書き進んでしまいコード量がバカほど増えてしまい改善しずらくなってしまったのでそこは次回以降気を付けていきたいです
次回こそは1ページ目に乗れるようにいろいろな武器を身につけておきたいと思いました。
次回はどんな問題になるのか今から楽しみです。次こそはいい結果を残せるように頑張ります！！
終わりに
最後まで読んでいただいてありがとうございます
最後に今回のコードのお気に入りの部分です（見栄え重視）
この記事が気に入ったらサポートをしてみませんか？