C++ の動作確認をしてみた（６８８）

C++の練習を兼ねて, AtCoder Beginner Contest 144 の問題E (Gluttony) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 144 解説をご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://img.atcoder.jp/abc144/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    vl a, b;
    rep(i, N){
        LL t;
        scanf("%lld", &t);
        a.pb(t);
    }
    rep(i, N){
        LL t;
        scanf("%lld", &t);
        b.pb(t);
    }
    
    // 2. sort.
    sort(all(a));
    sort(all(b));
    reverse(all(b));
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. 修行回数をカウント.
        // -> 完食にかかる時間を, m 以下にできるかを, 各メンバー毎に確認し,
        //    超過分は, 修行回数に反映させる.
        LL k = 0;
        rep(i, N){
            LL t = a[i] * b[i] - m;
            if(t > 0){
                LL q = t / b[i];
                LL r = t % b[i];
                k += q + (r > 0);
            }
        }
        
        // 3-2. 判定結果.
        return (k <= K);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = -1, h = 2e12 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1LL;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc144/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

LL K;

scanf("%d %lld", &N, &K);

vl a, b;

rep(i, N){

LL t;

scanf("%lld", &t);

a.pb(t);

}

rep(i, N){

LL t;

scanf("%lld", &t);

b.pb(t);

}

// 2. sort.

sort(all(a));

sort(all(b));

reverse(all(b));

// 3. 評価関数.

auto f = [&](LL m) -> bool {

// 3-1. 修行回数をカウント.

// -> 完食にかかる時間を, m 以下にできるかを, 各メンバー毎に確認し,

// 超過分は, 修行回数に反映させる.

LL k = 0;

rep(i, N){

LL t = a[i] * b[i] - m;

if(t > 0){

LL q = t / b[i];

LL r = t % b[i];

k += q + (r > 0);

}

// 3-2. 判定結果.

return (k <= K);

};

// 4. 二分探索で確認してみる.

LL l = -1, h = 2e12 + 1, m;

while(l + 1 < h){

LL m = (h + l) >> 1LL;

if(f(m)) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 5. 出力.

printf("%lld\n", h);

return 0;

}

[入力例]
3 5
4 2 1
2 3 1

[出力例]
2
※AtCoderテストケースより

[入力例]
3 8
4 2 1
2 3 1

[出力例]
0
※AtCoderテストケースより

[入力例]
11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2

[出力例]
12
※AtCoderテストケースより

[入力例]
5 12
3 6 5 4 7
5 3 7 2 1

[出力例]
7

[入力例]
20 32
81 18 82 83 42 20 32 50 37 37 37 117 119 63 99 104 34 29 31 99
108 94 5 72 99 81 122 98 97 12 114 15 85 6 8 12 28 26 51 94

[出力例]
3069

[入力例]
100 2022
175 889 1050 899 493 1109 480 410 194 274 940 594 993 685 929 499 1087 889 422 65 626 367 95 395 481 291 63 90 243 948 661 59 840 822 1011 583 994 532 791 120 653 1045 86 917 428 774 313 307 850 683 249 725 800 1000 194 138 943 728 1160 861 466 575 696 908 694 256 508 987 346 380 1200 328 772 567 1234 169 227 958 1178 1132 263 483 701 1199 770 840 279 399 219 512 359 999 846 1026 405 677 475 39 680 654
789 461 494 1030 915 230 308 639 80 365 259 619 888 901 152 1001 207 341 126 989 341 875 725 928 1185 913 495 54 918 1013 1007 328 129 222 672 854 865 888 960 111 114 999 293 898 153 696 133 543 571 680 443 1010 424 378 42 642 205 1159 516 992 331 1140 148 555 711 890 559 1097 840 1049 337 758 23 147 1008 227 280 1020 1176 956 307 688 403 1152 586 549 123 533 923 953 549 363 162 262 545 161 616 104 99 1010

[出力例]
310986

[入力例]
500 20220329
37625 31913 24870 10246 5597 6117 2413 80708 3713 71835 28673 17358 70496 78135 39198 56159 69643 62141 52081 85925 36168 53456 36791 19552 86319 94235 60978 73 48970 15774 96787 6203 39312 78991 39831 64409 69937 46172 88825 3364 17642 71353 92292 34332 72775 13590 57063 57262 65805 89570 42907 59477 50649 17386 15645 32122 20687 49918 36103 27749 68603 34616 5443 26360 80069 2565 46764 23616 77240 39090 39809 89091 36799 44416 40965 50181 83491 68503 63342 98144 3670 68623 32330 80673 932 25711 29150 25281 76132 99137 48546 25860 79432 96231 14213 6081 93038 46016 81327 2938 29152 3902 31157 2607 84550 81679 84559 44970 13987 27917 71876 28680 65172 92341 88527 83301 85380 25275 78139 7502 72015 53003 1522 28029 23607 41223 37666 19130 81285 36240 79704 94665 1288 41846 57565 64973 57022 35427 98862 89808 95744 8666 16810 27396 47933 71967 55470 42647 11546 56832 21494 62981 40456 34307 25131 91134 4961 91643 6728 78540 57311 73967 57535 49657 90885 77926 10778 71026 63575 10423 62872 17391 66113 93041 8546 98816 19757 47473 53228 67363 97553 43075 99385 81826 14701 97364 47361 43153 57201 7603 18133 5592 91956 25641 53938 18268 97690 98476 68837 5069 90913 58932 89428 60549 47294 1813 5439 8892 76360 44760 83349 22912 97203 89608 47449 33005 80860 6983 45462 37148 9697 85726 15241 3723 16232 13784 27340 52806 16193 86807 24704 59077 74832 37116 89428 92208 34378 21222 99483 53062 40897 81277 52983 70337 91622 77244 50129 78629 44828 59495 77416 54753 44417 43794 32880 5296 84727 11329 96828 36889 44764 89931 44450 32227 30184 63574 11978 39433 48341 82635 82003 79151 64875 38606 33350 74360 70450 10756 75963 49812 95020 96078 53031 28733 68596 86780 69917 45924 46967 29941 63478 47367 8198 75674 16062 27087 97145 7979 12181 1199 2368 95072 71203 54853 90622 1225 6060 73262 45713 69069 61253 65807 85266 99235 71278 74210 17839 37675 1054 15912 9527 20160 26684 74853 55543 97486 40330 56129 1661 48290 64480 92164 62873 68305 59187 3533 40781 35715 96842 56522 58245 49556 51024 96827 59958 47007 24472 91676 27841 22111 91365 34518 47384 8703 50678 88377 15334 48858 70168 21867 1831 28545 50540 75700 27378 46666 78682 8544 62946 64800 18977 28833 54515 3039 90347 14531 69205 52984 97325 20125 855 45019 42113 13506 32618 94325 83190 55278 84089 53509 86263 45247 96040 59799 94469 34717 90715 9403 83269 52358 62100 56992 25039 95692 74868 76712 19291 5221 13466 75001 67951 67917 64799 57736 98881 35159 94817 82349 73975 79043 632 57473 61687 8389 97251 99172 52119 62109 68718 1901 18325 68982 2134 12502 82296 36472 40997 33246 8050 46683 56391 65582 28395 78459 19568 15544 89253 27707 49788 46919 16236 55180 23156 18882 39544 24950 19806 8264 32044 2708 26739 51332 64592 68103 67851 11442 95862 64458 22022 91140 76445 54395 85252 61088 16910 88482 31605 36198 99017 81459 48080 34080 5124 59895 65204 74955 78709 55327 61890 99823 40246 53738 68584 85371 54849 61594 94088 19050 77087 34534
59010 20255 19482 78511 49049 19936 32557 99291 42203 49456 7865 14983 95989 69314 92747 62908 39231 831 9134 52535 24327 56398 76884 11563 79480 76035 3325 95646 20031 88304 60065 35328 5186 54238 59800 27732 14202 38682 9202 71431 2764 26160 94849 87853 23811 95518 16904 62774 64945 2025 89313 57743 77347 91056 5996 2024 19734 42747 76709 47954 85744 56704 91887 68624 29158 33388 8860 41326 30626 76320 38867 9994 70607 50896 21755 500 94586 76879 81137 19332 55507 76703 11837 65683 47652 61606 91630 32740 90 99074 13192 65843 21722 200 16681 58916 55279 97204 34487 73077 36963 48514 61354 70302 65235 50529 29272 70814 70461 62013 3186 31372 12227 84717 9372 977 94845 70512 17294 32834 30276 9608 82065 61097 36205 9849 83062 96798 14768 76693 98122 79180 31567 52884 15147 26515 80647 5907 64893 57939 7903 36880 55701 96824 17177 71544 99253 74819 65043 70471 6927 8608 64809 63519 100 52844 41069 700 57715 50281 80309 27200 57909 34611 12033 24774 82655 19208 81760 9031 33309 9312 3891 46442 16763 18791 41960 79402 33696 58886 56310 51721 67753 85790 32669 45890 13827 95470 70733 12954 78186 31574 27672 71917 96700 31900 79909 60854 12771 31590 94253 55392 20561 81713 86940 42014 73738 1200 58010 99733 91269 95867 29304 56580 57363 70097 33537 85968 18815 59636 63948 3389 2023 78141 7730 28647 65207 75793 75673 82387 78425 28024 22111 28743 95736 70783 34106 75291 65608 8540 51040 53513 53756 70135 38390 95521 45411 54559 4746 33090 95127 70952 2030 92034 64630 71398 62597 45700 33596 80810 23332 31194 91503 31282 89479 40570 6257 9272 47361 89079 8499 56972 91107 29355 75475 75001 17464 88173 51058 63999 41954 78259 88735 66791 25175 67869 87589 25370 16043 56293 93780 33195 31967 28658 34104 55377 1242 49709 53895 53925 97252 76023 2022 89453 66027 51111 65009 13114 68736 94184 52438 52723 8658 66955 34543 63144 53776 17584 29772 93815 61386 87999 77814 4144 63764 48671 28736 73960 54032 93427 50583 68395 65837 12709 900 46313 61277 52199 79704 19775 36702 77234 94539 53429 31067 80305 81045 81960 7533 89431 80 60009 91501 97534 85846 61857 26774 16809 17537 86751 29263 18329 35447 41421 56599 73589 19494 44277 71024 48802 66267 42048 17411 18360 12618 74638 12564 99663 50218 99060 96977 5808 35397 49093 78722 61516 31780 25168 29985 88898 55278 13287 13782 16583 33090 9425 48366 83891 66555 61870 27868 24779 3231 52664 43790 91014 58932 85335 97369 51929 36241 1500 56423 2050 42954 87402 1715 44440 68934 64793 99578 8777 25587 35031 57345 79418 77995 36254 73783 75360 12277 53072 26170 95122 98721 28810 45268 38976 50802 36781 32398 72050 70947 53134 85646 71050 72953 54233 4654 55954 974 29568 65128 17962 32795 4774 86883 21870 91824 10341 87696 3966 6594 88562 7600 36696 42613 65637 46916 93207 39481 14920 30012 56793 29281 38675 7487 58426 97489 11030 49291 15421 2652 71495 61962 1800 26330 3099 48280 62655 59020 82685 51028 16192 90417 82279 28684 77097 51096 63584

[出力例]
167129136

[入力例]

3 5

4 2 1

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

3 8

4 2 1

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

11 14

3 1 4 1 5 9 2 6 5 3 5

8 9 7 9 3 2 3 8 4 6 2

[出力例]

※AtCoderテストケースより

[入力例]

5 12

3 6 5 4 7

5 3 7 2 1

[出力例]

[入力例]

20 32

81 18 82 83 42 20 32 50 37 37 37 117 119 63 99 104 34 29 31 99

108 94 5 72 99 81 122 98 97 12 114 15 85 6 8 12 28 26 51 94

[出力例]

3069

[入力例]

100 2022

175 889 1050 899 493 1109 480 410 194 274 940 594 993 685 929 499 1087 889 422 65 626 367 95 395 481 291 63 90 243 948 661 59 840 822 1011 583 994 532 791 120 653 1045 86 917 428 774 313 307 850 683 249 725 800 1000 194 138 943 728 1160 861 466 575 696 908 694 256 508 987 346 380 1200 328 772 567 1234 169 227 958 1178 1132 263 483 701 1199 770 840 279 399 219 512 359 999 846 1026 405 677 475 39 680 654

789 461 494 1030 915 230 308 639 80 365 259 619 888 901 152 1001 207 341 126 989 341 875 725 928 1185 913 495 54 918 1013 1007 328 129 222 672 854 865 888 960 111 114 999 293 898 153 696 133 543 571 680 443 1010 424 378 42 642 205 1159 516 992 331 1140 148 555 711 890 559 1097 840 1049 337 758 23 147 1008 227 280 1020 1176 956 307 688 403 1152 586 549 123 533 923 953 549 363 162 262 545 161 616 104 99 1010

[出力例]

310986

[入力例]

500 20220329

37625 31913 24870 10246 5597 6117 2413 80708 3713 71835 28673 17358 70496 78135 39198 56159 69643 62141 52081 85925 36168 53456 36791 19552 86319 94235 60978 73 48970 15774 96787 6203 39312 78991 39831 64409 69937 46172 88825 3364 17642 71353 92292 34332 72775 13590 57063 57262 65805 89570 42907 59477 50649 17386 15645 32122 20687 49918 36103 27749 68603 34616 5443 26360 80069 2565 46764 23616 77240 39090 39809 89091 36799 44416 40965 50181 83491 68503 63342 98144 3670 68623 32330 80673 932 25711 29150 25281 76132 99137 48546 25860 79432 96231 14213 6081 93038 46016 81327 2938 29152 3902 31157 2607 84550 81679 84559 44970 13987 27917 71876 28680 65172 92341 88527 83301 85380 25275 78139 7502 72015 53003 1522 28029 23607 41223 37666 19130 81285 36240 79704 94665 1288 41846 57565 64973 57022 35427 98862 89808 95744 8666 16810 27396 47933 71967 55470 42647 11546 56832 21494 62981 40456 34307 25131 91134 4961 91643 6728 78540 57311 73967 57535 49657 90885 77926 10778 71026 63575 10423 62872 17391 66113 93041 8546 98816 19757 47473 53228 67363 97553 43075 99385 81826 14701 97364 47361 43153 57201 7603 18133 5592 91956 25641 53938 18268 97690 98476 68837 5069 90913 58932 89428 60549 47294 1813 5439 8892 76360 44760 83349 22912 97203 89608 47449 33005 80860 6983 45462 37148 9697 85726 15241 3723 16232 13784 27340 52806 16193 86807 24704 59077 74832 37116 89428 92208 34378 21222 99483 53062 40897 81277 52983 70337 91622 77244 50129 78629 44828 59495 77416 54753 44417 43794 32880 5296 84727 11329 96828 36889 44764 89931 44450 32227 30184 63574 11978 39433 48341 82635 82003 79151 64875 38606 33350 74360 70450 10756 75963 49812 95020 96078 53031 28733 68596 86780 69917 45924 46967 29941 63478 47367 8198 75674 16062 27087 97145 7979 12181 1199 2368 95072 71203 54853 90622 1225 6060 73262 45713 69069 61253 65807 85266 99235 71278 74210 17839 37675 1054 15912 9527 20160 26684 74853 55543 97486 40330 56129 1661 48290 64480 92164 62873 68305 59187 3533 40781 35715 96842 56522 58245 49556 51024 96827 59958 47007 24472 91676 27841 22111 91365 34518 47384 8703 50678 88377 15334 48858 70168 21867 1831 28545 50540 75700 27378 46666 78682 8544 62946 64800 18977 28833 54515 3039 90347 14531 69205 52984 97325 20125 855 45019 42113 13506 32618 94325 83190 55278 84089 53509 86263 45247 96040 59799 94469 34717 90715 9403 83269 52358 62100 56992 25039 95692 74868 76712 19291 5221 13466 75001 67951 67917 64799 57736 98881 35159 94817 82349 73975 79043 632 57473 61687 8389 97251 99172 52119 62109 68718 1901 18325 68982 2134 12502 82296 36472 40997 33246 8050 46683 56391 65582 28395 78459 19568 15544 89253 27707 49788 46919 16236 55180 23156 18882 39544 24950 19806 8264 32044 2708 26739 51332 64592 68103 67851 11442 95862 64458 22022 91140 76445 54395 85252 61088 16910 88482 31605 36198 99017 81459 48080 34080 5124 59895 65204 74955 78709 55327 61890 99823 40246 53738 68584 85371 54849 61594 94088 19050 77087 34534

59010 20255 19482 78511 49049 19936 32557 99291 42203 49456 7865 14983 95989 69314 92747 62908 39231 831 9134 52535 24327 56398 76884 11563 79480 76035 3325 95646 20031 88304 60065 35328 5186 54238 59800 27732 14202 38682 9202 71431 2764 26160 94849 87853 23811 95518 16904 62774 64945 2025 89313 57743 77347 91056 5996 2024 19734 42747 76709 47954 85744 56704 91887 68624 29158 33388 8860 41326 30626 76320 38867 9994 70607 50896 21755 500 94586 76879 81137 19332 55507 76703 11837 65683 47652 61606 91630 32740 90 99074 13192 65843 21722 200 16681 58916 55279 97204 34487 73077 36963 48514 61354 70302 65235 50529 29272 70814 70461 62013 3186 31372 12227 84717 9372 977 94845 70512 17294 32834 30276 9608 82065 61097 36205 9849 83062 96798 14768 76693 98122 79180 31567 52884 15147 26515 80647 5907 64893 57939 7903 36880 55701 96824 17177 71544 99253 74819 65043 70471 6927 8608 64809 63519 100 52844 41069 700 57715 50281 80309 27200 57909 34611 12033 24774 82655 19208 81760 9031 33309 9312 3891 46442 16763 18791 41960 79402 33696 58886 56310 51721 67753 85790 32669 45890 13827 95470 70733 12954 78186 31574 27672 71917 96700 31900 79909 60854 12771 31590 94253 55392 20561 81713 86940 42014 73738 1200 58010 99733 91269 95867 29304 56580 57363 70097 33537 85968 18815 59636 63948 3389 2023 78141 7730 28647 65207 75793 75673 82387 78425 28024 22111 28743 95736 70783 34106 75291 65608 8540 51040 53513 53756 70135 38390 95521 45411 54559 4746 33090 95127 70952 2030 92034 64630 71398 62597 45700 33596 80810 23332 31194 91503 31282 89479 40570 6257 9272 47361 89079 8499 56972 91107 29355 75475 75001 17464 88173 51058 63999 41954 78259 88735 66791 25175 67869 87589 25370 16043 56293 93780 33195 31967 28658 34104 55377 1242 49709 53895 53925 97252 76023 2022 89453 66027 51111 65009 13114 68736 94184 52438 52723 8658 66955 34543 63144 53776 17584 29772 93815 61386 87999 77814 4144 63764 48671 28736 73960 54032 93427 50583 68395 65837 12709 900 46313 61277 52199 79704 19775 36702 77234 94539 53429 31067 80305 81045 81960 7533 89431 80 60009 91501 97534 85846 61857 26774 16809 17537 86751 29263 18329 35447 41421 56599 73589 19494 44277 71024 48802 66267 42048 17411 18360 12618 74638 12564 99663 50218 99060 96977 5808 35397 49093 78722 61516 31780 25168 29985 88898 55278 13287 13782 16583 33090 9425 48366 83891 66555 61870 27868 24779 3231 52664 43790 91014 58932 85335 97369 51929 36241 1500 56423 2050 42954 87402 1715 44440 68934 64793 99578 8777 25587 35031 57345 79418 77995 36254 73783 75360 12277 53072 26170 95122 98721 28810 45268 38976 50802 36781 32398 72050 70947 53134 85646 71050 72953 54233 4654 55954 974 29568 65128 17962 32795 4774 86883 21870 91824 10341 87696 3966 6594 88562 7600 36696 42613 65637 46916 93207 39481 14920 30012 56793 29281 38675 7487 58426 97489 11030 49291 15421 2652 71495 61962 1800 26330 3099 48280 62655 59020 82685 51028 16192 90417 82279 28684 77097 51096 63584

[出力例]

167129136

■参照サイト
AtCoder Beginner Contest 144

C++の練習を兼ねて, AtCoder Beginner Contest 144 の 問題E (Gluttony) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 144 の問題E (Gluttony) を解いてみた.

コメントを残すコメントをキャンセル