C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題D (D – Blue and Red Balls) を解いてみた.
■感想.
1. 仕切りに必要な, 赤いボール, 青いボールを考えてから, 残った赤いボール, 青いボールの並べ方に気付けたので, ACを取ることが出来たと思う.
2. 解答を見る前に, 解けたので, 及第点取れたと思う.
3. 課題としては, 復習が全く追い付いてないので, 考慮時間を限定して, なるべく多くの問題(※新しい知識の獲得)に触れるように方針の変更が必要と思った.
本家のサイトABC 132解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; const LL MAX = 4321; LL F[MAX]; LL IF[MAX]; // Fermat's little theorem を 適用するため, ap-2乗 などを計算できるようにする. // @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; } // 配列 IF に, 逆元を保存. // @param: 特に無し. // @return: 配列IF の update. void initialize(){ F[0] = 1, IF[0] = 1; for(LL i = 1; i < MAX; i++){ F[i] = (F[i - 1] * i) % MOD; //逆元を、フェルマーの小定理を利用して求める IF[i] = inverse(F[i], MOD - 2) % MOD; } } // 組み合わせ(nCk)計算用(mod版). // ※配列F, IF は, 事前に計算済のものを使う. // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果. LL combination(LL n, LL k){ if(n < 0 || k < 0 || k > n) return 0; LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD; return ret; } int main() { // 1. 入力情報取得. LL N, K; scanf("%lld %lld", &N, &K); initialize(); // 2. 場合の数をカウントし, 出力. for(int i = 1; i <= K; i++){ // 2-1. 各計算項目を設定. LL rp = i - 1; // 仕切りに使う赤いボール. LL rr = N - K - rp; // 残った赤いボール. LL bp = i; // 仕切りで使う青いボール. LL br = K - bp; // 残った青いボール. // cout << "rp=" << rp << " rr=" << rr << " bp=" << bp << " br=" << br << endl; // 2-2. 場合の数を計算. // 残った赤いボールの並べ方. LL ans = combination(rr + bp, rr); ans %= MOD; // 残った青いボールの並べ方. ans *= combination(rp + br, br); ans %= MOD; // 2-3. 出力. printf("%lld\n", ans); } // 3. 後処理. 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 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 |
[入力例] 5 3 [出力例(debug版)] rp=0 rr=2 bp=1 br=2 3 rp=1 rr=1 bp=2 br=1 6 rp=2 rr=0 bp=3 br=0 1 ※AtCoderテストケースより [入力例] 2000 3 [出力例(debug版)] rp=0 rr=1997 bp=1 br=2 1998 rp=1 rr=1996 bp=2 br=1 3990006 rp=2 rr=1995 bp=3 br=0 327341989 ※AtCoderテストケースより [入力例] 7 4 [出力例(debug版)] rp=0 rr=3 bp=1 br=3 4 rp=1 rr=2 bp=2 br=2 18 rp=2 rr=1 bp=3 br=1 12 rp=3 rr=0 bp=4 br=0 1 [入力例] 1234 10 [出力例(debug版)] rp=0 rr=1224 bp=1 br=9 1225 rp=1 rr=1223 bp=2 br=8 6747300 rp=2 rr=1222 bp=3 br=7 2597123 rp=3 rr=1221 bp=4 br=6 17982499 rp=4 rr=1220 bp=5 br=5 486989341 rp=5 rr=1219 bp=6 br=4 354498646 rp=6 rr=1218 bp=7 br=3 965128240 rp=7 rr=1217 bp=8 br=2 974617226 rp=8 rr=1216 bp=9 br=1 891920999 rp=9 rr=1215 bp=10 br=0 473065861 |
■参照サイト
AtCoder Beginner Contest 132