C++の練習を兼ねて, AtCoder Beginner Contest 128 の 問題D (D – equeue) を解いてみた.
■感想.
1. 方針が見えなかったので, 解答を参考にコーディングしてみた.
2. priority_queue の 復習が出来たので, 良かったと思う.
本家のサイトABC 128解説をご覧下さい.
■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 |
// 解き直し. // ABC 128解説. // https://img.atcoder.jp/abc128/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; LL V[51]; typedef priority_queue<LL, vector<LL>, greater<LL>> PQ; int main() { // 1. 入力情報取得. LL N, K; scanf("%lld %lld", &N, &K); for(int i = 1; i <= N; i++) scanf("%lld", V + i); // 2. 解説通り. // 操作A, B を 行って, K - (A + B)回 捨てる操作. LL ans = 0; int upper = min(N, K); PQ pq0; // 2-1. 操作A で 宝石取り出す. for(int a = 0; a <= upper; a++){ if(a > 0) pq0.push(V[a]); PQ pq1 = pq0; // cout << "a=" << a << " pq1=" << pq1.size() << endl; // 2-2. 操作B で 宝石取り出す. for(int b = 0; b <= upper - a; b++){ if(b > 0) pq1.push(V[N + 1 - b]); PQ pq2 = pq1; int ret = K - (a + b); // cout << "b=" << b << " pq2=" << pq2.size() << endl; // 2-3. なるべく小さな負の価値の宝石を, 操作C, D で 戻す. LL total = 0; while(!pq2.empty()){ LL v = pq2.top(); pq2.pop(); if(v < 0 && ret > 0) ret--; // なるべく小さな負の価値の宝石を戻す. else total += v; // 宝石を戻さない場合は, キューが無くなるまで, 宝石の価値を加算. } // 2-4. 最大値を更新. ans = max(ans, total); } } // 3. 出力 ～ 後処理. 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 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 |
[入力例] 6 4 -10 8 2 1 2 6 [出力例(debug版)] a=0 pq1=0 b=0 pq2=0 b=1 pq2=1 b=2 pq2=2 b=3 pq2=3 b=4 pq2=4 a=1 pq1=1 b=0 pq2=1 b=1 pq2=2 b=2 pq2=3 b=3 pq2=4 a=2 pq1=2 b=0 pq2=2 b=1 pq2=3 b=2 pq2=4 a=3 pq1=3 b=0 pq2=3 b=1 pq2=4 a=4 pq1=4 b=0 pq2=4 14 ※AtCoderテストケースより [入力例] 6 4 -6 -100 50 -2 -5 -3 [出力例(debug版)] a=0 pq1=0 b=0 pq2=0 b=1 pq2=1 b=2 pq2=2 b=3 pq2=3 b=4 pq2=4 a=1 pq1=1 b=0 pq2=1 b=1 pq2=2 b=2 pq2=3 b=3 pq2=4 a=2 pq1=2 b=0 pq2=2 b=1 pq2=3 b=2 pq2=4 a=3 pq1=3 b=0 pq2=3 b=1 pq2=4 a=4 pq1=4 b=0 pq2=4 44 ※AtCoderテストケースより [入力例] 6 3 -6 -100 50 -2 -5 -3 [出力例(debug版)] a=0 pq1=0 b=0 pq2=0 b=1 pq2=1 b=2 pq2=2 b=3 pq2=3 a=1 pq1=1 b=0 pq2=1 b=1 pq2=2 b=2 pq2=3 a=2 pq1=2 b=0 pq2=2 b=1 pq2=3 a=3 pq1=3 b=0 pq2=3 0 ※AtCoderテストケースより [入力例] 7 5 1 5 -10 15 12 -3 2 [出力例(debug版)] a=0 pq1=0 b=0 pq2=0 b=1 pq2=1 b=2 pq2=2 b=3 pq2=3 b=4 pq2=4 b=5 pq2=5 a=1 pq1=1 b=0 pq2=1 b=1 pq2=2 b=2 pq2=3 b=3 pq2=4 b=4 pq2=5 a=2 pq1=2 b=0 pq2=2 b=1 pq2=3 b=2 pq2=4 b=3 pq2=5 a=3 pq1=3 b=0 pq2=3 b=1 pq2=4 b=2 pq2=5 a=4 pq1=4 b=0 pq2=4 b=1 pq2=5 a=5 pq1=5 b=0 pq2=5 29 [入力例] 47 85 -1 -12 -123 -1234 -12345 -123456 -1234567 -12345678 87654321 7654321 654321 54321 4321 321 21 1 -2 -23 -234 -2345 -23456 -234567 -2345678 -23456789 76543210 6543210 543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1 [出力例] 231823625 [入力例] 50 100 543210 43210 3210 210 10 0 -8 -78 -678 -5678 -45678 -345678 -2345678 -12345678 45678901 5678901 678901 78901 8901 901 1 -7 -67 -567 -4567 -34567 -234567 -1234567 98765432 8765432 765432 65432 5432 432 32 2 -6 -56 -456 -3456 -23456 -1234567 0 76543210 6543210 543210 43210 3210 210 10 [出力例] 244759153 |
■参照サイト
AtCoder Beginner Contest 128