読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 秒後まで計算できる。

f:id:pekempey:20160309142911p:plain

これは行列累乗できる DP なので、一気に T/5*5 秒後まで計算して残りは地道に DP すればいい。

RUPC 2016 day3 G: Destiny Draw

遷移行列を作るのが地味に面倒。