C++の練習を兼ねて, AtCoder Beginner Contest 247 の 問題E (Max Min) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達出来た.
2. 尺取り法 の 復習ができたので 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 247 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc247/editorial/3736 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; 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--) #define pb push_back int main(){ // 1. 入力情報. int N, X, Y; scanf("%d %d %d", &N, &X, &Y); vvi bs; vi cur; rep(i, N){ int a; scanf("%d", &a); if(a >= Y && a <= X){ cur.pb(a); }else{ bs.pb(cur); cur.clear(); } } if(cur.size()) bs.pb(cur); // 2. カウント. LL ans = 0; for(auto &b : bs){ // 要素が存在するか? int n = b.size(); if(!n) continue; // 初期化. int r = 0; map<int, int> m; m[X] = m[Y] = 0; ++m[b[r]]; // 尺取り法. rep(l, n){ // 区間[l, r] が 条件を満たさない. while((r < n) && (!m[X] || !m[Y])) m[b[++r]]++; // 区間[l, r] が 見つかった. if(m[X] && m[Y]) ans += (LL)(n - r); // 次へ. --m[b[l]]; } } // 3. 出力. printf("%lld\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 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 |
[入力例] 4 3 1 1 2 3 1 [出力例] 4 ※AtCoderテストケースより [入力例] 5 2 1 1 3 2 4 1 [出力例] 0 ※AtCoderテストケースより [入力例] 5 1 1 1 1 1 1 1 [出力例] 15 ※AtCoderテストケースより [入力例] 10 8 1 2 7 1 8 2 8 1 8 2 8 [出力例] 36 ※AtCoderテストケースより [入力例] 2 3 1 1 3 [出力例] 1 [入力例] 2 2 1 1 3 [出力例] 0 [入力例] 10 7 3 6 3 11 3 7 2 7 7 4 3 [出力例] 3 [入力例] 25 12 5 1 17 13 12 11 8 9 5 10 12 20 13 4 9 14 3 9 23 10 4 5 10 5 7 12 [出力例] 10 [入力例] 100 321 123 199 123 191 123 246 222 300 321 252 321 317 333 284 199 321 172 123 90 166 277 123 119 205 321 124 299 123 296 196 138 319 184 145 124 205 110 331 209 163 123 318 209 361 223 321 150 269 123 182 276 193 245 129 334 278 332 189 174 302 374 233 296 248 123 341 196 127 318 270 271 183 333 296 373 110 135 123 183 272 221 321 260 123 110 333 321 227 123 321 313 87 321 155 319 141 123 339 251 321 123 [出力例] 69 [入力例] 500 3030 2020 3793 1694 2053 3838 3167 3304 3176 2960 1733 1762 2973 3982 3455 2532 3646 2976 2503 3502 2057 2137 3073 2160 3370 2931 2134 2462 2286 1819 3078 3689 3519 1808 3148 2227 3340 3813 3449 1560 2794 2363 3304 3030 2297 2068 2940 1577 2784 2111 3545 3293 1970 3285 3841 2697 3030 2020 2810 3453 2521 2437 2020 3230 3239 2151 2545 3726 2107 3522 3290 1678 3746 2692 3444 1514 3489 1574 1970 3699 2989 1862 2354 3449 1660 3590 2615 3447 1799 1836 3839 2650 2020 2516 3030 3710 3024 3902 3590 3952 3305 2877 3553 3732 3434 2184 3030 3044 3731 1997 1681 2386 2207 2587 2745 3740 1991 3429 3996 3950 3643 3718 3030 1848 3074 3452 2132 1889 2410 2256 2449 2621 1936 1871 3614 2807 3338 3701 3014 2938 1994 3121 2228 3525 3744 3140 3618 1923 3502 3277 3743 1654 3399 2992 2020 1848 3015 2637 2988 2672 3427 3130 2715 2157 2136 3874 2848 2418 3023 2970 2494 2194 3974 2035 3613 3091 1602 1718 3289 1504 2298 2256 1870 2629 3709 2057 3844 3999 2092 3239 1940 3670 3090 2598 1503 3938 2614 3712 2811 2149 1538 2004 1691 1592 1754 2516 3996 3961 3441 3230 1500 2512 2112 2020 2931 3376 3525 1956 1605 2519 2082 3907 3355 1976 2213 3168 1768 2320 1805 1714 1853 2224 3209 3519 2580 2027 3508 3030 3613 2295 1911 3875 2674 2253 3961 2647 1812 2207 1600 3646 3528 1963 1618 3382 3258 3289 2020 3479 2038 2863 2247 3534 3096 1642 3718 2725 2463 1673 2022 2457 3482 2020 2598 2626 3030 3030 3003 2929 2020 2714 3061 2020 2021 2022 2699 3030 3030 1858 2525 3905 3617 3401 2462 3781 2020 2620 1806 2333 1932 3507 3803 1547 2076 1530 3759 3879 2394 3076 2793 3159 3588 1913 2194 1634 3583 2647 2226 2779 3250 3340 3822 2134 1723 1854 2697 3828 1764 2766 2240 2513 3410 2951 1563 3034 3797 3643 2905 3397 2461 3935 3265 2215 3132 1571 1808 3507 2257 1976 3719 2813 3239 3284 2062 1749 3904 3099 3406 3412 2961 2294 2640 3215 3245 3190 3012 3569 3874 2545 2762 2611 3030 1802 2499 2463 3278 1812 3749 1803 3430 3464 3525 2755 2616 3806 3059 2431 3776 2064 3146 3030 2603 2020 3030 2662 2444 2125 2975 2020 2901 3030 2733 2952 2863 2154 2020 3386 2536 2020 3410 3030 3030 2020 2623 2492 2020 2716 2020 2020 2384 3030 2020 3150 3729 3464 3664 3030 3035 1522 1688 2858 1962 1944 1762 1538 2828 3704 2757 2020 2676 1668 1997 3682 3761 3834 2763 3538 2473 3809 3177 2237 3759 2674 2927 1999 1860 3815 1616 2141 1779 3259 3394 3064 3030 2505 1652 3432 1553 3986 2934 3956 2020 2718 2884 2179 2134 2020 3030 3030 2020 2788 2428 3214 2638 2453 1641 2123 2362 2958 2933 1511 1509 3030 2959 2020 2203 3030 2922 2020 2025 2290 3000 2587 [出力例] 207 [入力例] 1000 1000 1 932 190 139 235 540 339 635 678 815 476 812 108 167 393 708 261 770 747 214 776 464 220 771 713 860 521 603 194 718 382 721 102 807 904 524 153 844 180 600 386 827 125 838 516 183 749 693 546 435 415 401 262 683 395 92 156 213 865 296 229 888 62 200 593 473 723 500 452 887 949 924 388 363 94 851 400 489 198 798 205 189 329 589 695 905 287 312 226 394 712 841 112 969 196 313 310 347 925 459 359 147 383 97 725 175 286 56 631 84 378 617 872 596 526 484 637 269 642 795 735 545 177 963 7 46 858 862 796 632 856 941 989 135 32 217 239 639 582 953 478 861 252 104 75 120 527 4 697 148 44 89 929 685 757 772 675 461 980 983 651 343 171 848 279 714 10 577 67 488 320 987 565 813 487 645 787 325 842 446 996 595 641 954 575 111 462 686 567 37 727 106 351 116 878 790 999 784 633 53 497 179 573 288 5 291 301 676 402 682 381 598 846 853 556 55 338 278 469 957 47 193 687 331 503 184 731 734 689 788 479 782 211 165 96 204 583 832 506 19 544 25 356 525 519 99 454 724 282 614 671 511 864 437 399 760 829 181 463 318 309 17 35 938 387 413 15 766 173 442 828 561 586 847 710 33 977 699 83 663 726 903 958 169 571 988 837 27 913 601 121 344 268 449 850 302 648 979 879 495 375 899 271 423 36 1000 594 43 908 91 9 715 499 667 346 348 8 471 802 758 71 69 72 654 936 21 876 763 234 245 907 186 2 151 384 468 900 974 299 505 30 951 216 608 123 109 223 11 306 810 883 991 406 935 172 470 374 145 808 124 618 276 786 202 307 247 656 976 551 778 854 779 885 263 144 289 6 515 518 42 509 230 972 274 432 915 319 249 345 434 150 392 126 349 811 672 990 337 817 430 334 308 275 357 946 558 707 81 836 835 149 773 450 616 696 270 87 722 136 50 805 728 362 801 781 340 970 352 716 684 998 161 34 533 152 458 326 360 869 967 405 917 739 119 368 912 20 570 411 364 228 767 751 444 122 634 439 803 182 314 427 285 611 419 297 579 636 373 738 209 894 391 244 255 666 79 995 141 101 765 358 195 655 107 376 412 260 624 933 330 649 273 174 732 901 494 619 409 114 514 74 653 742 720 746 170 231 88 311 93 638 408 146 257 549 191 460 513 859 930 154 574 799 664 628 973 627 800 68 188 26 110 131 780 597 691 77 256 3 416 806 874 992 994 889 607 48 834 365 29 140 873 882 886 845 28 647 868 867 201 264 222 709 661 576 517 480 292 753 748 816 192 294 681 404 630 483 948 896 502 677 420 76 621 840 455 700 968 966 609 80 210 1 744 902 491 221 448 821 777 385 127 849 492 421 246 58 755 792 928 354 493 441 429 157 984 336 823 881 100 522 830 14 300 629 327 971 130 588 940 613 669 103 528 569 424 397 158 501 534 797 947 298 317 612 659 428 16 457 794 370 657 560 531 418 804 562 897 162 679 541 467 447 70 769 975 559 606 919 259 981 701 891 508 752 626 822 438 422 944 481 133 224 993 23 64 759 138 396 453 498 581 602 166 451 623 176 692 926 164 674 893 414 335 550 118 431 293 855 98 884 921 407 937 703 729 960 783 745 662 238 658 568 591 12 280 361 371 688 942 945 610 906 563 203 572 178 566 871 877 206 440 143 698 295 962 543 267 316 756 54 523 652 820 547 115 304 233 737 997 41 369 66 253 232 466 496 168 486 390 482 258 520 818 956 185 218 622 40 328 283 90 914 985 791 290 580 910 38 163 538 24 646 377 132 137 705 219 266 825 272 542 950 764 341 215 208 584 814 49 863 22 615 477 248 585 875 355 774 57 890 350 403 13 277 78 927 398 660 895 372 711 199 931 425 553 934 964 51 86 592 322 668 82 305 986 237 410 281 490 507 740 532 251 59 809 690 793 265 548 456 436 242 236 315 775 640 443 978 857 537 243 475 870 923 539 472 643 943 504 552 250 52 284 426 113 704 736 212 134 620 665 852 555 529 920 530 117 240 332 95 197 982 719 227 743 535 389 65 353 843 955 587 761 892 342 61 768 474 590 367 128 785 911 702 694 866 918 557 625 333 379 512 323 303 578 644 207 650 160 129 730 604 673 417 741 18 465 241 31 433 105 819 922 789 599 142 159 959 898 60 155 939 380 754 706 321 717 733 961 824 680 63 73 85 762 670 839 366 831 254 750 554 880 965 324 510 826 952 225 536 39 45 605 564 916 833 445 909 187 485 [出力例] 124745 |
■参照サイト
AtCoder Beginner Contest 247