C++の練習を兼ねて, AtCoder Grand Contest 028 の 問題B（Removing Blocks) を解いてみた.
■感想.
1. 時間内で, 解答方針が全く分からなかったので, コンテスト終了後に, 解答を確認して, コーディングしてみた.
2. ブロックの連結についての解説が, なるほどと感心したが, 実際に答案へ反映する作業は, かなり大変だった(汗).
本家のサイトAGC 028 解説をご覧下さい.
■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 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 |
// 解き直し. // AGC 028 解説. // https://img.atcoder.jp/agc028/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) #define abs(x) ((x > 0) ? x : (-(x))) typedef long long LL; const LL MOD = 1000000007; // 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 N; cin >> N; LL A[N + 1] = {}; FOR(i, 1, N + 1) cin >> A[i]; // 解説通り. // ------------------------------------------------------------------------------------------ // 2. 1/1, 1/2, 1/3, ... , 1/N の 累積和を保管. // Fermat's Little Theorem から, 1/x = x の (p - 2)乗 で 計算可能(※本問では, p = 1000000007). // 例) 1/2 = 500000004, 1/3 = 333333336, ..., 1/9 = 111111112, ...などと計算される. LL INV[100001] = {}; FOR(i, 1, 100001) { INV[i] += INV[i - 1]; INV[i] += inverse(i, MOD - 2) % MOD; } // 3. block[i] を取り除くとき, block[i], block[j] が連結である確率を, // P(i, j) と置いて, P(j) = ΣP(i, j) を, 計算する. // P(i, j) は, P(i, j) = 1 / (abs(i - j) + 1) で, 計算可能とのこと. LL P[N + 1] = {}; FOR(i, 1, N + 1) { LL r = abs(i - 1 + 1); // 左端までの距離(1 ～ i). LL l = abs(N - i + 1); // 右端までの距離(i ～ N). P[i] += INV[r]; P[i] %= MOD; P[i] += INV[l]; P[i] %= MOD; P[i] -= INV[1]; P[i] %= MOD; } // 4. 総コスト = Σ(A[j] × P(j)) × N! で, N回の操作のコストの合計(期待値)を求める. LL total = 0; // 4-1. Σ(A[j] × P(j)) の 部分 を 計算. FOR(i, 1, N + 1) { total += A[i] * P[i]; total %= MOD; // cout << i << " " << A[i] << " " << P[i] << endl; } // 4-2. × N! の 部分 を 計算. FOR(i, 1, N + 1) { total *= i; total %= MOD; } // ------------------------------------------------------------------------------------------ // 5. 後処理. cout << total << endl; 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 |
[入力例] 2 1 2 [総コスト] ブロック1: 1/1 + 1/2 = 3/2 ブロック2: 1/2 + 1/1 = 3/2 -> 各操作に関するコストの期待値: 3/2 * 1 + 3/2 * 2 = 9/2 -> 2!倍すると, 総コスト9 となる. [入力例] 4 1 1 1 1 [総コスト] ブロック1: 1/1 + 1/2 + 1/3 + 1/4 = 25/12 ブロック2: 1/2 + 1/1 + 1/2 + 1/3 = 7/3 ブロック3: 1/3 + 1/2 + 1/1 + 1/2 = 7/3 ブロック4: 1/4 + 1/3 + 1/2 + 1/1 = 25/12 -> 各操作に関するコストの期待値: 25/12 * 1 + 7/3 * 1 + 7/3 * 1 + 25/12 * 1 = 53 / 6 -> 4!倍すると, 総コスト212 となる. [入力例] 5 3 4 5 2 1 [総コスト] ブロック1: 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60 ブロック2: 1/2 + 1/1 + 1/2 + 1/3 + 1/4 = 31/12 ブロック3: 1/3 + 1/2 + 1/1 + 1/2 + 1/3 = 8/3 ブロック4: 1/4 + 1/3 + 1/2 + 1/1 + 1/2 = 31/12 ブロック5: 1/5 + 1/4 + 1/3 + 1/2 + 1/1 = 137/60 -> 各操作に関するコストの期待値: 137/60 * 3 + 31/12 * 4 + 8/3 * 5 + 31/12 * 2 + 137/60 * 1 = 1139 / 30 -> 5!倍すると, 総コスト4556 となる. [入力例] 10 1 2 4 8 16 32 64 128 256 512 [出力例] 880971923 |
■参照サイト
AtCoder Grand Contest 028