C++の練習を兼ねて, AtCoder Beginner Contest 024 の 問題D (D – 動的計画法) を解いてみた.
■感想.
1. 着眼点が見えなかったので, 解説どおりに実装したところ, AC版となった.
2. 数式変形を駆使する解法に, 目から鱗だった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 024解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
// 解き直し. // https://www.slideshare.net/chokudai/abc024 #include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } int main(){ // 1. 入力情報. LL A, B, C; scanf("%lld %lld %lld", &A, &B, &C); // 2. 解説通り. // 2-1. c を 計算. // c = (B * C - A * B) / (C * A - B * C + A * B) LL ab = A * B % MOD, bc = B * C % MOD, ca = C * A % MOD; LL cMol = (bc + MOD - ab) % MOD; LL cDen = mPow((ca + MOD - bc + ab) % MOD, MOD - 2); LL c = cMol * cDen % MOD; // 2-2. r を 計算. // r = (B * C - C * A) / (A * B - B * C + C * A) LL rMol = (bc + MOD - ca) % MOD; LL rDen = mPow((ab + MOD - bc + ca) % MOD, MOD - 2); LL r = rMol * rDen % MOD; // 3. 出力. printf("%lld %lld\n", r, c); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
[入力例] 15 35 21 [出力例] 4 2 ※AtCoderテストケースより [入力例] 126 252 210 [出力例] 5 4 ※AtCoderテストケースより [入力例] 144949225 545897619 393065978 [出力例] 314159 365358 ※AtCoderテストケースより [入力例] 999888777 666555444 333222111 [出力例] 681836797 485100218 |
■参照サイト
AtCoder Beginner Contest 024