C++の練習を兼ねて, AtCoder Regular Contest 123 の 問題D (Inc, Dec – Decomposition) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 最小値を見つけることが出来る点に, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 123 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc123/editorial/2292 #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<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--) #define pb push_back #define all(x) x.begin(), x.end() LL a[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. p[i] を 保存. // |B[0]| = |x - 0| // |C[0]| = |x - A[0]| // |B[1]| = |x + max(0, A[1] - A[0])| // |C[1]| = |x - A[0] + max(0, A[0] - A[1])| // |B[2]| = |x + max(0, A[1] - A[0]) + max(0, A[2] - A[1])| // |C[2]| = |x - A[0] + max(0, A[0] - A[1]) + max(0, A[1] - A[2])| // |B[3]| = |x + max(0, A[1] - A[0]) + max(0, A[2] - A[1]) + max(0, A[3] - A[2])| // |C[3]| = |x - A[0] + max(0, A[0] - A[1]) + max(0, A[1] - A[2]) + max(0, A[2] - A[3])| // ... vl v1, v2; v1.pb(0); v2.pb(a[0]); repx(i, 1, N) v1.pb(v1.back() - max(0LL, a[i] - a[i - 1])); repx(i, 1, N) v2.pb(v2.back() - max(0LL, a[i - 1] - a[i])); // 3. sort. vl v; for(auto &p : v1) v.pb(p); for(auto &p : v2) v.pb(p); sort(all(v)); // 4. Σ|x - p[i]| の 最小値は? // -> x として (N - 1)番目, N番目 の 二通りがあり得るので, 小さい方を取得. LL x1 = v[N - 1], t1 = 0; for(auto &p : v) t1 += abs(x1 - p); LL x2 = v[N], t2 = 0; for(auto &p : v) t2 += abs(x2 - p); // 5. 出力. printf("%lld\n", min(t1, t2)); 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 |
[入力例] 3 1 -2 3 [出力例] 10 ※AtCoderテストケースより [入力例] 4 5 4 3 5 [出力例] 17 ※AtCoderテストケースより [入力例] 1 -10 [出力例] 10 ※AtCoderテストケースより [入力例] 5 3 1 -4 -1 5 [出力例] 28 [入力例] 10 8 -33 -53 22 54 -11 47 -1 -77 66 [出力例] 1430 [入力例] 20 1763 1124 -1228 -176 813 996 -1107 150 1133 221 -716 34 1 1261 -611 676 1142 358 751 2019 [出力例] 100000 [入力例] 50 17876 -19009 13813 10057 19167 11118 -20933 10157 13289 -11037 15048 19983 14283 -14907 19296 19134 12684 12279 13878 21662 18454 -13252 13365 11329 20028 17895 12020 13117 20000 12000 -11760 18693 -18805 14316 13121 14283 10636 20456 11957 18784 19373 19579 17064 -15614 16764 20012 -15000 10841 -19285 16925 [出力例] 8000000 |
■参照サイト
AtCoder Regular Contest 123