C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題G (Colorful Candies 2) を解いてみた.
■感想.
1. 問題Gは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 期待値の性質について, 学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 215 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 83 84 |
// 解き直し. // https://atcoder.jp/contests/abc215/editorial/2497 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second const LL MOD = 998244353; const int LIMIT = 50505; LL FAC[LIMIT], INV[LIMIT]; // 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; } // 組み合わせ(nCk)計算用(mod版). // ※配列FAC, INV は, 事前に計算済のものを使う. // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果(mod版). LL combination(LL n, LL k){ if(n < 0 || k < 0 || k > n) return 0LL; if(n == k || k == 0LL) return 1LL; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<LL, LL> n; rep(i, N){ LL c; scanf("%lld", &c); ++n[c]; } // 2. 事前準備. FAC[0] = INV[0] = 1; repx(i, 1, LIMIT){ FAC[i] = (LL)i * FAC[i - 1] % MOD; INV[i] = mPow(FAC[i], MOD - 2); } // 3. n = x となる種類数 の 個数. map<LL, LL> a; for(auto &x : n) ++a[x.b]; // 4. 各ケースの期待値. repx(k, 1, N + 1){ // 4-1. 集計(分子). LL ans = 0, C = combination(N, k); for(auto &p : a){ ans += p.b * (C + MOD - combination(N - p.a, k)) % MOD; ans %= MOD; } // 4-2. 集計(分母). ans *= mPow(C, MOD - 2); ans %= MOD; // 4-3. 出力. printf("%lld\n", ans); } 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
[入力例] 3 1 2 2 [出力例] 1 665496237 2 ※AtCoderテストケースより [入力例] 11 3 1 4 1 5 9 2 6 5 3 5 [出力例] 1 725995895 532396991 768345657 786495555 937744700 574746754 48399732 707846002 907494873 7 ※AtCoderテストケースより [入力例] 5 1 2 3 2 1 [出力例] 1 399297743 199648873 399297744 3 [入力例] 30 11 13 17 11 15 13 16 17 12 14 15 15 15 15 10 16 15 15 16 16 16 14 14 14 10 15 10 17 13 12 [出力例] 1 562229580 319389021 415434298 975870615 53715478 501543505 339533645 154451006 238429014 173030800 653731178 429089161 262362724 934047753 339060528 788588261 758430204 295930312 450468204 118934339 752164850 486064297 256002128 597156160 842379096 517070913 800890305 8 8 [入力例] 50 11 13 10 20 21 17 20 14 21 11 13 12 18 21 14 11 15 11 17 15 13 18 16 11 14 18 15 12 14 21 21 20 15 14 15 15 10 17 10 18 17 19 17 18 10 18 12 10 17 18 [出力例] 1 224095673 671981431 633115787 595544474 547699361 900336322 276842986 392056943 288893097 135364271 844271167 751503079 571334287 894503529 452728420 378573628 722948910 448621936 139198593 673557343 99923386 926211909 113495582 941823113 68601316 927699740 800024195 707229517 432983203 870852727 959336993 422426853 567436911 383072599 154361806 853215869 540561324 994916051 847242386 415883070 510878726 436585674 421512894 727120358 668008835 775931273 359367979 678806172 12 |
■参照サイト
AtCoder Beginner Contest 215