C++の練習を兼ねて, AtCoder Regular Contest 051 の 問題C (掛け算) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 数列の大小関係(※最大値が, 最小値の定数倍以下に収まるケース)が確定するまでシュミレーションして, 残り部分は, 高速累乗で, 計算可能という解説にあるロジックが, 目から鱗だった.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 051 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/data/arc/051/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 pb push_back #define all(x) x.begin(), x.end() 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; } int main(){ // 1. 入力情報. int N; LL A, B; scanf("%d %lld %lld", &N, &A, &B); vl a(N); rep(i, N) scanf("%lld", &a[i]); // 2. sort. sort(all(a)); // 3. 例外. if(A == 1){ for(auto &p : a) printf("%lld\n", p); return 0; } // 4. シュミレーション. LL s = a.front(), e = a.back(), C = 0; while(s * A < e){ ++C; a.erase(a.begin()); a.pb(s * A); sort(all(a)); s = a.front(); e = a.back(); if(C == B) break; } // printf("C=%d\n", C); // 5. 例外. if(B == C){ for(auto &p : a) printf("%lld\n", p); return 0; } // 6. 高速累乗. // 6-1. 商の部分. LL q = (B - C) / N; rep(i, N){ a[i] *= mPow(A, q); a[i] %= MOD; } // 6-2. 余り部分. int r = (B - C) % N; while(r){ s = a.front(); a.erase(a.begin()); a.pb(s * A % MOD); --r; } // 7. 出力. for(auto &p : a) printf("%lld\n", p); 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 131 132 133 134 135 136 137 138 |
[入力例] 3 10 3 1 99 10 [出力例] 99 100 100 ※AtCoderのテストケースより [入力例] 2 100001 2 1 200000 [出力例] 200000 199931 ※AtCoderのテストケースより [入力例] 10 123 1000000000 394632992 714094234 84420 5 3439891 3395 35 58 5001 730 [出力例] 954804718 385989482 948741792 268211139 100694402 492858064 955116743 68100851 154525400 479209143 ※AtCoderのテストケースより [入力例] 5 1 3 1 2 3 4 5 [出力例] 1 2 3 4 5 [入力例] 3 2 5 3 18 75 [出力例] 36 48 75 [入力例] 7 2 12 31 41 59 26 5 3 58 [出力例] 52 58 59 62 80 82 96 [入力例] 12 3 15 63 15 1 9 91 54 24 23 114 77 65 90 [出力例] 77 81 81 90 91 114 135 162 189 195 207 216 [入力例] 30 5 20220419 15 55 97 20 72 7 37 55 77 90 92 100 120 72 11 39 101 123 52 9 66 10 63 88 97 48 3 58 82 111 [出力例] 766349623 362346882 362346882 919945243 919945243 439144692 631139217 303934286 861532647 859904170 51898688 243893213 819876788 607868572 799863097 991857622 779849406 779849406 779849406 567841190 547827499 335819283 911802858 911802858 699794642 699794642 891789167 871775476 447759044 639753569 [入力例] 10 7 987654321 534272906 925848312 51921325 636258348 766724404 254864144 535929987 258927917 906007521 841903248 [出力例] 986918973 184630732 724343739 165436415 884949643 768125768 187543668 209626080 802753440 483131451 |
■参照サイト
AtCoder Regular Contest 051