E - GO!GO! サイコロ線路 Editorial by maspy
解説が世の中に存在するか分からなかったので一応書きます.
ボス問とはいえ,発想はほとんど要らないタイプの問題です.
\(N=6\) のとき \((0,0)\) から \((N-1,N-1)\) への単純パスは,約 \(126\) 万個(https://oeis.org/A007764 )です.パスの最後の時点でのサイコロの向きを状態として,状態数は \(24\times 126\) 万程度です.各状態から \(3\) 方向以下,方向ごとに次のサイコロの向きが \(4\) 通り.
すると,すべての単純パスを無駄なく列挙できれば,適切に実装すれば間に合いそうな範囲です.
私の場合,この dfs を実装したところ,3 sec 近くかかりました(75 点解法?). 探索しているノード数が \(1847\) 万程度となっていました.
単純に dfs すると,次のような無駄が発生してしまいます.
######
.....#
.....#
.....#
....##
...##.
パスの途中までの時点を取り出したものが上図のようになっていると,ここから先の探索が無駄です.
こういう無駄を減らすような,適当な枝狩りを足せば AC できると思います.
私は,「通ったマスの個数が 5 の倍数になるたびに連結性をチェックする」という枝狩りを入れると,探索ノード数が \(842\) 万程度となり AC できました.
posted:
last update: