[AHC011] A - Sliding Tree Puzzle

[Q] https://atcoder.jp/contests/ahc011/tasks

37.7Mで暫定56位->システス60位
・最終スコア率: 74.57%
・未完率: 5.43%(163/3000)
・内訳
20%~: 4
30%~: 44
40%~: 115
50%~: 0
60%~: 7
65%~: 702
70%~: 1012
75%~: 1583
80%~: 399
85%~: 6

・未完がこんなにたくさんあるなんて思わなかった…。
・揃いさえすれば得点率高い。

・Seed0：Score = 782407

[1日目] 19067882点
満点を狙わず、ビームサーチでできるだけ大きい木を作る。スコア率は40%。

[4日目] 24883091点
N=6だけ、枝切DFSで理想盤面を1つ探す。
探索順序を

0 1 2 3 4 
5 6 7 8 9
...

とした。
枝切は
1. 枝が余ったら打ち切り
2. 木が独立したら打ち切り(UnionFind)
3. 閉路ができたら打ち切り(UnionFind)
で相当数減らせるので、割と一瞬で求まる。

しかしN=8から見つからない。
N=7まで理想盤面を追求し、合わせ技でスコア率49%

[6日目] 27093871点
よりよいDFS探索順序が閃いた。天啓。

0 1 3 6 ...
2 4 7 ...
5 8 ...
9 ...

この順序で探索すれば、途中の枝切が早まってN=10でも余裕をもって見つかる。ようになった気がする。
（2辺or3辺が縛られるので、どのマスも4通り/2通りしか設置できない）
理想盤面を見つけられても、生成手順が見つからず伸び悩む。スコア率は54%

[最終日1] 30397018点
山登りを実装。ダイクストラをした。
1. スタート(初期面)からゴール(理想面)までの盤面状態に、IDを振り出す。
map<state, ID> memo
2. preID -> IDにコスト1，ID->preIDにコスト1の辺を張る。
3. 途中の盤面からランダム移動を試み、新しい盤面にどんどんIDを振り出し、コスト1を両辺に張る。既ID盤面との合流をもくろむ。
4. 規定盤面数(60000とした)になったら、初期盤面からゴール盤面までダイクストラ。

[最終日2] 32000880点
理想盤面のDFS探索をやめて、ビームサーチで探索する。
初期盤面と理想盤面のマンハッタン距離でスコア化し、最も距離が短い理想盤面を採用した。

[最終] 37710866点
折り返し部分を作るのに一生モタモタしているようなので、評価関数に折り返し点数を実装。

[Ex]上位者のプレイング(Seed0, N=8)

8 1024
edec01e5
229c5c78
5e4cf11a
22d57ca9
ab15549b
873719a5
e31437f5
414ae282

///// OUTPUT /////
180
DDDRDDLDLLDRRULULULUUURDRDDDLLULDRURUUURDLUURRRDDRULDDDRDDDLURRDLUULDDRUURDLLLLLDRRULLDLULURUURUUULDRDLLUURDDLUURDLDDDRDDRUUURDRUURDLLDDLDDRRRUURUURUULLDRUURDDDDLLLUUURRDDLLDRDDRDR
218
LLDRDDDLURDDRRDRDLLULLULUUURRDDDLLUUURURDRULURDRURDDDRUULLURRDDLLDDRDLLLLDLUULDDRDLUURRURDDDLURRURRRULDDRULDLDLUUURDRULLLDRRRULLDRRULDRRULLULLDLUURUURDRULLDRDDLURDDLLULDRRUULLDRULURULDLURRDDLURDLLURRDRDDDLURUULDDRDLURR

Score = 912109

Score = 893555

柔軟性すごい。固定場所の法則性が見えない。
途中まで全然そろえないのに一筆で全部そろっちゃうとか、
上をそろえた後、下をそろえにいく、などしている。
あたかも簡単にそろえられるように見える。

実装順序は「とりあえずの解法を見つける=>焼きなまし」だと思うんだけど。

Q. とりあえずの解法を見つけるのにどのくらいかかったのか
Q. とりあえずの精度は
Q. 焼きなましの上昇精度は

俺の場合、とりあえずの解法で1.5sec ~ 2.9sec。精度70%。
山登りはせいぜい1割の効率化。精度75%。
N=6の時はほぼ1.5sec余るので、山登りを焼きなましにできれば効果的かもしれない。
例えば、深さ20手まで動かしてみて、合流地点がなければ打ち切り。
見つかった場合でも、90%は採用、10%は不採用にするなど。

コード増えてもいいことはない。
こまめにpushしてコメント残したほうがいい。
https://atcoder.jp/contests/ahc011/submissions/32267767