RUPC 2016 day3 G: Destiny Draw
※この解説は難しく考えすぎているのであまり参考にしない方がいいかも。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=G
らてさんにいい解法を教えてもらったので、そっちで書いたコードも挙げておきました。 原理は No.213 素数サイコロと合成数サイコロ (3-Easy) - yukicoder に近いのかな。
多分こういうことだよね。
https://gist.github.com/pekempey/bde7e262f56887524e0e
解法
T が小さければ次のような DP が可能である。
- dp[ i ][ j ] := i 秒後に C が位置 j にあるようなパターン数
行列累乗で T 秒後まで一気に求められればいいのだが、操作毎に必要な時間にばらつきがあるため簡単にはできない。
そこで次のような DP を考えてみる。
- dp[ i ][ j ][ k ] := 5*i+j 秒後に C が位置 k にあるようなパターン数
5 秒毎のラインをまたぐような操作のかたまりを 1 単位とすれば、T/5 回この操作を繰り返すことにより T/5*5 秒後まで計算できる。
これは行列累乗できる DP なので、一気に T/5*5 秒後まで計算して残りは地道に DP すればいい。
RUPC 2016 day3 G: Destiny Draw
遷移行列を作るのが地味に面倒。
