AtCoder Beginner Contest 154 F - Many Many Paths
二次元のある長方形領域 (r1≦y≦r2, c1≦x≦c2) の中の yCx の和を計算する問題。
とりあえず2次元の中の何かの和を考えるときは、包除原理を使うことにより 0≦y<≦r, 0≦x≦c で計算するルーチンを書いておき、あとから余計な部分を引くのが定石。
では、あるr,c が与えられたとき、0≦y<≦r, 0≦x≦c でのΣyCx の計算だがいろいろな方法がある。
一つはWolfram Alphaを使う方法。適当に入力すると式を簡約し今回は計算量の小さい式を勝手に計算してくれたみたいなので、使えるようにしておきたい。
本番で考えたのはyCxの計算は格子点領域の中である地点から別の地点へ向かう最短経路の数の数え方に一致することから、このDPの漸化式を考察した。すると、その長方形領域を斜めで縦でも横でも良いがあるラインで考え、そのライン上のyCxの和が計算できたとする。その時、最短経路の数え方は隣接した格子の数を足し合わせる、ということを考えると、
[あるライン上の yCxの和] = [一つ前のライン上の yCxの和] * 2- [ラインの端っこの調整]
という漸化式が成り立つ。この漸化式に従って、計算していき、ライン上の yCx の和をどんどん足し合わせて行けば良い。O(max(R,C))
