C++の練習を兼ねて, AtCoder Beginner Contest 260 の 問題E (At Least One) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 尺取り法, いもす法 の 復習ができたので 非常に良かったと思う.
3. 再度見直したところ, 前回実装した版(※テストケースで, A[i]がすべて同じで, B[i] が全て異なる場合)は, おそらく, TLE版に見えたため, ロジック修正の上, 再提出した.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 260 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／おそらくTLE版).
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 |
// 解き直し. // https://atcoder.jp/contests/abc260/editorial/4458 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, 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--) #define pb push_back int ma[202020], mb[202020], ans[202020]; int main(){ // 1. 入力情報. int N, M, n = 0; scanf("%d %d", &N, &M); vvi a(M + 1), b(M + 1); set<P> st; rep(i, N){ int u, v; scanf("%d %d", &u, &v); // A[i], B[i] の インデックス i. if(!st.count({u, v})){ a[u].pb(i); b[v].pb(i); ++n; } // 重複区間をチェックするために保存. st.insert({u, v}); } // 2. 尺取り法. int t = 0, bef = 1; repx(l, 1, M + 1){ // A[i](消滅). for(auto &p : a[l - 1]){ --ma[p]; if(mb[p] == 0) --t; } // B[i](消滅). for(auto &p : b[l - 1]){ --mb[p]; if(ma[p] == 0) --t; } // 区間[L, R] が 条件を満たすか？ int cur = 0; repx(r, bef, M + 1){ // 今回分. cur = r; // A[j](出現). for(auto &p : a[r]){ if(ma[p]) continue; ++ma[p]; if(mb[p] == 0) ++t; } // B[j](出現). for(auto &p : b[r]){ if(mb[p]) continue; ++mb[p]; if(ma[p] == 0) ++t; } // 条件を満たす区間[L, R]が見つかった. if(t == n){ // いもす法. // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定. ++ans[r - l + 1]; --ans[M - l + 2]; // 終了. break; } } // 前回分. bef = max(cur, l + 1); } // 3. 累積和. rep(i, M) ans[i + 1] += ans[i]; // 4. 出力. repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n"); return 0; } |
■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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
// AC版. // 解き直し. // https://atcoder.jp/contests/abc260/editorial/4458 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; 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 int ma[202020], mb[202020], ans[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi a(M + 1), b(M + 1); rep(i, N){ int u, v; scanf("%d %d", &u, &v); // A[i], B[i] の インデックス i. a[u].pb(i); b[v].pb(i); } // 2. 尺取り法. int t = 0, bef = 1, debug = 0; repx(l, 1, M + 1){ // A[i](消滅). for(auto &p : a[l - 1]){ ++debug; --ma[p]; if(mb[p] == 0) --t; } // B[i](消滅). for(auto &p : b[l - 1]){ ++debug; --mb[p]; if(ma[p] == 0) --t; } // 前回分. bef = max(bef, l); // 条件を満たす区間[L, R]が見つかった. if(t == N){ // いもす法. // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定. ++ans[bef - l + 1]; --ans[M - l + 2]; // 次へ. continue; } // 区間[L, R] が 条件を満たすか？ int cur = 0; repx(r, bef, M + 1){ // 今回分. cur = r; // A[j](出現). for(auto &p : a[r]){ ++debug; if(ma[p]) continue; ++ma[p]; if(mb[p] == 0) ++t; } // B[j](出現). for(auto &p : b[r]){ ++debug; if(mb[p]) continue; ++mb[p]; if(ma[p] == 0) ++t; } // 条件を満たす区間[L, R]が見つかった. if(t == N){ // いもす法. // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定. ++ans[r - l + 1]; --ans[M - l + 2]; // 終了. break; } } // 前回分. bef = max(cur, l + 1); } // 3. 累積和. rep(i, M) ans[i + 1] += ans[i]; // 4. 出力. // printf("debug=%d\n", debug); repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n"); 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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 |
[入力例] 3 5 1 3 1 4 2 5 [出力例] 0 1 3 2 1 ※AtCoderテストケースより [入力例] 1 2 1 2 [出力例] 2 1 ※AtCoderテストケースより [入力例] 5 9 1 5 1 7 5 6 5 8 2 6 [出力例] 0 0 1 2 4 4 3 2 1 ※AtCoderテストケースより [入力例] 3 7 1 5 2 4 3 6 [出力例] 0 0 3 4 3 2 1 [入力例] 10 20 5 9 5 15 2 16 8 11 3 10 11 16 8 13 7 17 3 9 4 11 [出力例] 0 0 0 0 0 0 0 0 1 4 6 7 7 7 6 5 4 3 2 1 [入力例] 25 50 2 26 20 32 9 27 4 11 18 26 2 17 3 26 9 15 8 14 9 17 3 30 5 17 8 25 6 36 20 33 15 37 3 27 6 11 1 22 3 30 6 15 16 43 8 19 10 26 13 20 [出力例] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 3 4 6 8 9 10 11 11 11 11 11 11 11 11 11 11 11 10 9 8 7 6 5 4 3 2 1 [入力例] 100 250 100 101 100 102 100 103 100 104 100 105 100 106 100 107 100 108 100 109 100 110 100 111 100 112 100 113 100 114 100 115 100 116 100 117 100 118 100 119 100 120 100 121 100 122 100 123 100 124 100 125 100 126 100 127 100 128 100 129 100 130 100 131 100 132 100 133 100 134 100 135 100 136 100 137 100 138 100 139 100 140 100 141 100 142 100 143 100 144 100 145 100 146 100 147 100 148 100 149 100 150 100 151 100 152 100 153 100 154 100 155 100 156 100 157 100 158 100 159 100 160 100 161 100 162 100 163 100 164 100 165 100 166 100 167 100 168 100 169 100 170 100 171 100 172 100 173 100 174 100 175 100 176 100 177 100 178 100 179 100 180 100 181 100 182 100 183 100 184 100 185 100 186 100 187 100 188 100 189 100 190 100 191 100 192 100 193 100 194 100 195 100 196 100 197 100 198 100 199 100 200 [出力例(debug=10301 から debug=401 に 改善した)] 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 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 [入力例] 200 1000 250 301 250 302 250 303 250 304 250 305 250 306 250 307 250 308 250 309 250 310 250 311 250 312 250 313 250 314 250 315 250 316 250 317 250 318 250 319 250 320 250 321 250 322 250 323 250 324 250 325 250 326 250 327 250 328 250 329 250 330 250 331 250 332 250 333 250 334 250 335 250 336 250 337 250 338 250 339 250 340 250 341 250 342 250 343 250 344 250 345 250 346 250 347 250 348 250 349 250 350 250 351 250 352 250 353 250 354 250 355 250 356 250 357 250 358 250 359 250 360 250 361 250 362 250 363 250 364 250 365 250 366 250 367 250 368 250 369 250 370 250 371 250 372 250 373 250 374 250 375 250 376 250 377 250 378 250 379 250 380 250 381 250 382 250 383 250 384 250 385 250 386 250 387 250 388 250 389 250 390 250 391 250 392 250 393 250 394 250 395 250 396 250 397 250 398 250 399 250 400 250 401 250 402 250 403 250 404 250 405 250 406 250 407 250 408 250 409 250 410 250 411 250 412 250 413 250 414 250 415 250 416 250 417 250 418 250 419 250 420 250 421 250 422 250 423 250 424 250 425 250 426 250 427 250 428 250 429 250 430 250 431 250 432 250 433 250 434 250 435 250 436 250 437 250 438 250 439 250 440 250 441 250 442 250 443 250 444 250 445 250 446 250 447 250 448 250 449 250 450 250 451 250 452 250 453 250 454 250 455 250 456 250 457 250 458 250 459 250 460 250 461 250 462 250 463 250 464 250 465 250 466 250 467 250 468 250 469 250 470 250 471 250 472 250 473 250 474 250 475 250 476 250 477 250 478 250 479 250 480 250 481 250 482 250 483 250 484 250 485 250 486 250 487 250 488 250 489 250 490 250 491 250 492 250 493 250 494 250 495 250 496 250 497 250 498 250 499 250 500 [出力例(debug=50651 から debug=801 に 改善した)] 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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 |
■参照サイト
AtCoder Beginner Contest 260
