C++の練習を兼ねて, AtCoder Beginner Contest 267 の 問題B (Split?) ～ 問題E (Erasing Vertices 2) を解いてみた.
■感想.
1. 問題D, Eは, いったん実装してみたものの, 方針が誤っていたので, 解説を参考に, AC版に到達できたと思う.
2. 問題D で, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 実装に苦労したものの 問題Eで, 二分探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 267 解説 の 各リンク を ご覧下さい.
■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 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 126 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. char c[22]; scanf("%s", c); string s(c); // 2. 出力. // 2-1. ピン 1 が 立っている. if(s[0] == '1'){ puts("No"); return 0; } // 2-2. ピン 4 が 倒れている. if(s[3] == '0'){ // ピン 7. int l = s[6] - '0'; // ピン 2, 3, 5, 6, 8, 9, 10. int r = s[1] - '0'; r += s[2] - '0'; r += s[4] - '0'; r += s[5] - '0'; r += s[7] - '0'; r += s[8] - '0'; r += s[9] - '0'; // スプリット. if(l && r){ puts("Yes"); return 0; } } // 2-3. ピン 2, 8 が 倒れている. if(s[1] == '0' && s[7] == '0'){ // ピン 4, 7. int l = s[3] - '0'; l += s[6] - '0'; // ピン 3, 5, 6, 9, 10. int r = s[2] - '0'; r += s[4] - '0'; r += s[5] - '0'; r += s[8] - '0'; r += s[9] - '0'; // スプリット. if(l && r){ puts("Yes"); return 0; } } // 2-4. ピン 1, 5 が 倒れている. if(s[4] == '0'){ // ピン 2, 4, 7, 8. int l = s[1] - '0'; l += s[3] - '0'; l += s[6] - '0'; l += s[7] - '0'; // ピン 3, 6, 9, 10. int r = s[2] - '0'; r += s[5] - '0'; r += s[8] - '0'; r += s[9] - '0'; // スプリット. if(l && r){ puts("Yes"); return 0; } } // 2-5. ピン 3, 9 が 倒れている. if(s[2] == '0' && s[8] == '0'){ // ピン 2, 4, 5, 7, 8. int l = s[1] - '0'; l += s[3] - '0'; l += s[4] - '0'; l += s[6] - '0'; l += s[7] - '0'; // ピン 6, 10. int r = s[5] - '0'; r += s[9] - '0'; // スプリット. if(l && r){ puts("Yes"); return 0; } } // 2-6. ピン 6 が 倒れている. if(s[5] == '0'){ // ピン 2, 3, 4, 5, 7, 8, 9. int l = s[1] - '0'; l += s[2] - '0'; l += s[3] - '0'; l += s[4] - '0'; l += s[6] - '0'; l += s[7] - '0'; l += s[8] - '0'; // ピン 10. int r = s[9] - '0'; // スプリット. if(l && r){ puts("Yes"); return 0; } } // 2-7. 上記以外. puts("No"); 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 |
[入力例] 0101110101 [出力例] Yes ※AtCoderテストケースより [入力例] 0100101001 [出力例] Yes ※AtCoderテストケースより [入力例] 0000100110 [出力例] No ※AtCoderテストケースより [入力例] 1101110101 [出力例] No ※AtCoderテストケースより [入力例] 0101010101 [出力例] Yes [入力例] 0110110110 [出力例] No |
■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 |
// 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--) LL a[202020], aCum[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); LL cur = 0; rep(i, N){ scanf("%lld", &a[i]); aCum[i + 1] = aCum[i] + a[i]; if(i < M) cur += a[i] * (LL)(i + 1); } // 2. 最大値は？ LL ans = cur; repx(i, 1, N - M + 1){ cur += a[i - 1 + M] * (LL)M; cur -= (aCum[i - 1 + M] - aCum[i - 1]); ans = max(ans, cur); } // 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 |
[入力例] 4 2 5 4 -1 8 [出力例] 15 ※AtCoderテストケースより [入力例] 10 4 -3 1 -4 1 -5 9 -2 6 -5 3 [出力例] 31 ※AtCoderテストケースより [入力例] 20 5 66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66 [出力例] 1000 [入力例] 50 7 16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77 [出力例] 1327 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc267/editorial/4728 // 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--) const LL INF = 101010101010101010; LL dp[2020][2020], a[2020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &a[i]); // 2. 初期化(解説通り). rep(i, N + 1) repx(j, i + 1, N + 1) dp[i][j] = -INF; // 3. dp更新. repx(i, 1, N + 1){ repx(j, 1, i + 1){ dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] * (LL)j); } } // 4. 出力. printf("%lld\n", dp[N][M]); 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 |
[入力例] 4 2 5 4 -1 8 [出力例] 21 ※AtCoderテストケースより [入力例] 10 4 -3 1 -4 1 -5 9 -2 6 -5 3 [出力例] 54 ※AtCoderテストケースより [入力例] 20 5 66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66 [出力例] 1352 [入力例] 50 7 16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77 [出力例] 3000 |
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc267/editorial/4729 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; #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 LL a[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &a[i]); vvi G(N); rep(i, M){ int u, v; scanf("%d %d", &u, &v); --u; --v; G[u].pb(v); G[v].pb(u); } // 2. 評価関数. auto f = [&](LL m) -> bool { // 2-1. 初期化. LL cost[N]; int memo[N]; rep(i, N) cost[i] = memo[i] = 0; rep(i, N) for(auto &u : G[i]) cost[i] += a[u]; // 2-2. スタック に 追加. stack<int> st; rep(i, N) if(cost[i] <= m) st.push(i), ++memo[i]; // 2-3. 操作. while(!st.empty()){ // 頂点を取り出す. int u = st.top(); st.pop(); // 隣接頂点を確認. for(auto &v : G[u]){ if(!memo[v]){ // コスト減算. cost[v] -= a[u]; // コストが, m以下ならば, 頂点 を スタック に 追加. if(cost[v] <= m) st.push(v), ++memo[v]; } } } // 2-4. 未削除の頂点が残っているか？ bool ok = false; rep(i, N) if(!memo[i]) ok = true; // 2-5. 判定結果. return ok; }; // 3. 二分探索で確認してみる. // test_10.txt ～ test_13.txt で, WA版だったため, l = 0 でなく, l = -1 に修正. // -> これらのテストケースは, M = 0 に, 該当すると予想. LL l = -1, h = 202020202020202020, m; while(l + 1 < h){ LL m = (h + l) >> 1; if(f(m)) l = m; else h = m; } // 4. 出力. printf("%lld\n", h); 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 |
[入力例] 4 3 3 1 4 2 1 2 1 3 4 1 [出力例] 3 ※AtCoderテストケースより [入力例] 7 13 464 661 847 514 74 200 188 5 1 7 1 5 7 4 1 4 5 2 4 5 2 1 3 1 6 3 5 1 2 4 6 2 7 [出力例] 1199 ※AtCoderテストケースより [入力例] 3 0 7 5 3 [出力例] 0 [入力例] 5 6 222 106 77 51 333 1 2 2 3 3 1 3 4 1 4 4 5 [出力例] 234 [入力例] 15 20 97 35 65 88 53 49 65 37 101 29 65 68 55 49 75 1 4 1 5 2 1 7 1 6 4 6 2 3 2 13 2 13 11 13 3 11 3 5 8 5 15 15 14 14 8 8 7 8 9 9 7 9 12 9 10 [出力例] 123 [入力例] 22 28 463 888 999 1084 21 1220 1213 375 132 748 1188 61 612 1077 982 501 668 1042 533 273 1226 134 1 2 1 8 1 9 1 17 3 2 3 20 3 9 4 3 4 5 20 21 21 22 22 20 17 18 18 19 19 17 8 7 7 9 7 6 7 14 14 15 15 16 16 15 5 9 5 6 5 11 11 12 12 13 13 11 [出力例] 1234 |