C++の練習を兼ねて, AtCoder Grand Contest 040 の 問題B (Two Contests) を解いてみた.
■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 040 解説 を ご覧下さい.
■C++版プログラム(問題B／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 |
// 解き直し. // https://img.atcoder.jp/agc040/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--) #define pb push_back #define all(x) x.begin(), x.end() const LL INF = 202020202020202020; LL l[101010], r[101010], as[101010], bt[101010]; struct joy{ int i; LL a, b; bool operator < (const joy& rhs) const{ return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b)); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); LL ans = 0, maxL = 0, minR = INF; int p = -1, q = -1; rep(i, N){ scanf("%lld %lld", &l[i], &r[i]); if(maxL < l[i]){ maxL = l[i]; p = i; } if(minR > r[i]){ minR = r[i]; q = i; } ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存. } ans += max(0LL, minR - maxL + 1LL); // 2. 解説通り. vector<joy> v; rep(i, N){ LL a = max(r[i] - maxL + 1LL, 0LL); LL b = max(minR - l[i] + 1LL, 0LL); joy j; j.i = i; j.a = a; j.b = b; v.pb(j); } // 3. sort. sort(all(v)); // for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b); // 4. 事前準備. rep(i, N + 1) as[i] = bt[i] = INF; repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a); rep(i, N) bt[i + 1] = min(bt[i], v[i].b); // rep(i, N + 1) printf("%lld ", as[i]); // puts(""); // rep(i, N + 1) printf("%lld ", bt[i]); // puts(""); // 5. 最大値は？ repx(i, 1, N) ans = max(ans, as[i] + bt[i]); // 6. 出力. 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
[入力例] 4 4 7 1 4 5 8 2 5 [出力例] 6 ※AtCoderテストケースより [入力例] 4 1 20 2 19 3 18 4 17 [出力例] 34 ※AtCoderテストケースより [入力例] 10 457835016 996058008 456475528 529149798 455108441 512701454 455817105 523506955 457368248 814532746 455073228 459494089 456651538 774276744 457667152 974637457 457293701 800549465 456580262 636471526 [出力例] 540049931 ※AtCoderテストケースより [入力例] 25 1 6 17 23 16 31 7 22 4 5 3 13 19 27 7 13 11 22 2 3 6 21 3 19 3 13 7 7 15 20 2 11 9 23 17 25 6 15 15 19 9 19 4 5 15 19 1 2 11 21 [出力例] 17 |
■参照サイト
AtCoder Grand Contest 040