C++の練習を兼ねて, AtCoder Regular Contest 133 の 問題A (Erase by Value) ～ 問題B (Dividing Subsequence) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. LIS(Longest increase subsequence) の 応用版(追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 133 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A／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 vi = vector<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); vi a(N); rep(i, N) scanf("%d", &a[i]); // 2. x を 求める. int x = a[0]; rep(i, N){ // 減少. if(x > a[i]) break; // 増加. if(x < a[i]) x = a[i]; } // 3. 出力. rep(i, N){ if(a[i] == x) continue; else printf("%d ", a[i]); } 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 |
[入力例] 5 2 4 4 1 2 [出力例] 2 1 2 ※AtCoderのテストケースより [入力例] 3 1 1 1 [出力例] ※AtCoderのテストケースより [入力例] 5 1 1 2 3 3 [出力例] 1 1 2 ※AtCoderのテストケースより [入力例] 7 3 1 4 1 5 9 2 [出力例] 1 4 1 5 9 2 [入力例] 20 1 1 2 2 3 3 5 5 7 7 7 7 11 11 11 10 5 3 2 1 [出力例] 1 1 2 2 3 3 5 5 7 7 7 7 10 5 3 2 1 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc133/editorial/3283 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using P = pair<int, int>; using vp = vector<P>; #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 a first #define b second #define all(x) x.begin(), x.end() int p[202020], q[202020]; int main(){ // 1. 入力情報. int N, x; scanf("%d", &N); rep(i, N){ scanf("%d", &x); p[x] = i + 1; } rep(i, N){ scanf("%d", &x); q[x] = i + 1; } // 2. Q[j] が P[i] の 倍数になっているペアは？ vp v; repx(i, 1, N + 1) repex(j, i, N + 1, i) v.pb({p[i], -q[j]}); // 3. sort. sort(all(v)); // 4. 狭義単調増加な数列の長さの最大値は？ // 以下の問題を参照. // https://atcoder.jp/contests/typical90/tasks/typical90_bh // -> LIS(Longest increase subsequence) を 利用. vi dp; for(auto &p : v){ // 数列を保存. // -> 但し, 符号を反転したもので, 保存等を行うこと. if(dp.size() == 0 || dp.back() < -p.b){ dp.pb(-p.b); }else{ int at = lower_bound(all(dp), -p.b) - dp.begin(); dp[at] = -p.b; } } // 5. 出力. printf("%d\n", dp.size()); 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 |
[入力例] 4 3 1 4 2 4 2 1 3 [出力例] 2 ※AtCoderのテストケースより [入力例] 5 1 2 3 4 5 5 4 3 2 1 [出力例] 3 ※AtCoderのテストケースより [入力例] 10 4 3 1 10 9 2 8 6 5 7 9 6 5 4 2 3 8 10 1 7 [出力例] 6 ※AtCoderのテストケースより [入力例] 25 10 24 16 19 21 5 8 9 18 3 25 17 7 4 11 14 2 1 22 15 23 13 6 12 20 22 4 18 23 1 24 17 6 14 12 11 2 13 21 7 5 15 3 16 25 19 9 20 10 8 [出力例] 10 [入力例] 100 68 49 78 16 97 82 47 41 69 44 38 45 36 32 92 66 33 10 57 94 52 100 30 75 59 89 37 83 11 55 17 60 50 71 28 2 20 12 81 53 3 96 19 42 14 1 67 70 58 72 23 98 51 56 84 95 6 26 79 73 8 13 48 5 80 63 29 85 76 31 34 90 25 65 86 99 54 77 62 74 91 7 87 35 22 4 9 40 43 64 27 24 15 93 46 61 18 21 39 88 78 11 52 79 82 46 90 8 83 80 39 58 35 54 3 6 75 51 76 27 13 96 33 25 65 2 43 20 92 21 60 84 9 74 30 63 32 19 22 14 86 55 15 85 100 61 37 34 81 23 1 40 26 59 94 47 70 88 89 71 62 69 87 7 68 66 4 44 48 36 95 67 10 38 12 64 45 72 24 16 28 93 99 17 53 42 18 29 97 41 56 49 91 73 77 5 50 98 31 57 [出力例] 27 [入力例] 250 117 221 242 13 123 219 175 25 243 129 83 20 199 44 244 67 183 150 74 241 86 130 235 124 3 41 73 79 232 142 58 170 37 162 43 210 230 248 194 80 68 21 55 7 19 229 192 169 171 96 187 109 8 184 163 52 133 200 215 225 228 48 45 30 2 211 216 250 118 197 177 165 35 111 212 85 51 32 112 23 234 78 105 206 167 247 75 77 213 164 193 181 54 144 172 92 120 22 159 90 10 125 128 100 49 148 131 222 231 160 238 11 139 180 134 5 18 4 138 201 224 233 246 119 64 99 106 101 154 190 158 40 27 166 214 186 102 70 84 205 149 38 39 140 155 185 61 108 31 196 66 189 69 93 245 173 145 72 89 141 126 59 115 110 153 226 202 176 113 137 57 94 17 218 60 136 174 122 237 182 81 198 127 91 98 29 104 1 6 208 76 62 179 116 147 9 178 239 191 50 143 87 82 209 15 188 152 135 65 28 204 132 121 33 14 157 223 42 161 88 220 156 203 114 227 103 47 95 240 12 36 46 56 107 207 249 151 97 146 63 217 53 236 24 34 26 168 16 195 71 53 240 65 148 59 167 138 76 17 98 220 64 127 130 70 110 88 116 194 56 55 231 32 219 154 214 182 63 54 1 82 153 85 31 40 135 170 155 102 6 193 180 244 81 179 142 131 22 11 77 212 43 217 103 227 75 69 15 198 118 66 174 232 26 140 169 225 132 166 125 242 195 177 62 172 126 78 37 197 238 185 68 191 250 222 38 187 196 147 176 115 226 105 44 165 230 90 151 25 35 188 45 16 243 209 93 192 10 61 112 136 161 34 48 181 95 137 104 2 229 96 168 4 211 221 101 133 178 24 241 206 21 124 83 215 107 190 149 100 186 113 199 97 207 92 84 108 89 74 73 111 52 119 129 42 72 51 58 173 143 152 9 247 139 12 3 13 223 208 14 184 146 144 67 237 7 8 91 94 36 235 120 28 246 157 228 163 39 41 128 150 27 86 145 117 248 23 218 200 224 141 239 249 33 80 46 79 204 47 158 216 183 122 57 114 29 123 162 121 60 164 210 205 134 19 18 49 234 109 245 175 201 156 159 106 20 236 202 30 213 203 233 99 189 160 5 71 87 171 50 [出力例] 45 |