C++の練習を兼ねて, AtCoder Beginner Contest 253 の 問題G (Swap Many Times) を解いてみた.
■感想.
1. 問題Gは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 253 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G/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 127 128 129 130 131 132 |
// 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--) int a[202020], ans[202020]; int main(){ // 1. 入力情報. int N; LL L, R; scanf("%d %lld %lld", &N, &L, &R); // 2. 事前準備. // 以下のように, 前半(L ~ X - 1), 中盤(X ~ Y), 後半(Y + 1 ~ R) に 分ける. // N = 8, L = 10, R = 24 の 場合. // (1, 2) // (1, 3) // (1, 4) // (1, 5) // (1, 6) // (1, 7) // (1, 8) // (2, 3) // (2, 4) // (2, 5) => L = 10 // (2, 6) // (2, 7) // (2, 8) // (3, 4) => X = 14 // (3, 5) // (3, 6) // (3, 7) // (3, 8) // (4, 5) // (4, 6) // (4, 7) // (4, 8) => Y = 22 // (5, 6) // (5, 7) => R = 24 // (5, 8) // (6, 7) // (6, 8) // (7, 8) // 2-1. 初期化. repx(i, 1, N + 1) a[i] = i; // 2-2. 情報整理(X, Y). LL X = 0, Y = 0; int x = 0, y = 0; repr(i, N - 1, 1){ if(X < L){ X += (LL)i; ++x; if(X >= L){ ++X; ++x; } } if(Y < R){ Y += (LL)i; ++y; if(Y > R){ Y -= (LL)i; --y; break; } } } // 2-3. 情報整理(L). // L = (la, lb) と 置く. LL lSum = 0; int la = 0, lb = 0; repx(i, 1, N){ lSum += (LL)(N - i); if(lSum >= L){ la = i; lb = N - (int)(lSum - L); break; } } // 2-4. 情報整理(R). // R = (ra, rb) と 置く. LL rSum = 0; int ra = 0, rb = 0; repx(i, 1, N){ rSum += (LL)(N - i); if(rSum >= R){ ra = i; rb = N - (int)(rSum - R); break; } } // 3. 例外. if(la == ra){ repx(i, lb, rb + 1) swap(a[la], a[i]); repx(i, 1, N + 1) printf("%d%s", a[i], (i < N) ? " " : "\n"); return 0; } // 4. Swap操作. // 4-1. 前半(L ~ X - 1). repx(i, lb, N + 1) swap(a[la], a[i]); // 4-2. 中盤(X ~ Y). // 中盤(X ~ Y) では, 以下の性質を利用することを検討. // X = (x, x + 1), Y = (y, N) と 置いた場合. // // [開始] // a[1], a[2], ..., a[x - 1], a[x], a[x + 1], ..., a[N - (y - x) - 1], a[N - (y - x)], ..., a[N - 1], a[N] // // [終了] // a[1], a[2], ..., a[x - 1], a[N], a[N - 1], ..., a[N - (y - x)], a[x], a[x + 1]..., a[N - (y - x) - 1] repx(i, 1, x) ans[i] = a[i]; rep(i, y - x + 1) ans[x + i] = a[N - i]; rep(i, N - y) ans[y + 1 + i] = a[x + i]; // 4-3. 後半(Y + 1 ~ R). if(Y < R) repx(i, y + 2, rb + 1) swap(ans[y + 1], ans[i]); // 5. 出力. repx(i, 1, N + 1) printf("%d%s", ans[i], (i < N) ? " " : "\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 |
[入力例] 5 3 6 [出力例] 5 1 2 3 4 ※AtCoderテストケースより [入力例] 10 12 36 [出力例] 1 10 9 8 7 4 3 2 5 6 ※AtCoderテストケースより [入力例] 3 1 1 [出力例] 2 1 3 [入力例] 3 1 2 [出力例] 3 1 2 [入力例] 3 1 3 [出力例] 3 2 1 [入力例] 4 1 1 [出力例] 2 1 3 4 [入力例] 4 1 2 [出力例] 3 1 2 4 [入力例] 4 1 3 [出力例] 4 1 2 3 [入力例] 4 1 4 [出力例] 4 2 1 3 [入力例] 4 1 5 [出力例] 4 3 1 2 [入力例] 4 1 6 [出力例] 4 3 2 1 [入力例] 8 10 24 [出力例] 1 8 7 6 2 3 4 5 [入力例] 12 25 50 [出力例] 1 2 12 11 10 8 4 5 6 3 7 9 [入力例] 30 123 321 [出力例] 1 2 3 4 30 29 28 27 26 25 24 23 22 21 12 6 7 8 9 10 11 13 14 15 16 17 5 18 19 20 [入力例] 50 256 512 [出力例] 1 2 3 4 5 50 49 48 47 46 45 34 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 6 27 28 29 30 31 32 33 35 36 37 38 39 40 41 42 43 44 [入力例] 100 2020 3030 [出力例] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 100 99 98 97 96 23 95 94 93 92 91 90 89 88 87 57 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 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 [入力例] 500 11111 111111 [出力例] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421 420 419 418 417 416 415 414 413 412 411 410 409 408 407 406 405 404 403 402 401 400 399 398 397 396 395 394 393 392 391 390 389 388 387 23 386 385 384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 304 303 302 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 80 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 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 |
■参照サイト
NOMURA プログラミングコンテスト2022(AtCoder Beginner Contest 253)