競技プログラミング用 知識集積所
H - Grid 1
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
動的計画法における考え方自体は単純。
（もしかしたら、DPコンテストで一番簡単かもしれない）
「左上から順に、そのマスまでの経路数を全部埋めていく」だけ。
しかも、その経路数を求める計算は、左から来るものと上から来るものを加算するだけ。
（もしかしたら、DPコンテストで一番簡単かもしれない）
「左上から順に、そのマスまでの経路数を全部埋めていく」だけ。
しかも、その経路数を求める計算は、左から来るものと上から来るものを加算するだけ。
例えば入力例1ならこういう表を作るだけ。
| 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 2 | 3 |
ただし、まず、二次元的に継承する動的計画法自体が書きなれていなければ大変。
さらに、
さらに、
- 壁だったら0にする
- 端だったら左からや上からの片方しかない
- 左上だけは計算なしで1を入れる特殊処理が必要
など、実装上気を配らなくてはいけない箇所がたくさんある。
トドメに、「答えは非常に大きくなりうるので、10^9+7で割った余りを求めてください。」の指示。
もちろん最後だけでなく途中もとんでもなく大きくなるので、剰余類環の考えを用いる。
つまり、今回の計算が足し算引き算掛け算以外使わないことを確認したうえで、「全ての計算後に10^9+7で割った余りに書き直す」をやる。
計算は足し算しかないので、計算途中で出てくる最大数は2*10^9+14未満。
つまり、きちんとサボらず剰余を取り続けるならint型で大丈夫。
もちろん最後だけでなく途中もとんでもなく大きくなるので、剰余類環の考えを用いる。
つまり、今回の計算が足し算引き算掛け算以外使わないことを確認したうえで、「全ての計算後に10^9+7で割った余りに書き直す」をやる。
計算は足し算しかないので、計算途中で出てくる最大数は2*10^9+14未満。
つまり、きちんとサボらず剰余を取り続けるならint型で大丈夫。
