C++の練習を兼ねて, AtCoder Beginner Contest 042 の 問題C(こだわり者いろはちゃん / Iroha’s Obsession) ~ 問題D (いろはちゃんとマス目 / Iroha and a Grid) を解いてみた.
■感想.
1. 問題D は, 解答の方針が, 全く見えなかったので, 解説を読んだうえで, おおよそ, このような内容を問われていたと推測してコーディングしている.
本家のサイトABC042/ARC058解説をご覧下さい.
■C++版プログラム(問題C/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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. string N; int K; cin >> N >> K; char D[K] = {}; FOR(i, 0, K) cin >> D[i]; // 2. 嫌いな数字が出現しないような最も少ない金額を探索. string ans = N; while(1) { bool ok = true; FOR(i, 0, K) { // 嫌いな数字が出現したら, 次の数字を確認するため, // break で, 抜ける. if(ans.find(D[i]) != string::npos) { ok = false; break; } } if(!ok) ans = to_string(stoi(ans) + 1); if(ok) break; } // 3. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// 解き直し. // ABC042/ARC058解説. // http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1000000007; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) // Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL inverse(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 H, W, A, B; cin >> H >> W >> A >> B; // 2. 解説通り. // ※座標(0, 0)が, 基準となっている点に注意. // 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を 計算. LL LIMIT = H + W - 2; LL FAC[LIMIT + 1] = {}; FAC[0] = 1; FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD; // 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元 を 計算. LL INV[LIMIT + 1] = {}; FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD; // 3. 各i(B ≦ i ≦ W - 1)で, (0, 0), (H - A - 1, i), (H - A, i), (H - 1, W - 1) のような順路を数え上げて合計する. // 最短経路. // http://examist.jp/mathematics/math-a/baainokazu/saitankeiro/ LL ans = 0LL; FOR(i, B, W) { // 3-1. ルート①. // (0, 0) -> (H - A - 1, i) の場合の数は, 縦方向(↓) (H - A - 1)個, 横方向(→) i個 なので, // (H - A - 1 + i)! / (H - A - 1)! / i! で計算される筈. LL r1 = FAC[H - A - 1 + i]; r1 *= INV[H - A - 1]; r1 %= MOD; r1 *= INV[i]; r1 %= MOD; // 3-2. ルート②. // (H - A - 1, i) -> (H - A, i) の場合の数は, 縦方向(↓) 1個, 横方向(→) 0個 なので, 1通り(※計算は省略可). // 3-3. ルート③. // (H - A, i) -> (H - 1, W - 1) の場合の数は, 縦方向(↓) ((H - 1) - (H - A) =) A - 1個, // 横方向(→) W - 1 - i個 なので, (A - 1 + W - 1 - i)! / (A - 1)! / (W - 1 - i)! で計算される筈. LL r3 = FAC[A - 1 + W - 1 - i]; r3 *= INV[A - 1]; r3 %= MOD; r3 *= INV[W - 1 - i]; r3 %= MOD; // 3-4. ルート① ~ ルート③ を 反映. ans += r1 * r3; ans %= MOD; } // 4. 出力 ~ 後処理. cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 042