C++の練習を兼ねて, AtCoder Grand Contest 025 の 問題C (Interval Game) を解いてみた.
■感想.
1. 問題C は, 解答方針が見えなかったので, 解説を参考に実装した.
2. 非常に苦労したものの, AC版まで到達出来たので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 025 解説 を ご覧下さい.
■C++版プログラム(問題C／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 116 117 118 119 120 121 122 123 124 125 |
// 解き直し. // https://img.atcoder.jp/agc025/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using T3 = tuple<LL, LL, int>; #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--) int main(){ // 1. 入力情報. int N; scanf("%d", &N); priority_queue<T3> lPQ; priority_queue<T3, vector<T3>, greater<T3>> rPQ; deque<T3> dqL1, dqR1, dqL2, dqR2; rep(i, N){ LL l, r; scanf("%lld %lld", &l, &r); lPQ.emplace(l, r, i); rPQ.emplace(r, l, i); } // 2. sort結果を保存. // 2-1. 左側. while(!lPQ.empty()){ T3 t = lPQ.top(); lPQ.pop(); LL l = get<0>(t); LL r = get<1>(t); int i = get<2>(t); // printf("l=%lld r=%lld i=%d\n", l, r, i); dqL1.emplace_back(l, r, i); dqL2.emplace_back(l, r, i); } // 2-2. 右側. while(!rPQ.empty()){ T3 t = rPQ.top(); rPQ.pop(); LL l = get<1>(t); LL r = get<0>(t); int i = get<2>(t); // printf("l=%lld r=%lld i=%d\n", l, r, i); dqR1.emplace_back(l, r, i); dqR2.emplace_back(l, r, i); } // 3. ゲーム実施. auto f = [&](int N, bool b, deque<T3> &dql, deque<T3> &dqr) -> LL{ LL ret = 0, cur = 0; set<int> idx; // 訪問済みの区間番号. rep(i, N){ // 右向き. if(b){ while(!dql.empty()){ // 区間取得. T3 t = dql.front(); dql.pop_front(); LL l = get<0>(t); LL r = get<1>(t); int i = get<2>(t); // 未訪問の場合に, 移動. bool ok = false; if(idx.count(i) == 0){ // 訪問済みの区間を保存. idx.insert(i); // 右方向に進む. if(cur < l) ret += (l - cur), cur = l; // 方向の切り替え. b = !b; // 移動完了. ok = true; } // 移動方向が変わったかをチェック. if(ok) break; } } // 左向き. if(!b){ while(!dqr.empty()){ // 区間取得. T3 t = dqr.front(); dqr.pop_front(); LL l = get<0>(t); LL r = get<1>(t); int i = get<2>(t); // 未訪問の場合に, 移動. bool ok = false; if(idx.count(i) == 0){ // 訪問済みの区間を保存. idx.insert(i); // 左方向に進む. if(cur > r) ret += (cur - r), cur = r; // 方向の切り替え. b = !b; // 移動完了. ok = true; } // 移動方向が変わったかをチェック. if(ok) break; } } } // 原点に戻る(ゲーム終了). ret += abs(cur); // 返却. return ret; }; // 3-1. 右方向からスタートした場合. LL rAns = f(N, 1, dqL1, dqR1); // 3-2. 左方向からスタートした場合. LL lAns = f(N, 0, dqL2, dqR2); // 4. 出力. printf("%lld\n", max(rAns, lAns)); 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 86 87 |
[入力例] 3 -5 1 3 7 -4 -2 [出力例] 10 ※AtCoderのテストケースより [入力例] 3 1 2 3 4 5 6 [出力例] 12 ※AtCoderのテストケースより [入力例] 5 -2 0 -2 0 7 8 9 10 -2 -1 [出力例] 34 ※AtCoderのテストケースより [入力例] 50 643 725 -882 -759 116 205 -658 -535 523 546 -531 -408 427 461 -995 -872 122 229 -232 -109 824 838 -446 -323 35 152 724 751 -295 -172 143 169 652 679 -175 -52 722 756 244 299 126 197 -389 -266 395 505 653 737 742 743 957 1042 579 603 70 155 -31 92 -597 -474 -182 -59 -866 -743 662 761 -926 -803 -679 -556 528 609 -872 -749 -968 -845 463 466 -1000 -877 -73 50 -941 -818 317 371 -937 -814 531 607 -25 98 -211 -88 525 610 -446 -323 -235 -112 [出力例] 44790 |
■参照サイト
AtCoder Grand Contest 025