C++の練習を兼ねて, AtCoder Beginner Contest 262 の 問題F (Erase and Rotate) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. スライド最小値（応用版） を, 確認できたので, 非常に良かったと思う.
3. 実装に苦労したものの, スライド最小値 に対して, 理解を, 深めることが出来たので良かったと思う.
4. なお, 解説上の “回転を1回以上行う場合” について, “回転なし” の ケース を 参考に, スライド最小値で実装したものの, テストケース 05_hand_01.txt の WA を 回避出来なかった.
解決方法が見えなかったため, スライド最小値 と 思われる実装されている上級者の方々のソースから, 変数(r[cur], k2) や 処理(dq2.pob(), else) の 組み合わせ を 特定して, 修正版として提出したものである.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 262 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc262/editorial/4504 // 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--) #define pub push_back #define pob pop_back int p[202020], r[202020]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N) scanf("%d", &p[i]); // 2. 回転なし. // 2-1. シミュレーション. int k1 = K; deque<int> dq1; rep(i, N){ // スライド最小値. // https://phwinx.hatenablog.com/entry/2018/11/17/042646 // -> 先頭要素に, 最小値が保存されている状態を目指す. // 削除. while(k1 && !dq1.empty()){ if(dq1.back() <= p[i]) break; --k1; dq1.pob(); } // 追加. dq1.pub(p[i]); } // 2-2. k1 の 残分. while(k1 && !dq1.empty()){ --k1; dq1.pob(); } // for(auto &x : dq1) printf("%d ", x); // puts("\n-----"); // 3. 回転あり. // 3-1. 先頭の項が最小となる回転数. int rMin = 0, pMin = N + 1; repr(i, N - 1, 0){ if(N - i <= K && pMin > p[i]){ rMin = N - i; pMin = p[i]; } } // 3-2. 操作対象の数列. vi p2; repx(i, N - rMin, N) p2.pub(p[i]), ++r[p[i]]; rep(i, N - rMin) p2.pub(p[i]); // 3-3. シミュレーション. int k2 = K - rMin; deque<int> dq2; rep(i, N){ // 削除. // -> スライド最小値 の 考え方を拡張する必要があるとのこと. while(!dq2.empty()){ int cur = dq2.back(); if(cur <= p2[i]) break; // ex. // 6 3 // 4 5 6 1 3 2 // -> r[cur] と dq2.pob() と --k2 の 処理条件の組み合わせに注意する. // -> 組み合わせを間違えると, 1 3 2 4 5 6 のような誤出力となる. // -> 05_hand_01.txt で WAとなった原因とみられるもの. // -> なお, 1 2 4 5 6 が 期待される出力. if(r[cur]){ dq2.pob(); }else if(k2){ --k2; dq2.pob(); }else{ break; } } // 追加. dq2.pub(p2[i]); } // 3-4. k2 の 残分. while(k2 && !dq2.empty()){ int cur = dq2.back(); --k2; dq2.pob(); } // for(auto &x : dq2) printf("%d ", x); // puts("\n-----"); // 4. 比較. bool ok = (dq1 < dq2); // 5. 出力. int n = ok ? dq1.size() : dq2.size(); rep(i, n) printf("%d%s", ok ? dq1[i] : dq2[i], (i < n - 1) ? " " : "\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 |
[入力例] 5 3 4 5 2 3 1 [出力例] 1 2 3 ※AtCoderのテストケースより [入力例] 3 0 3 2 1 [出力例] 3 2 1 ※AtCoderのテストケースより [入力例] 15 10 12 10 7 2 8 11 9 1 6 14 3 15 13 5 4 [出力例] 1 3 4 7 2 8 11 9 ※AtCoderのテストケースより [入力例] 20 5 13 1 15 10 20 14 5 12 7 4 18 16 8 19 2 17 6 9 3 11 [出力例] 1 5 12 7 4 18 16 8 19 2 17 6 9 3 11 [入力例] 20 7 10 6 19 7 14 15 2 17 12 9 3 18 8 11 20 4 5 1 13 16 [出力例] 1 6 7 2 17 12 9 3 18 8 11 20 4 5 [入力例] 50 32 7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10 [出力例] 1 2 3 23 32 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 [入力例] 50 49 7 13 37 31 20 14 48 35 27 3 45 23 47 41 38 32 46 6 12 26 39 44 33 36 16 24 11 50 29 5 34 18 1 28 19 4 17 15 25 22 2 43 9 30 49 8 40 42 21 10 [出力例] 1 [入力例] 100 77 7 6 36 85 8 17 38 50 28 22 44 87 59 99 42 81 4 35 45 56 84 89 52 65 77 88 90 70 55 92 23 27 24 72 39 95 14 63 20 48 67 61 100 53 26 73 96 5 97 79 49 98 31 76 33 94 60 78 13 64 32 9 37 51 66 16 57 19 10 75 29 41 82 46 40 12 25 34 30 15 93 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86 1 69 [出力例] 1 4 5 9 10 12 15 68 58 43 2 91 80 62 47 11 21 3 71 18 83 74 54 86 [入力例] 200 123 125 31 193 196 91 105 61 111 108 159 50 173 194 88 57 37 172 19 104 185 124 96 161 129 35 13 45 99 138 72 154 156 81 151 53 178 179 11 95 86 155 198 92 87 115 89 113 157 162 23 12 49 16 121 117 29 114 85 83 33 149 142 58 137 158 5 52 36 90 127 60 126 80 66 41 100 28 135 69 47 44 82 101 79 174 123 55 17 166 27 143 84 15 94 68 8 190 112 98 199 39 181 128 186 170 163 122 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109 1 152 32 21 131 7 200 51 134 48 110 148 46 197 56 25 140 191 26 [出力例] 1 5 8 39 59 145 133 18 4 20 74 76 164 169 136 77 78 62 119 34 38 102 2 167 192 93 144 182 107 120 183 168 63 42 40 9 75 67 64 10 150 146 139 176 24 6 22 97 43 160 177 180 106 189 147 184 132 70 71 175 65 141 187 103 3 30 14 73 165 171 54 116 153 188 130 195 118 109 [入力例] 1000 567 692 605 661 39 9 936 931 368 906 789 127 37 583 910 530 886 865 10 788 2 170 814 226 46 996 513 866 228 547 266 357 260 844 701 114 526 815 802 468 17 308 284 19 755 681 898 582 741 31 278 584 14 413 984 479 900 481 631 911 647 889 539 376 434 212 738 419 418 438 415 54 847 319 509 751 854 51 712 965 141 256 850 795 611 868 528 327 962 386 606 769 414 332 679 596 929 77 538 264 25 836 768 321 206 607 722 832 267 499 915 163 125 469 916 586 55 950 123 667 708 43 156 590 143 576 307 207 511 884 378 158 442 353 555 940 373 685 118 627 422 562 171 999 253 448 101 969 841 251 409 370 345 683 806 903 761 358 364 492 752 213 554 662 172 506 658 478 410 956 715 91 563 641 305 926 826 403 666 1000 655 790 888 848 391 525 293 352 963 876 947 989 648 147 372 758 306 801 41 838 323 295 247 338 15 742 896 778 292 728 476 552 575 638 567 592 417 805 22 785 501 988 303 446 632 239 536 879 912 725 365 126 467 273 861 953 745 870 842 289 899 629 772 349 593 709 642 959 6 909 244 645 687 490 621 682 23 429 736 558 161 633 485 243 155 542 68 299 937 630 561 87 735 863 45 917 489 809 180 425 830 13 440 710 724 933 88 779 340 674 711 882 986 656 816 227 727 361 406 329 892 521 309 824 978 35 393 285 160 964 189 635 897 186 350 297 38 794 935 447 439 775 238 44 502 508 5 152 771 948 182 262 646 764 760 510 732 86 787 90 318 351 34 66 918 497 799 183 581 236 961 640 644 696 776 671 951 545 218 83 216 232 360 315 678 215 523 16 699 618 423 591 529 311 192 480 24 477 97 444 754 992 654 428 407 330 50 923 120 139 52 42 913 934 166 73 96 746 825 336 250 196 187 780 1 348 873 199 457 987 904 191 757 326 878 201 810 93 164 598 819 209 695 577 553 995 449 972 669 759 894 743 625 298 672 106 594 272 905 70 395 543 109 550 960 867 173 571 704 531 394 200 713 404 833 431 84 79 798 874 691 537 556 230 211 296 880 72 921 49 565 356 472 811 167 520 636 747 421 205 380 257 800 784 47 495 975 76 928 643 782 612 958 871 33 29 651 990 246 450 202 142 148 694 157 150 665 80 869 475 544 855 639 770 970 840 275 652 69 807 107 111 435 220 234 548 610 829 858 980 159 574 138 570 657 864 108 875 389 92 791 198 739 703 859 254 566 224 730 61 362 53 955 223 774 914 891 117 684 938 237 845 781 369 660 922 181 57 274 130 484 719 169 268 971 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804 [出力例] 1 29 53 57 130 169 268 437 496 473 78 453 67 930 408 518 763 74 263 149 486 95 993 128 628 18 384 344 634 482 343 585 81 670 381 134 677 441 862 688 500 820 834 668 102 693 587 740 981 233 217 616 622 697 952 942 290 994 249 877 700 944 885 30 64 821 21 347 578 333 604 28 328 240 827 976 846 991 907 458 416 462 144 498 310 954 135 470 887 26 153 967 488 20 60 822 165 765 541 371 94 849 204 129 136 717 367 924 269 957 58 99 3 514 424 608 705 580 354 105 902 803 534 737 374 883 623 133 919 908 609 797 390 579 551 281 777 231 288 85 121 452 569 276 852 314 291 265 750 673 116 813 808 786 188 483 856 258 783 208 219 325 837 653 282 707 145 615 40 533 853 949 387 432 733 411 313 176 966 322 943 675 925 342 762 261 573 245 540 203 723 154 252 377 731 698 983 324 464 512 835 242 773 115 977 927 920 589 184 366 720 392 331 436 400 454 122 559 532 997 283 335 4 650 515 459 194 831 504 383 726 398 595 721 151 839 32 430 113 210 255 767 619 7 426 626 549 146 271 689 190 59 503 796 601 753 602 363 162 734 620 985 62 792 617 624 818 748 546 507 27 603 270 225 487 979 812 341 399 175 443 229 355 277 463 828 649 860 474 564 637 168 517 382 75 396 248 535 505 857 385 124 941 893 597 375 316 516 82 119 221 112 71 901 286 131 968 178 304 433 716 195 388 817 100 659 36 494 137 179 197 491 600 945 749 456 522 302 301 460 193 465 851 557 132 973 259 235 613 998 287 690 766 455 11 572 466 346 932 702 317 588 402 614 48 427 337 104 412 714 599 103 568 140 56 982 461 974 524 664 706 881 729 312 872 279 843 8 185 12 401 823 527 445 174 560 793 300 110 663 397 686 222 359 493 676 241 451 379 756 63 294 946 280 895 939 334 744 214 420 339 177 519 471 98 680 405 65 89 890 320 718 804 [入力例] 6 3 4 5 6 1 3 2 [出力例] 1 2 4 5 6 |