C++の練習を兼ねて, AtCoder Regular Contest 100 の 問題D (Equal Cut) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できた.
2. 尺取り法(応用版) の 訓練 が 出来たので良かったと思う.
3. TLE版の実装における, R, S の 計算について, 単調増加の性質が欠けていたことに気付いて, AC版のような実装へ修正できたことが大きな収穫だったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 100 解説 を ご覧下さい.
■C++版プログラム(問題D／TLE版).
|
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 |
// 解き直し. // https://img.atcoder.jp/arc092/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--) LL a[202020], aCum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 累積和. rep(i, N) aCum[i + 1] = aCum[i] + a[i]; // 3. 数列に切れ込みを入れる. int idxL = 0, idxR = 3; LL ans = 202020202020202020, debugL = 0, debugR = 0; repx(m, 2, N - 1){ // ※TLEに注意. // 6331[ms]かかったテストケース(subtask_1_08.txt)の場合, 処理回数について, // 左側: 73113回 右側: 5345510769回 と カウントされた. // 中央の切れ込みを, m番目 と (m + 1)番目 の 間 とする. // 左側の切れ込みを, l番目 と (l + 1)番目 の 間 とする. LL P, Q, PQ, pq = 202020202020202020; repx(l, idxL, m){ P = aCum[l + 1]; Q = aCum[m] - aCum[l + 1]; PQ = abs(P - Q); if(pq >= PQ){ pq = PQ; }else{ // idxL更新. idxL = l - 1; P = aCum[l]; Q = aCum[m] - aCum[l]; break; } debugL++; } // 右側の切れ込みを, r番目 と (r + 1)番目 の 間 とする. LL R, S, RS, rs = 202020202020202020; repx(r, idxR, N){ R = aCum[r] - aCum[m]; S = aCum[N] - aCum[r]; RS = abs(R - S); if(rs >= RS){ rs = RS; }else{ // idxR更新. idxR = r - 1; R = aCum[r - 1] - aCum[m]; S = aCum[N] - aCum[r - 1]; break; } debugR++; } // P, Q, R, S の 最大値, 最小値 の 差 の 絶対値について, 最小値 を 更新. ans = min(ans, max({P, Q, R, S}) - min({P, Q, R, S})); } // 4. 出力. // printf("debugL=%lld debugR=%lld\n", debugL, debugR); printf("%lld\n", ans); return 0; } |
■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://img.atcoder.jp/arc092/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--) LL a[202020], pqCum[202020], rsCum[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 累積和. rep(i, N){ pqCum[i + 1] = pqCum[i] + a[i]; rsCum[i + 1] = rsCum[i] + a[N - 1 - i]; } // 3. 数列に切れ込みを入れる. // TLE版で, 6331[ms]かかったテストケース(subtask_1_08.txt)の場合, 処理回数について, // 左側: 73113回 右側: 73113回 と カウントが大幅に減少した. // -> 実行時間は, 16[ms] に 改善された. // なお, TLE版では, R, S を 求める部分で, R = aCum[r - 1] - aCum[m]; の ように, // 計算していたため, 単調増加の性質が, 欠けるケースが出現するため, // 計算量が, O(N) に 収まらない現象が発生したと理解する. // 3-1. P, Q を 求める. vector<LL> P(N), Q(N); int idx = 0; LL debugL = 0; repx(m, 2, N - 1){ // 中央の切れ込みを, m番目 と (m + 1)番目 の 間 とする. // 左側の切れ込みを, l番目 と (l + 1)番目 の 間 とする. LL tP, tQ, tPQ, t = 202020202020202020; repx(l, idx, m){ tP = pqCum[l + 1]; tQ = pqCum[m] - pqCum[l + 1]; tPQ = abs(tP - tQ); if(t >= tPQ){ t = tPQ; }else{ // idx更新. idx = l - 1; tP = pqCum[l]; tQ = pqCum[m] - pqCum[l]; // P, Q 保存. P[m] = tP; Q[m] = tQ; break; } debugL++; } } // 3-2. R, S を 求める. vector<LL> R(N), S(N); idx = 0; LL debugR = 0; repx(m, 2, N - 1){ // 中央の切れ込みを, m番目 と (m + 1)番目 の 間 とする. // 右側の切れ込みを, r番目 と (r + 1)番目 の 間 とする. LL tR, tS, tRS, t = 202020202020202020; repx(r, idx, m){ tR = rsCum[r + 1]; tS = rsCum[m] - rsCum[r + 1]; tRS = abs(tR - tS); if(t >= tRS){ t = tRS; }else{ // idx更新. idx = r - 1; tR = rsCum[r]; tS = rsCum[m] - rsCum[r]; // R, S 保存. R[N - m] = tR; S[N - m] = tS; break; } debugR++; } } // 4. P, Q, R, S の 最大値, 最小値 の 差 の 絶対値について, 最小値 を 更新. LL ans = 202020202020202020; repx(m, 2, N - 1) ans = min(ans, max({P[m], Q[m], R[m], S[m]}) - min({P[m], Q[m], R[m], S[m]})); // 5. 出力. // printf("debugL=%lld debugR=%lld\n", debugL, debugR); 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 |
[入力例] 5 3 2 4 1 2 [出力例] 2 ※AtCoderテストケースより [入力例] 10 10 71 84 33 6 47 23 25 52 64 [出力例] 36 ※AtCoderテストケースより [入力例] 7 1 2 3 1000000000 4 5 6 [出力例] 999999994 ※AtCoderテストケースより [入力例] 50 89 27 61 105 4 101 108 28 83 3 18 64 70 89 55 109 75 115 11 7 63 9 112 103 93 58 79 117 51 7 11 18 33 113 4 97 43 79 10 110 103 24 11 51 95 52 75 40 97 45 [出力例] 68 [入力例] 123 18384837 100840309 84097639 96990740 66888400 47520626 17205717 7837921 49142859 20137744 66458483 72021663 77050497 39869874 46908029 9601243 30899185 54309467 61740506 2024917 25869186 39300515 115293846 70747377 51523872 75345959 55484275 75476466 25966262 86973675 102711256 45507158 49605866 107394982 1555300 36770700 48502302 106625299 24932643 6074727 120829341 47602613 52227677 14076577 90708464 59265829 89310234 9585988 80129950 3113769 93209980 108242882 11553009 42477467 99356288 86371054 9531237 39602149 72509336 28336036 4763943 7146767 2445920 102183980 48940665 105558471 26391729 63368885 109878055 4104754 54019376 35396552 23091887 14675674 109247389 36221136 51967909 47142561 100946563 97259787 24166661 91607291 48469085 52741172 30501694 95384610 33860300 26635540 67006114 69444800 102053317 108730615 10432089 23453060 75672957 24576142 95934467 74433970 90130837 26194905 10543170 86144484 35785716 47492169 71067819 39958460 74184686 54997682 12373432 99590402 14157889 78202354 81961345 48767329 14945309 22976054 65420745 5125004 49599458 108080120 106053874 34319914 20458441 [出力例] 98515184 |
■参照サイト
AtCoder Regular Contest 100