ABC問題のABC042D
競技プログラミングAtCoderの過去問にある、ABC042のDをやってみた。
問題文
縦 H マス、横 W マスのマス目があります。 いろはちゃんは、今一番左上のマス目にいます。 そして、右か下に1マス移動することを繰り返し、一番右下のマス目へと移動します。 ただし、下から A 個以内、かつ左から B 個以内のマス目へは移動することは出来ません。
移動する方法は何通りあるか求めてください。
なお、答えは非常に大きくなることがあるので、答えは \( 10^9+7 \) で割ったあまりを出力してください。
制約
- \( 1 \leq H,W \leq 100000 \)
- \( 1 \leq A < H \)
- \( 1 \leq B < W \)
問題の本文はこちら
解答
最初は試しに全探索で試みる。各マス目において右か下にしか移動できないので、深さ優先探索でゴールを目指す。その際、移動が禁じられているエリアには入らないようにする。
void search_recursive(int x, int y, int H, int W,
int A, int B,
uint64_t &goal_counter) {
if (x == W && y == H) { // stop condition, goal
goal_counter++;
return;
}
if (x == W+1 || y == H+1
|| (x <= B && y == H-A+1)) {
return;
}
search_recursive(x+1, y, H, W, A, B, goal_counter);
search_recursive(x, y+1, H, W, A, B, goal_counter);
}
int main() {
int H, W, A, B;
std::cin >> H >> W >> A >> B;
uint64_t goal_counter = 0LL;
search_recursive(1, 1, H, W, A, B, goal_counter);
std::cout << goal_counter % (1000000000+7)
<< std::endl;
}結果、これだとWとHが大きい値になると制限時間までに間に合わない。次にやってみたのは、組合せを使った計算。スタート地点からゴールに辿り着くのに、どのルートを辿っても、トータルで右に W – 1 回と、下に H – 1 回移動することになるので、W x H のマス目のなかで左上から右下に移動するルートの全パターンは
\( Total = {(W-1)+(H-1)}\choose{(W-1)} \)で求めることが出来る。この全ルートから、禁止されているエリアを通るルート
\( Sub = \sum_{k=0}^{B-1} { {(W-1-k)+(A-1)}\choose{(A-1)} } { {k+(H-A-1)}\choose{k} } \)を引いた値が答えになる。
int64_t fact(int n) {
int64_t factorial = 1LL;
for (int i = 1; i <= n; i++) {
factorial = (factorial*i);
}
return factorial;
}
int64_t comb(int n, int r) {
return fact(n) / (fact(r) * fact(n-r));
}
int main() {
int H, W, A, B;
std::cin >> H >> W >> A >> B;
int64_t total = comb((H-1)+(W-1), (W-1));
int64_t sub = comb((A-1)+(W-1), (A-1));
for (int i = 1; i < B; i++) {
int64_t c0 = comb((A-1)+(W-1-i), (A-1));
int64_t c1 = comb(i+(H-A-1), i);
int64_t m0 = (c0 * c1);
sub = (sub + m0);
}
int64_t res = (total-sub) % (1000000000+7);
std::cout << res << std::endl;
}結果、これでも、やはりHとWが大きいと間に合わない。そもそも、階乗の計算がオーバーフローしてしまって、正しい値を出力できていない。階乗の計算は毎回呼び出す度に、同じ計算を再度行っている状態なので、そこに時間を取られている。前もって階乗のテーブルを作っておく手法でやってみた。
階乗の結果が大きくなるとオーバーフローしてしまうので、\( 10^9+7 \) の素数で剰余演算しながらテーブルを作っていく。組合せの計算には、階乗の割り算も含まれるのだが、割り算に対しては剰余演算の分配法則は成り立たないので、逆数とその階乗のテーブルも作っておく。
逆数の計算
- \( D = dq + r \) （ユークリッド除法, D=Dividend, d=divisor, q=quotient, r=remainder）
- \( M = iq + r \) （\( M = 10^9+7 \), i = 逆数を計算したい整数）
- \( M \bmod M = (iq + r) \bmod M \) （両サイドに剰余演算）
- \( 0 = iq \bmod M + r \bmod M \)
- \( r \bmod M = -iq \bmod M \)
- \( i^{-1} r \bmod M = i^{-1} (-iq) \bmod M \) （両サイドに\( i^{-1} \) を掛ける）
- \( r^{-1} i^{-1} r \bmod M = r^{-1} (-q) \bmod M \) （同じく\( r^{-1} \) を掛ける）
- \( i^{-1} \bmod M = -q r^{-1} \bmod M \)
- \( i^{-1} \bmod M = -[M / i] (M \bmod i)^{-1} \bmod M \) （\( q = [M/i], r = (M \bmod i) \)）
- \( i^{-1} \bmod M = -[M / i] (M \bmod i)^{-1} \bmod M + M \) （負の剰余演算）
- \( i^{-1} \bmod M = M – [M / i] (M \bmod i)^{-1} \bmod M \) （整数 i の逆数）
const int64_t M = 1000000007;
const int MAX = 200000;
int64_t f[MAX], finv[MAX], inv[MAX];
void create_fact_table() {
f[0] = 1;
f[1] = 1;
finv[0] = 1;
finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
f[i] = f[i-1] * i % M;
inv[i] = M - inv[M % i] * (M / i) % M;
finv[i] = finv[i-1] * inv[i] % M;
}
}
int64_t comb_t(int n, int r) {
return (f[n] * ((finv[r] * finv[n-r]) % M)) % M;
}
int main() {
int H, W, A, B;
std::cin >> H >> W >> A >> B;
create_fact_table();
int64_t total = comb_t((H-1)+(W-1), (W-1));
int64_t sub = comb_t((A-1)+(W-1), (A-1));
for (int i = 1; i < B; i++) {
int64_t c0 = comb_t((A-1)+(W-1-i), (A-1));
int64_t c1 = comb_t(i+(H-A-1), i);
int64_t m0 = (c0 * c1) % M;
sub = (sub + m0) % M;
}
int64_t res = ((total-sub) % M + M) % M;
// または、以下のコードも同じ
//
// int64_t res = 0;
// int i = 0;
// int j = H-1;
// while (i <= H-A-1 && j >= A) {
// int64_t c0 = comb_t(B-1+i, i);
// int64_t c1 = comb_t(W-B-1+j, j);
// res = (res + ((c0 * c1) % M)) % M;
// i++;
// j--;
// }
std::cout << res << std::endl;
}結果、これで解決できた。
