C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題H (Red and Blue Lamps) を解いてみた.
■感想.
1. 問題H は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 実装に苦労したものの, 解説のロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 218 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題H/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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
// 解き直し. // https://atcoder.jp/contests/abc218/editorial/2602 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, int>; using PQ = priority_queue<P>; #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 b[202020]; int main(){ // 1. 入力情報. int N, R; scanf("%d %d", &N, &R); set<int> st; // インデックス(操作時に使う予定). st.insert(N - 1); rep(i, N - 1){ int a; scanf("%lld", &a); b[i + 0] += a; b[i + 1] += a; st.insert(i); } // 2. sort. PQ pq; rep(i, N) pq.push({b[i], i}); // 3. R回繰り返す. R = min(R, N - R); LL ans = 0; while(!pq.empty() && R > 0){ // 要素を取り出す. P u = pq.top(); pq.pop(); LL r = u.a; int i = u.b; // 左端, 右端 の インデックス. int idxL = *st.begin(); int idxR = *(--st.end()); // 左端 の 場合. bool ok = false; if(i == idxL){ // 報酬加算. ans += r; // B[0], B[1]削除 st.erase(st.begin()); st.erase(st.begin()); // フラグ更新. ok = true; } // 右端 の 場合. if(i == idxR){ // 報酬加算. ans += r; // B[N], B[N - 1]削除. st.erase(--st.end()); st.erase(--st.end()); // フラグ更新. ok = true; } // それ以外 の 場合. if(i != idxL && i != idxR){ // 存在しない場合. if(!st.count(i)) continue; // 報酬加算. ans += r; // B[i - 1], B[i], B[i + 1]取得. auto it = st.lower_bound(i); ++it; int tIdxR = *it; --it; --it; int tIdxL = *it; // B[i]更新. b[i] = b[tIdxL] - b[i] + b[tIdxR]; // 追加. pq.push({b[i], i}); // B[i - 1], B[i + 1]削除. st.erase(tIdxL); st.erase(tIdxR); // フラグ更新. ok = true; } // デクリメント. if(ok) R--; } // 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 |
[入力例] 6 2 3 1 4 1 5 [出力例] 11 ※AtCoderテストケースより [入力例] 7 6 2 7 1 8 2 8 [出力例] 10 ※AtCoderテストケースより [入力例] 11 7 12345 678 90123 45678901 234567 89012 3456 78901 23456 7890 [出力例] 46207983 ※AtCoderテストケースより [入力例] 6 2 36 48 38 17 53 [出力例] 156 [入力例] 19 5 314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582 [出力例] 6885 [入力例] 20 12 32 31 42 15 30 42 48 32 49 50 52 20 8 53 18 5 39 34 52 [出力例] 600 [入力例] 50 7 110253291 6598438 106440061 28086927 26995611 26360301 28139813 91640793 43706518 73883983 76021961 1862112 110168433 1690248 12891670 122635038 14674036 32936523 57191454 113582837 108343620 76232476 37982706 69888172 48331131 59780499 46229096 49313209 75487258 24643503 115387228 84672747 16152296 88398861 107703767 101929368 60941425 107935538 122741402 98294501 72886527 97016986 43783312 88844825 110587306 21450700 38539034 55714661 5368450 [出力例] 1390868077 |
■参照サイト
AtCoder Beginner Contest 218