C++の練習を兼ねて, AtCoder Beginner Contest 271 の 問題C (Manga) ～ 問題D (Flip and Adjust) を解いてみた.
■感想.
1. 問題Cは, 実装したもののロジック誤りが修正出来なかったため, 解説を参考に, AC版に到達できた.
2. 問題Dで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 271 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc271/editorial/4930 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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); multiset<int> mst; rep(i, N){ int a; scanf("%d", &a); // 1-1. N より大きな巻. if(a > N){ mst.insert(N + 1); continue; } // 1-2. 二冊以上ある. if(mst.count(a)){ mst.insert(N + 1); continue; } // 1-3. それ以外. mst.insert(a); } // 2. 単行本売買. int ans = 0; repx(i, 1, N + 1){ // 2-1. 単行本を持っている. auto s = mst.begin(); if(i == *s){ ++ans; mst.erase(mst.find(*s)); continue; } // 2-2. 単行本を持ってない. if(mst.size() < 2) break; mst.erase(mst.find(*(--mst.end()))); mst.erase(mst.find(*(--mst.end()))); ++ans; } // 3. 出力. printf("%d\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 |
[入力例] 6 1 2 4 6 7 271 [出力例] 4 ※AtCoderテストケースより [入力例] 10 1 1 1 1 1 1 1 1 1 1 [出力例] 5 ※AtCoderテストケースより [入力例] 1 5 [出力例] 0 ※AtCoderテストケースより [入力例] 10 1 2 3 4 5 6 7 8 9 10 [出力例] 10 [入力例] 12 1 2 2 2 4 5 6 7 8 9 10 8 [出力例] 10 [入力例] 25 70 77 52 10 56 11 95 80 93 7 66 74 114 8 4 1 66 2 34 35 8 42 55 74 60 [出力例] 16 [入力例] 100 89 161 141 234 1 38 245 4 22 15 12 16 123 33 65 201 114 174 155 150 121 245 161 146 23 7 13 191 178 193 53 7 221 122 242 86 174 150 116 98 24 8 14 112 185 9 168 10 96 58 176 201 179 8 17 210 155 72 208 151 217 240 96 22 215 18 190 178 123 50 73 233 117 20 111 88 6 208 126 2 210 11 178 19 35 3 215 224 171 223 5 108 12 85 168 21 239 51 250 216 [出力例] 66 |
■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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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() bool dp[101][10101][2]; int a[101], b[101]; int main(){ // 1. 入力情報. int N, S; scanf("%d %d", &N, &S); rep(i, N) scanf("%d %d", &a[i], &b[i]); // 2. dp更新. dp[0][0][0] = dp[0][0][1] = 1; rep(i, N){ repr(j, S, 0){ // 表. int h = a[i] + j; if(h <= S){ if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][h][0] = true; } // 裏. int t = b[i] + j; if(t <= S){ if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][t][1] = true; } } } // 3. 例外. if(!dp[N][S][0] && !dp[N][S][1]){ puts("No"); return 0; } // 4. カードの置き方は？ string ans = ""; int s = S; ans.pb(dp[N][S][0] ? 'H' : 'T'); s -= dp[N][S][0] ? a[N - 1] : b[N - 1]; repr(i, N - 2, 0){ // 表. if(s >= 0 && dp[i + 1][s][0]){ ans.pb('H'); s -= a[i]; continue; } // 裏. if(s >= 0 && dp[i + 1][s][1]){ ans.pb('T'); s -= b[i]; } } // 5. 反転. reverse(all(ans)); // 6. 出力. printf("%s\n%s\n", "Yes", ans.c_str()); 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 126 127 128 129 130 131 132 133 134 135 136 137 138 |
[入力例] 3 11 1 4 2 3 5 7 [出力例] Yes THH ※AtCoderテストケースより [入力例] 5 25 2 8 9 3 4 11 5 1 12 6 [出力例] No ※AtCoderテストケースより [入力例] 7 18 2 3 2 4 2 3 3 2 9 5 1 2 3 1 [出力例] Yes HHHHTHH [入力例] 7 18 3 2 4 2 3 2 2 3 5 9 2 1 1 3 [出力例] Yes HTHHHHH [入力例] 5 15 1 3 3 1 1 3 3 1 1 3 [出力例] Yes THTHT [入力例] 12 210 18 5 12 12 15 12 7 18 7 15 24 12 8 25 18 13 8 22 12 1 23 21 8 2 [出力例] Yes HHHTTHTHTHHH [入力例] 50 2022 40 93 24 85 78 30 54 5 25 40 92 65 36 29 23 77 83 84 82 73 57 2 1 31 98 28 35 17 66 93 54 70 72 1 28 79 72 83 68 74 81 62 32 26 59 75 5 87 13 27 68 77 47 11 40 80 27 41 95 51 21 21 93 90 17 32 95 25 31 87 80 25 47 45 14 60 89 96 90 56 59 26 5 47 83 99 32 18 79 85 1 11 87 20 79 1 14 85 57 91 [出力例] Yes HHTTHTTHHTTHTTHHTHHTTHHHHHTHHTHHHTHTHHHTHHHHHHHHHH |