[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
この記事が気に入ったらサポートをしてみませんか?