C++の練習を兼ねて, AtCoder Grand Contest 028 の 問題A (Two Abbreviations) ～ 問題C (Min Cost Cycle) を解いてみた.
■感想.
1. 問題B ～ C は, 解答方針が見えなかったので, 解説を参考に実装して, AC版まで到達出来たので良かったと思う.
※ 問題B は, 過去記事 の 実装を 書き換えた内容になっている.
2. 個人的には, いずれの問題も, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 028 解説 を ご覧下さい.
■C++版プログラム(問題A／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 |
// 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--) int main(){ // 1. 入力情報. LL N, M; char S[101010], T[101010]; scanf("%lld %lld %s %s", &N, &M, S, T); // 2. 最大公約数は？ LL g = __gcd(N, M); // 3. 判定. // -> 0 ～ (g - 1) まで, 比較. bool ok = true; rep(i, (int)g){ int idxS = i * (int)(N / g); int idxT = i * (int)(M / g); if(S[idxS] != T[idxT]){ ok = false; break; } } // 4. 出力. printf("%lld\n", ok ? (M * N / g) : -1); 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 |
[入力例] 3 2 acp ae [出力例] 6 ※AtCoderのテストケースより [入力例] 6 3 abcdef abc [出力例] -1 ※AtCoderのテストケースより [入力例] 15 9 dnsusrayukuaiia dujrunuma [出力例] 45 ※AtCoderのテストケースより [入力例] 1 1 a a [出力例] 1 [入力例] 15 21 abcdefghijklmno abcdehgfijolmnkpqrstu [出力例] 105 |
■C++版プログラム(問題B／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 |
// 解き直し. // https://img.atcoder.jp/agc028/editorial.pdf // 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--) const LL MOD = 1e9 + 7; const int LIMIT = 101010; LL INV[LIMIT], A[LIMIT], P[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 % MOD; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &A[i + 1]); // 2. 1/1, 1/2, 1/3, ... , 1/N の 累積和を保管. // Fermat's Little Theorem から, 1/x = x の (p - 2)乗 で 計算可能(※本問では, p = 1e9 + 7). // 例) 1/2 = 500000004, 1/3 = 333333336, ..., 1/9 = 111111112, ...などと計算される. repx(i, 1, LIMIT) INV[i] += INV[i - 1], INV[i] += mPow(i, MOD - 2); // 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) で, 計算可能とのこと. repx(i, 1, N + 1) { LL l = abs(i - 1 + 1); // 左端までの距離(1 ～ i). LL r = abs(N - i + 1); // 右端までの距離(i ～ N). P[i] += INV[l]; P[i] %= MOD; P[i] += INV[r]; P[i] %= MOD; P[i] -= INV[1]; P[i] %= MOD; } // 4. 総コスト = Σ(A[j] × P(j)) × N! で, N回の操作のコストの合計(期待値)を求める. // 4-1. Σ(A[j] × P(j)) の 部分 を 計算. LL ans = 0; repx(i, 1, N + 1) ans += A[i] * P[i], ans %= MOD; // 4-2. × N! の 部分 を 計算. repx(i, 1, N + 1) ans *= (LL)i, ans %= MOD; // 5. 出力. 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 |
[入力例] 2 1 2 [出力例] 9 ※AtCoderのテストケースより [入力例] 4 1 1 1 1 [出力例] 212 ※AtCoderのテストケースより [入力例] 10 1 2 4 8 16 32 64 128 256 512 [出力例] 880971923 ※AtCoderのテストケースより |
■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 89 90 91 92 |
// 解き直し. // https://img.atcoder.jp/agc028/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, int>; #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 a first #define b second int main(){ // 1. 入力情報. int N; scanf("%d", &N); vector<P> va, vb; priority_queue<P, vector<P>, greater<P>> pq; LL yAll = 0, zAll = 0; rep(i, N){ LL a, b; scanf("%lld %lld", &a, &b); // 全頂点がタイプ Y. yAll += a; // 全頂点がタイプ Z. zAll += b; // {重み, 頂点番号}. va.pb({a, i}); vb.pb({b, i}); // sort用. pq.push({a, i}); pq.push({b, i}); } // 2. sort済み情報の保管. vector<P> v; while(!pq.empty()){ P p = pq.top(); pq.pop(); v.pb(p); } // 3. 最初 の N項 を 確認. LL xwType1 = 0; bool ok = false; int idx[101010]; memset(idx, 0, sizeof(idx)); rep(i, N){ // 出現した頂点番号を保存. idx[v[i].b]++; // 最初 の N項 で, A[v], B[v] の 両方 を 確認出来た場合. if(idx[v[i].b] == 2) ok = true; // 最初 の N項 までの 和 を集計. xwType1 += v[i].a; } // 4. 最初 の N項 で, A[v], B[v] の 両方 を 確認出来なかった場合. LL xwType2 = 202020202020202020; if(!ok){ // i項目 を 除外して確認. rep(i, N){ // タイプ W の 頂点 w を 決め打ち. int w = v[i].b; // (N + 1)項目, (N + 2)項目のいずれを採用するか. // -> 原則, (N + 1)項目 の 頂点を採用するが, // 頂点番号が, w の 場合は, (N + 2)項目 の 頂点を採用. LL cost = v[N].a; if(v[N].b == w) cost = v[N + 1].a; // 更新. xwType2 = min(xwType2, xwType1 - v[i].a + cost); } } // 5. 出力. LL ans = min(yAll, zAll); ans = ok ? min(ans, xwType1) : min(ans, xwType2); 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 |
[入力例] 3 1 5 4 2 6 3 [出力例] 7 ※AtCoderのテストケースより [入力例] 4 1 5 2 6 3 7 4 8 [出力例] 10 ※AtCoderのテストケースより [入力例] 6 19 92 64 64 78 48 57 33 73 6 95 73 [出力例] 227 ※AtCoderのテストケースより [入力例] 12 5 1 1 9 7 5 8 9 3 4 5 2 12 6 9 8 8 5 10 1 1 3 8 12 [出力例] 36 [入力例] 30 12215 3370 12177 7726 4964 2611 6560 7493 3018 11392 1528 6868 1961 12138 11793 3883 254 10220 1417 6974 7367 2308 1747 7212 1504 8640 6726 9102 3693 6369 8183 4441 5846 7052 1031 4780 9748 846 22 3277 836 6243 3161 4269 10999 557 10938 5665 2119 9823 11871 1250 7141 11419 4579 7586 1723 4740 4969 821 [出力例] 75679 |
■参照サイト
AtCoder Grand Contest 028