C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題H (Snuketoon) を解いてみた.
■感想.
1. 問題Hは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
※ 解説プログラムが, Python実装だったので, C++版に置き換えて提出した.
2. 新しい知識として, Slope Trick に触れることが出来たので, 非常に良かったと思う.
3. 今後も, 新しいアルゴリズムを, 少しずつ学習していきたいと思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 217 解説 の 各リンク を ご覧下さい.
■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 |
// 解答不能. // https://atcoder.jp/contests/abc217/editorial/2581 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using PQ = priority_queue<LL, vector<LL>, greater<LL>>; #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--) // Slope Trick. // https://atcoder.jp/contests/abc217/editorial/2581 // https://maspypy.com/slope-trick-1-解説編 // -> 一部改変. struct SlopeTrick{ PQ L; // 傾き 0以下で, 傾きの変化点全体の多重集合. PQ R; // 傾き 0以上で, 傾きの変化点全体の多重集合. LL addL, addR, minF; SlopeTrick(int n){ addL = 0LL; addR = 0LL; minF = 0LL; rep(i, n + 1) L.push(0LL); rep(i, n + 1) R.push(0LL); } void pushLeft(LL x){ L.push(-x + addL); } void pushRight(LL x){ R.push(x - addR); } LL topLeft(){ return -L.top() + addL; } LL topRight(){ return R.top() + addR; } LL popLeft(){ LL ret = -L.top() + addL; L.pop(); return ret; } LL popRight(){ LL ret = R.top() + addR; R.pop(); return ret; } void addXsubA(LL a){ minF += (L.size() ? max(0LL, topLeft() - a) : 0LL); pushLeft(a); pushRight(popLeft()); } void addAsubX(LL a){ minF += (R.size() ? max(0LL, a - topRight()) : 0LL); pushRight(a); pushLeft(popRight()); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. ゲームを進める. SlopeTrick st(N); LL t = 0; rep(i, N){ // 今回分取得. LL T, D, X; scanf("%lld %lld %lld", &T, &D, &X); // Slope Trick を 更新. st.addL -= T - t; st.addR += T - t; if(D) st.addXsubA(X); else st.addAsubX(X); // 前回分保存. t = T; } // 3. 出力. printf("%lld\n", st.minF); 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 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 |
[入力例] 3 1 0 3 3 1 0 4 0 6 [出力例] 7 ※AtCoderテストケースより [入力例] 3 1 0 1 6 1 1 8 0 -1 [出力例] 0 ※AtCoderテストケースより [入力例] 5 1 0 1000000000 2 1 -1000000000 3 0 1000000000 4 1 -1000000000 5 0 1000000000 [出力例] 4999999997 ※AtCoderテストケースより [入力例] 7 1 0 3 3 1 -2 7 0 5 8 0 -1 12 1 -2 17 1 -3 20 0 6 [出力例] 11 ※実際, 以下の動作をすると, 合計 11 の ダメージを受ける. t = 1 (地点) +1 (ダメージ) +3 - 1 = +2 t = 3 (地点) -1 (ダメージ) -1 - (-2) = +1 t = 7 (地点) +3 (ダメージ) +5 - 3 = +2 t = 8 (地点) +2 (ダメージ) +2 >= -1 なので無し. t = 12 (地点) -2 (ダメージ) -2 == -2 なので無し. t = 17 (地点) -3 (ダメージ) -3 == -3 なので無し. t = 20 (地点) 0 (ダメージ) +6 - 0 = +6 [入力例] 12 1 1 5 2 1 8 4 0 -6 7 1 10 10 1 -1 13 0 7 17 0 -2 19 1 8 23 0 9 25 1 -11 29 1 3 30 0 15 [出力例] 34 ※実際, 以下の動作をすると, 合計 34 の ダメージを受ける. t = 1 (地点) +1 (ダメージ) +1 <= +5 なので無し. t = 2 (地点) +2 (ダメージ) +2 <= +8 なので無し. t = 4 (地点) +4 (ダメージ) +4 >= -6 なので無し. t = 7 (地点) +1 (ダメージ) +1 <= +10 なので無し. t = 10 (地点) 0 (ダメージ) 0 - (-1) = +1 t = 13 (地点) +3 (ダメージ) +7 - (+3) = +4 t = 17 (地点) -1 (ダメージ) -1 >= -2 なので無し. t = 19 (地点) +1 (ダメージ) +1 <= +8 なので無し. t = 23 (地点) +1 (ダメージ) +9 - (+1) = +8 t = 25 (地点) -1 (ダメージ) -1 - (-11) = +10 t = 29 (地点) +3 (ダメージ) +3 == +3 なので無し. t = 30 (地点) +4 (ダメージ) +15 - (+4) = +11 |