C++の練習を兼ねて, AtCoder Regular Contest 119 の 問題C (ARC Wrecker 2) を解いてみた.
■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 119 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc119/editorial/1850 // 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 LL C[303030], D[303030]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ LL a; scanf("%lld", &a); // 累積和. C[i + 1] = C[i] + ((i & 1) ? -1 : +1) * a; } // 2. 座標圧縮. map<LL, int> m; rep(i, N + 1) m[C[i + 1]] = 0; int idx = -1; for(auto &p : m) p.b = ++idx; // 3. 集計. LL ans = 0; rep(i, N){ ++D[m[C[i]]]; ans += D[m[C[i + 1]]]; } // 4. 出力. 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 |
[入力例] 5 5 8 8 6 6 [出力例] 3 ※AtCoderテストケースより [入力例] 7 12 8 11 3 3 13 2 [出力例] 3 ※AtCoderテストケースより [入力例] 10 8 6 3 9 5 4 7 2 1 10 [出力例] 1 ※AtCoderテストケースより [入力例] 14 630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491 [出力例] 8 ※AtCoderテストケースより [入力例] 7 3 1 4 1 5 9 2 [出力例] 1 [入力例] 20 7 8 9 5 1 4 5 3 4 1 6 3 4 8 3 7 6 4 7 1 [出力例] 11 [入力例] 100 6 3 1 6 3 10 6 9 3 5 10 9 10 10 1 9 7 8 8 5 9 10 6 2 2 5 3 8 1 7 7 10 7 3 3 10 3 2 7 5 8 8 8 7 5 3 3 3 1 8 10 8 5 9 3 10 3 8 7 7 7 10 5 10 9 7 9 7 5 2 6 3 8 2 9 5 3 1 8 3 9 7 5 6 1 5 1 3 1 9 9 10 5 2 1 3 1 3 9 3 [出力例] 85 [入力例] 500 11 2 3 15 2 19 11 12 10 9 20 15 17 3 6 9 19 18 5 5 10 11 12 10 10 13 16 16 15 5 6 3 13 17 16 7 12 16 2 19 18 5 15 16 9 12 13 9 12 19 5 20 5 9 5 9 19 3 3 20 18 3 13 12 19 13 3 5 19 17 3 8 3 3 6 6 3 17 18 16 13 9 3 9 13 2 13 6 17 18 17 13 8 6 6 12 6 20 3 16 7 5 11 11 1 7 15 7 15 2 7 5 2 19 15 18 8 1 7 17 11 19 11 19 12 5 7 1 1 13 3 3 3 13 7 1 15 1 13 13 6 20 12 20 9 13 3 7 12 6 9 6 11 16 2 15 15 10 2 17 9 9 7 2 15 9 5 8 8 2 12 13 16 16 8 9 15 9 2 10 18 9 16 11 2 18 15 9 13 12 18 12 9 19 15 7 13 3 5 20 5 13 18 1 19 16 9 3 18 18 2 11 18 8 7 1 9 3 2 11 13 7 10 15 7 16 1 15 19 5 7 12 5 10 5 11 18 17 20 2 8 6 10 7 6 3 11 12 17 18 13 12 2 6 15 5 13 16 13 16 1 15 12 6 7 19 16 13 11 8 9 16 17 17 7 16 15 16 20 10 1 15 20 10 19 13 20 13 16 18 12 16 2 3 15 2 13 5 6 18 9 10 1 13 8 19 20 16 3 8 13 11 18 16 3 5 6 9 1 3 3 17 1 16 1 12 10 6 15 5 2 11 6 8 12 8 10 19 11 6 3 19 18 9 10 5 12 20 1 1 2 13 19 12 10 11 9 12 12 3 8 2 9 10 7 20 1 5 19 18 10 11 15 19 16 5 20 5 17 3 16 16 15 18 13 12 15 17 12 8 11 19 7 13 6 19 18 17 18 16 16 13 11 16 1 5 17 1 20 12 6 7 18 13 3 12 18 15 15 6 5 5 5 7 18 17 7 2 15 10 6 7 18 6 20 18 11 1 13 18 19 19 20 7 6 3 15 18 11 10 8 18 17 18 2 1 18 1 5 15 5 20 8 3 2 13 15 18 12 11 12 16 12 3 17 3 7 1 19 16 15 10 12 13 19 16 5 15 19 5 15 10 9 7 11 3 3 13 12 12 [出力例] 903 |
■参照サイト
AtCoder Regular Contest 119