C++の練習を兼ねて, AtCoder Regular Contest 077 の 問題E (guruguru) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 解説を参考に, おそらくこのような処理だろう, と推測しながら実装したため, 非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト
AtCoder Regular Contest 077 解説
をご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://img.atcoder.jp/arc077/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--) int a[202020], b[202020]; LL up[202020], down[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%d", &a[i]); // 2. お気に入り(x = 0 -> x = M に 読み替え)を使う場合. LL cnt = 0; repx(i, 1, N){ if(a[i - 1] > a[i]) cnt += (LL)(a[i] + (M - a[i - 1] > 0)); else if(a[i] == M) cnt++; else cnt += (LL)(a[i] - a[i - 1]); } // 3. 増加分. repx(i, 1, N) up[a[i]] += (LL)((a[i] + M - a[i - 1]) % M - 1); // rep(i, M + 1) printf("i=%d up=%d\n", i, up[i]); // 4. 減少分. // a[i] と a[i + 1] の 間に x があるような iの個数. rep(i, N - 1){ int s = a[i] + 1; if(s > M) s -= M; if(a[i + 1] - a[i] > 1){ b[s]++, b[a[i + 1]]--; } if(a[i + 1] < a[i] && a[i + 1] + M - a[i] > 1){ if(s > 1) b[s]++, b[M + 1]--; b[1]++, b[a[i + 1]]--; } } rep(i, M) down[i + 1] = down[i] + (LL)b[i + 1]; // rep(i, M + 1) printf("i=%d down=%d\n", i, down[i]); // 5. 出力. LL ans = cnt, bef = cnt, cur = 0; repx(x, 1, M){ // 今回分更新. int idx = (x - 1) == 0 ? M : x - 1; cur = bef + up[idx] - down[idx]; // printf("cur=%d bef=%d up=%d down=%d\n", cur, bef, up[idx], down[idx]); // 最小値更新. ans = min(ans, cur); // 前回分更新. bef = cur; } 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 |
[入力例] 4 6 1 5 1 4 [出力例] 5 ※AtCoderのテストケースより [入力例] 10 10 10 9 8 7 6 5 4 3 2 1 [出力例] 45 ※AtCoderのテストケースより [入力例] 5 2 1 2 1 2 1 [出力例] 4 [入力例] 5 3 2 1 3 2 1 [出力例] 6 [入力例] 7 7 1 5 2 6 7 4 3 [出力例] 15 [入力例] 30 23 16 19 11 11 17 20 4 6 23 11 8 5 18 5 20 9 3 13 15 1 6 6 15 9 14 9 22 21 9 1 [出力例] 193 |
■参照サイト
AtCoder Regular Contest 077