semiexp https://blog.hatena.ne.jp/semiexp/ Algorithmer’s note https://semiexp.hatenadiary.org/ Algorithm TopCoder 今日の問題。 問題 きつねが原点にいる。今、(Tx, Ty)に移動しようとしている。きつねは、1回のジャンプで、x方向の正方向に0マスからMxマス、y方向の正方向に0マスからMyマス動ける。動く距離は正でないといけない。また、bがbadに含まれるとき、x方向、y方向両方にbマス動くことはできない。badには10の倍数だけが入っている。ちょうどR回で目的地につく場合の数を求めよ。 方針 まず、ゼロ距離移動が許されてないのはうざいのでbadに0を追加してゼロ距離移動も特別視しないようにする。 次に、badを許可して、R回で(x, y)に移動する場合の数は、X方向とY方向に独立なので、DPを使うと簡… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsemiexp.hatenadiary.org%2Fentry%2F20110227%2F1298793686" title="TopCoder SRM498 Div1Hard - Algorithmer’s note" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2011-02-27 17:01:26 rich https://semiexp.hatenadiary.org/entry/20110227/1298793686 1.0 100%