https://atcoder.jp/contests/abc154/tasks/abc154_f
前提知識
解説
https://atcoder.jp/contests/abc154/submissions/10005470
問われているのは、ある矩形区間での総和であるが、変数が4つもあるのは扱いにくい。
2次元累積和で使われている考え方を用いて、変数を2つに減らそう。
g(r,c) := 左下が(0,0)で、右上が(r,c)である矩形区間でのf(r,c)の総和
これを計算することができれば、g(r2, c2) - g(r1 - 1, c2) - g(r2, c1 - 1) + g(r1 - 1, c1 - 1)が答えとなる。
もし、これがあまりピンとこない場合は、2次元累積和について学ぶと良い。
これで変数が絞られたので、g(r,c)の計算方法を考えよう。
f(r,c)の計算方法を考えると、二項係数を使う方法が有名。
高校数学でもよく出てくる。これ
しかし、競技プログラミング的にはDPで解く方法も良く使われる。
DPにするとしたら、何を添字とするかとなるが、106なので1変数しか使えない。
ここからひらめくと、以下のようなDPができる。
dp[rc] := r+c=rcである(r,c)についてf(r,c)の総和
もしDPで行くとしたら、これしか作れない感があるのだが、実はこれが計算可能。
これの遷移を見てみると、序盤はdp[rc+1] = dp[rc] * 2となっていることに気がつく。
途中では片方の端の要素だけ2倍とならず、最後は両端の要素だけ2倍とならない。
つまり、遷移をしていくが、2倍とならない要素だけ、引くことで計算ができる。
2倍とならない要素は両端の最大2個なので、そこだけ二項係数を使って計算して引いてやればいい。
最後は2倍とならない要素の判定方法である。
rcをインクリメントしていくのは、傾き-1の直線が平行移動していくようなイメージ。
その時に矩形区間と交わる部分が端となる。
端に注目すると、↑→と移動する点1と、→↑と移動する点2が、速度1で同時に移動しているような感じになる。
点1が→に移動する時は、遷移先に1回しか足されてないので、引く。
点2が↑に移動する時は、遷移先に1回しか足されてないので、引く。
よって、それぞれの点の座標を覚えておいて、遷移しながら移動させることで、引く要素を判定するといい感じ。
Comb<mint, 2010101> com; //--------------------------------------------------------------------------------------------------- mint dp[2010101]; mint g(int R, int C) { dp[0] = 1; int r1 = 0, c1 = 0; int r2 = 0, c2 = 0; rep(rc, 0, R + C) { dp[rc + 1] = dp[rc] * 2; if (r1 != R) r1++; else { dp[rc + 1] -= com.aCb(r1 + c1, r1); c1++; } if (c2 != C) c2++; else { dp[rc + 1] -= com.aCb(r2 + c2, r2); r2++; } } mint res = 0; rep(rc, 0, R + C + 1) res += dp[rc]; return res; } //--------------------------------------------------------------------------------------------------- void _main() { int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; mint ans = g(r2, c2) - g(r1 - 1, c2) - g(r2, c1 - 1) + g(r1 - 1, c1 - 1); cout << ans << endl; }
