C++の練習を兼ねて, AtCoder Regular Contest 129 の 問題D (-1+2-1) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 数式の性質から操作回数を決めていくロジックが, 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 129 解説 の 各リンク を ご覧下さい.
■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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://atcoder.jp/contests/arc129/editorial/2938 // 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--) LL A[202020], a[202020], b[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL t = 0; rep(i, N){ scanf("%lld", &A[i + 1]); t += A[i + 1]; } A[0] = A[N]; A[N + 1] = A[1]; // 2. 例外. if(t != 0){ puts("-1"); return 0; } // 3. 数列 b. // 3-1. 計算準備. // // b[2] - b[1] = A[2] // b[3] - b[2] = A[3] // ... // b[N] - b[N - 1] = A[N] // // -> 上記の (N - 1)個 の 数式は, 以下のように読み替えることができる. // b[2] - b[1] = A[2] // b[3] - b[1] = A[2] + A[3] // ... // b[N] - b[1] = A[2] + A[3] + ... + A[N] // // -> 左辺 の 合計は? // (b[2] + b[3] + ... + b[N]) - b[1] * (N - 1) = -b[1] - b[1] * (N - 1) = - b[1] * N が 分かる. LL B1 = A[2]; b[2] = A[2]; rep(i, N - 2){ b[i + 3] = b[i + 2] + A[i + 3]; B1 += b[i + 3]; } // 3-2. 例外. if(B1 % N != 0){ puts("-1"); return 0; } // 3-3. 計算. B1 /= -N; b[1] = B1; repx(i, 2, N + 1) b[i] += b[1]; // 4. 数列 a. // 4-1. 計算準備. // a[2] - a[1] = b[1] // a[3] - a[2] = b[2] // ... // a[N] - a[N - 1] = b[N - 1] // // -> 上記の (N - 1)個 の 数式は, 以下のように読み替えることができる. // a[2] - a[1] = b[1] // a[3] - a[1] = b[1] + b[2] // ... // a[N] - a[1] = b[1] + b[2] + ... + b[N - 1] LL aMin = 202020202020202020, bSum = 0; bSum = b[1]; aMin = min(aMin, bSum); rep(i, N - 2){ bSum += b[i + 2]; aMin = min(aMin, bSum); } // 4-2. a[1] を 決める. a[1] = (aMin < 0) ? -aMin : 0; // 4-3. 計算. repx(i, 1, N) a[i + 1] = a[i] + b[i]; // 5. 操作回数. LL ans = 0; rep(i, N) ans += a[i + 1]; // 6. 出力. 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 |
[入力例] 4 3 0 -1 -2 [出力例] 5 ※AtCoderのテストケースより [入力例] 3 1 0 -2 [出力例] -1 ※AtCoderのテストケースより [入力例] 4 1 -1 1 -1 [出力例] -1 ※AtCoderのテストケースより [入力例] 10 -28 -3 90 -90 77 49 -31 48 -28 -84 [出力例] 962 ※AtCoderのテストケースより [入力例] 5 2 0 5 -3 -4 [出力例] 12 [入力例] 20 32 114 -39 -57 12 -77 -51 70 -23 120 21 -26 77 -25 88 -93 11 -101 -80 27 [出力例] 6054 [入力例] 44 -2 5 -6 7 0 -11 11 -5 -1 4 1 -2 -3 4 -8 5 2 4 -9 6 -6 8 -6 1 1 5 -10 4 6 -3 -6 -1 7 4 -6 -4 1 11 -10 -4 11 -2 -9 6 [出力例] 213 |
■参照サイト
AtCoder Regular Contest 129