個人用メモ帳

2022年3月29日

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

2022年3月28日2022年3月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 140 の問題F (Many Slimes) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 親頂点としてあり得る上限の個数に着目して, 同じ整数が複数登場した場合も, 対応出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc140/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using PQ = priority_queue<int, vector<int>, greater<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 a first
#define b second
int memo[1 << 20];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, 1 << N){
        int s;
        scanf("%d", &s);
        m[s]++;
    }
    
    // 2. スライム配置.
    bool ok = true;
    int mIdx = (1 << (N + 1));
    PQ pq; // 親頂点(候補).
    pq.push(1);
    map<int, int>::reverse_iterator itr;
    // S の 大きい要素から割り当てる.
    for(itr = m.rbegin(); itr != m.rend(); ++itr){
        // フラグ, 終了確認.
        if(!ok) break;
        
        // 親のサイズ, 整数の出現数.
        int ps = pq.size();
        int ns = itr->b;
        
        // 割り当て不可.
        if(ps < ns){
            ok = false;
            break;
        }
        
        // 整数の割り当て.
        // -> 同じ整数を, 一括で割り当てる.
        queue<int> q;
        int sCur = itr->a;
        while(!pq.empty() && ns){
            int c = pq.top();
            pq.pop();
            while(c < mIdx){
                memo[c] = sCur;
                if((c << 1) + 1 < mIdx) q.push((c << 1) + 1);
                c <<= 1;
            }
            --ns;
        }
        
        // 親頂点(次回以降).
        while(!q.empty()){
            int t = q.front();
            q.pop();
            pq.push(t);
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using PQ = priority_queue<int, vector<int>, greater<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 a first

#define b second

int memo[1 << 20];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, 1 << N){

int s;

scanf("%d", &s);

m[s]++;

}

// 2. スライム配置.

bool ok = true;

int mIdx = (1 << (N + 1));

PQ pq; // 親頂点(候補).

pq.push(1);

map<int, int>::reverse_iterator itr;

// S の大きい要素から割り当てる.

for(itr = m.rbegin(); itr != m.rend(); ++itr){

// フラグ, 終了確認.

if(!ok) break;

// 親のサイズ, 整数の出現数.

int ps = pq.size();

int ns = itr->b;

// 割り当て不可.

if(ps < ns){

ok = false;

break;

}

// 整数の割り当て.

// -> 同じ整数を, 一括で割り当てる.

queue<int> q;

int sCur = itr->a;

while(!pq.empty() && ns){

int c = pq.top();

pq.pop();

while(c < mIdx){

memo[c] = sCur;

if((c << 1) + 1 < mIdx) q.push((c << 1) + 1);

c <<= 1;

}

--ns;

}

// 親頂点(次回以降).

while(!q.empty()){

int t = q.front();

q.pop();

pq.push(t);

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

[入力例]
2
4 2 3 1

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

[入力例]
2
1 2 3 1

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

[入力例]
1
1 1

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

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

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

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

[出力例]
Yes

[入力例]
3
5 5 5 5 6 5 6 7

[出力例]
No

[入力例]
5
52 52 13 47 1 29 2 55 21 30 43 1 53 2 31 2 7 50 1 18 37 23 15 3 28 5 52 9 49 29 30 37

[出力例]
Yes

[入力例]
7
35 7 8 33 19 12 25 1 5 13 26 2 33 52 36 15 52 32 6 52 5 23 2 55 9 33 33 8 33 5 17 33 35 53 50 33 17 7 33 8 37 25 11 50 30 33 19 33 37 51 8 7 20 34 32 32 33 33 33 23 20 33 9 33 23 19 30 51 18 12 3 22 33 50 31 33 19 33 31 23 22 53 12 33 13 15 54 13 11 15 15 33 52 2 33 33 53 30 27 33 24 33 20 54 31 17 17 21 52 28 33 37 15 33 35 18 33 17 33 32 15 26 32 14 5 50 33 27

[出力例]
Yes

[入力例]
10
82 64 51 66 1 88 89 12 69 87 81 6 55 65 119 77 76 32 19 48 112 46 52 91 50 76 39 30 29 48 89 105 78 89 120 92 28 56 50 57 95 62 17 65 113 99 5 14 53 46 43 113 94 15 19 60 123 110 23 49 27 100 5 22 3 44 78 15 20 65 92 89 80 28 29 101 93 43 41 70 28 100 22 90 27 22 103 9 92 79 43 21 46 52 80 105 35 115 69 62 98 44 40 72 23 60 87 115 46 114 60 21 34 58 28 4 56 107 43 21 63 20 115 97 56 23 114 114 114 62 11 23 36 24 23 79 64 25 17 18 16 19 93 28 92 113 24 23 29 47 19 35 88 59 59 84 22 86 119 110 102 58 11 85 109 2 34 58 48 110 93 101 86 39 94 8 12 76 13 108 15 32 80 9 12 83 90 48 117 93 121 92 20 108 48 80 92 65 116 96 87 31 94 52 99 1 117 112 22 49 17 75 30 35 100 107 33 44 81 46 116 19 33 35 80 93 44 85 81 19 21 15 31 28 55 73 20 41 108 88 19 86 97 72 48 41 109 16 32 17 57 56 83 102 113 74 93 19 74 76 13 80 33 39 20 113 13 23 6 7 99 10 78 104 43 108 80 70 108 71 77 86 7 26 2 74 56 110 47 73 31 110 74 115 32 70 45 24 40 28 122 19 92 34 24 13 24 2 87 57 51 51 48 37 87 74 106 115 63 76 97 31 49 114 19 104 51 112 106 24 69 111 71 63 22 66 94 55 118 69 111 46 115 54 25 30 73 35 44 117 105 62 58 103 22 16 81 99 101 66 52 26 63 105 58 29 79 103 51 2 80 30 49 61 98 70 30 75 119 78 62 100 49 51 117 109 1 78 48 10 46 80 105 115 4 29 18 60 39 45 108 103 57 40 82 96 87 9 89 83 73 82 117 36 84 25 85 10 27 11 74 92 10 21 69 57 36 83 97 23 110 115 69 90 46 66 102 119 101 118 16 43 39 23 118 24 13 80 5 81 106 58 43 33 40 117 108 121 52 30 41 90 114 6 99 82 52 83 78 80 55 13 35 39 17 97 80 94 76 119 101 18 18 49 66 88 116 29 52 37 118 75 30 82 2 119 80 26 92 92 113 30 64 100 81 50 92 7 57 10 96 14 23 70 79 43 30 107 115 32 114 24 112 55 34 118 109 95 38 83 115 103 18 68 7 70 30 84 55 11 78 14 7 92 51 73 19 39 81 57 93 84 57 34 28 29 91 47 107 52 113 11 83 47 17 107 21 12 114 56 27 109 76 9 91 54 7 24 7 1 56 54 15 25 75 66 72 52 74 32 43 84 49 66 78 38 38 72 84 117 91 69 90 11 47 27 21 117 20 52 101 77 64 60 88 83 80 94 92 47 27 27 11 101 94 27 41 63 74 21 4 67 115 25 8 18 118 80 104 10 118 20 93 23 24 118 47 86 109 89 46 72 4 74 74 2 109 93 13 110 82 74 98 72 109 108 97 59 44 105 85 7 17 33 56 5 36 111 5 31 14 95 77 60 108 121 29 118 74 13 77 24 3 64 80 74 87 120 30 46 101 61 44 25 36 43 21 56 103 90 92 38 68 38 41 34 76 69 105 7 101 23 64 40 101 9 92 13 3 100 51 2 32 75 26 22 117 13 76 24 69 113 78 48 55 79 78 9 32 61 77 79 83 8 56 38 32 119 76 36 104 119 49 116 54 27 70 90 43 5 89 116 24 41 117 120 69 61 2 69 103 106 32 18 81 28 51 3 20 49 88 75 46 60 26 105 20 18 99 97 56 114 53 93 21 6 40 32 51 71 77 33 86 75 9 19 13 91 30 74 120 116 72 58 81 58 37 58 83 72 47 17 38 118 14 74 47 15 36 91 85 13 110 11 100 66 35 102 45 4 86 9 26 101 86 49 89 55 79 99 51 115 82 17 3 113 62 105 23 43 14 33 84 69 78 3 70 53 36 76 97 17 58 91 84 62 7 55 73 8 40 112 90 59 25 97 116 55 84 52 28 91 114 65 30 41 88 48 23 102 61 100 77 21 43 72 92 22 8 17 74 107 99 68 21 32 64 121 62 78 80 1 50 13 48 51 48 60 90 37 85 67 51 107 85 108 84 102 65 98 25 83 110 114 28 91 1 113 105 118 19 111 50 84 43 108 116 59 48 108 68 17 79 73 112 78 108 2 14 17 69 32 105 47 50 17 30 6 83 68 23 19 10 17 1 39 52 25 91 118 29 58 46 72 78 91 52 118 97 58 29 89 63 11 52 101 1 47 120 2 6 20 30 122

[出力例]
Yes

[入力例]

4 2 3 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2 3 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 5 6 5 6 7

[出力例]

Yes

[入力例]

5 5 5 5 6 5 6 7

[出力例]

[入力例]

52 52 13 47 1 29 2 55 21 30 43 1 53 2 31 2 7 50 1 18 37 23 15 3 28 5 52 9 49 29 30 37

[出力例]

Yes

[入力例]

35 7 8 33 19 12 25 1 5 13 26 2 33 52 36 15 52 32 6 52 5 23 2 55 9 33 33 8 33 5 17 33 35 53 50 33 17 7 33 8 37 25 11 50 30 33 19 33 37 51 8 7 20 34 32 32 33 33 33 23 20 33 9 33 23 19 30 51 18 12 3 22 33 50 31 33 19 33 31 23 22 53 12 33 13 15 54 13 11 15 15 33 52 2 33 33 53 30 27 33 24 33 20 54 31 17 17 21 52 28 33 37 15 33 35 18 33 17 33 32 15 26 32 14 5 50 33 27

[出力例]

Yes

[入力例]

82 64 51 66 1 88 89 12 69 87 81 6 55 65 119 77 76 32 19 48 112 46 52 91 50 76 39 30 29 48 89 105 78 89 120 92 28 56 50 57 95 62 17 65 113 99 5 14 53 46 43 113 94 15 19 60 123 110 23 49 27 100 5 22 3 44 78 15 20 65 92 89 80 28 29 101 93 43 41 70 28 100 22 90 27 22 103 9 92 79 43 21 46 52 80 105 35 115 69 62 98 44 40 72 23 60 87 115 46 114 60 21 34 58 28 4 56 107 43 21 63 20 115 97 56 23 114 114 114 62 11 23 36 24 23 79 64 25 17 18 16 19 93 28 92 113 24 23 29 47 19 35 88 59 59 84 22 86 119 110 102 58 11 85 109 2 34 58 48 110 93 101 86 39 94 8 12 76 13 108 15 32 80 9 12 83 90 48 117 93 121 92 20 108 48 80 92 65 116 96 87 31 94 52 99 1 117 112 22 49 17 75 30 35 100 107 33 44 81 46 116 19 33 35 80 93 44 85 81 19 21 15 31 28 55 73 20 41 108 88 19 86 97 72 48 41 109 16 32 17 57 56 83 102 113 74 93 19 74 76 13 80 33 39 20 113 13 23 6 7 99 10 78 104 43 108 80 70 108 71 77 86 7 26 2 74 56 110 47 73 31 110 74 115 32 70 45 24 40 28 122 19 92 34 24 13 24 2 87 57 51 51 48 37 87 74 106 115 63 76 97 31 49 114 19 104 51 112 106 24 69 111 71 63 22 66 94 55 118 69 111 46 115 54 25 30 73 35 44 117 105 62 58 103 22 16 81 99 101 66 52 26 63 105 58 29 79 103 51 2 80 30 49 61 98 70 30 75 119 78 62 100 49 51 117 109 1 78 48 10 46 80 105 115 4 29 18 60 39 45 108 103 57 40 82 96 87 9 89 83 73 82 117 36 84 25 85 10 27 11 74 92 10 21 69 57 36 83 97 23 110 115 69 90 46 66 102 119 101 118 16 43 39 23 118 24 13 80 5 81 106 58 43 33 40 117 108 121 52 30 41 90 114 6 99 82 52 83 78 80 55 13 35 39 17 97 80 94 76 119 101 18 18 49 66 88 116 29 52 37 118 75 30 82 2 119 80 26 92 92 113 30 64 100 81 50 92 7 57 10 96 14 23 70 79 43 30 107 115 32 114 24 112 55 34 118 109 95 38 83 115 103 18 68 7 70 30 84 55 11 78 14 7 92 51 73 19 39 81 57 93 84 57 34 28 29 91 47 107 52 113 11 83 47 17 107 21 12 114 56 27 109 76 9 91 54 7 24 7 1 56 54 15 25 75 66 72 52 74 32 43 84 49 66 78 38 38 72 84 117 91 69 90 11 47 27 21 117 20 52 101 77 64 60 88 83 80 94 92 47 27 27 11 101 94 27 41 63 74 21 4 67 115 25 8 18 118 80 104 10 118 20 93 23 24 118 47 86 109 89 46 72 4 74 74 2 109 93 13 110 82 74 98 72 109 108 97 59 44 105 85 7 17 33 56 5 36 111 5 31 14 95 77 60 108 121 29 118 74 13 77 24 3 64 80 74 87 120 30 46 101 61 44 25 36 43 21 56 103 90 92 38 68 38 41 34 76 69 105 7 101 23 64 40 101 9 92 13 3 100 51 2 32 75 26 22 117 13 76 24 69 113 78 48 55 79 78 9 32 61 77 79 83 8 56 38 32 119 76 36 104 119 49 116 54 27 70 90 43 5 89 116 24 41 117 120 69 61 2 69 103 106 32 18 81 28 51 3 20 49 88 75 46 60 26 105 20 18 99 97 56 114 53 93 21 6 40 32 51 71 77 33 86 75 9 19 13 91 30 74 120 116 72 58 81 58 37 58 83 72 47 17 38 118 14 74 47 15 36 91 85 13 110 11 100 66 35 102 45 4 86 9 26 101 86 49 89 55 79 99 51 115 82 17 3 113 62 105 23 43 14 33 84 69 78 3 70 53 36 76 97 17 58 91 84 62 7 55 73 8 40 112 90 59 25 97 116 55 84 52 28 91 114 65 30 41 88 48 23 102 61 100 77 21 43 72 92 22 8 17 74 107 99 68 21 32 64 121 62 78 80 1 50 13 48 51 48 60 90 37 85 67 51 107 85 108 84 102 65 98 25 83 110 114 28 91 1 113 105 118 19 111 50 84 43 108 116 59 48 108 68 17 79 73 112 78 108 2 14 17 69 32 105 47 50 17 30 6 83 68 23 19 10 17 1 39 52 25 91 118 29 58 46 72 78 91 52 118 97 58 29 89 63 11 52 101 1 47 120 2 6 20 30 122

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 140

2022年3月25日2022年3月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題A (Coprime Pair) ～問題B (Count 1’s) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 137 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/arc137/editorial/3592
// 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 main(){
    
    // 1. 入力情報.
    LL L, R;
    scanf("%lld %lld", &L, &R);
    
    // 2. y - x の 最大値は？
    // 01-007.txt などで, WA版だったので, 修正.
    LL ans = 0, x = L, y = R;
    rep(i, 1501){
        rep(j, 1501){
            if(y - j <= 0 || (y - j <= x + i)) continue;
            if(__gcd(x + i, y - j) == 1)       ans = max(ans, y - j - x - i);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3592

// 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 main(){

// 1. 入力情報.

LL L, R;

scanf("%lld %lld", &L, &R);

// 2. y - x の最大値は？

// 01-007.txt などで, WA版だったので, 修正.

LL ans = 0, x = L, y = R;

rep(i, 1501){

rep(j, 1501){

if(y - j <= 0 || (y - j <= x + i)) continue;

if(__gcd(x + i, y - j) == 1) ans = max(ans, y - j - x - i);

}

// 3. 出力.

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

return 0;

}

[入力例]
2 4

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

[入力例]
14 21

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

[入力例]
1 100

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

[入力例]
123 456

[出力例]
332

[入力例]
12345 67890

[出力例]
55544

[入力例]

2 4

[出力例]

※AtCoderのテストケースより

[入力例]

14 21

[出力例]

※AtCoderのテストケースより

[入力例]

1 100

[出力例]

※AtCoderのテストケースより

[入力例]

123 456

[出力例]

332

[入力例]

12345 67890

[出力例]

55544

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

// 解き直し.
// https://atcoder.jp/contests/arc137/editorial/3591
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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[303030], b[303030], c[303030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 0, 1 の 出現数確認.
    // -> 01-001.txt などで, WA版となったのでロジック修正.
    int cnt10 = 0; // (1 の 個数) - (0 の 個数) の 最大値.
    int cnt01 = 0; // (0 の 個数) - (1 の 個数) の 最大値.
    rep(i, N){
        // 1 の 場合.
        if(a[i]){
            b[i + 1] = max(b[i] + 1, 1);
            c[i + 1] = max(c[i] - 1, -1);
        }
        
        // 0 の 場合.
        if(!a[i]){
            b[i + 1] = max(b[i] - 1, -1);
            c[i + 1] = max(c[i] + 1, 1);
        }
        
        // 最大値更新.
        cnt10 = max(cnt10, b[i + 1]);
        cnt01 = max(cnt01, c[i + 1]);
    }
    
    // 3. 出力.
    printf("%d\n", cnt10 + cnt01 + 1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3591

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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[303030], b[303030], c[303030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

// 2. 0, 1 の出現数確認.

// -> 01-001.txt などで, WA版となったのでロジック修正.

int cnt10 = 0; // (1 の個数) - (0 の個数) の最大値.

int cnt01 = 0; // (0 の個数) - (1 の個数) の最大値.

rep(i, N){

// 1 の場合.

if(a[i]){

b[i + 1] = max(b[i] + 1, 1);

c[i + 1] = max(c[i] - 1, -1);

}

// 0 の場合.

if(!a[i]){

b[i + 1] = max(b[i] - 1, -1);

c[i + 1] = max(c[i] + 1, 1);

}

// 最大値更新.

cnt10 = max(cnt10, b[i + 1]);

cnt01 = max(cnt01, c[i + 1]);

}

// 3. 出力.

printf("%d\n", cnt10 + cnt01 + 1);

return 0;

}

[入力例]
4
0 1 1 0

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

[入力例]
5
0 0 0 0 0

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

[入力例]
6
0 1 0 1 0 1

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

[入力例]
1
1

[出力例]
2

[入力例]
11
0 0 1 0 1 0 1 0 1 1 0

[出力例]
5

[入力例]
100
0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0

[出力例]
18

[入力例]

0 1 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 0 1 0 1

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

0 0 1 0 1 0 1 0 1 1 0

[出力例]

[入力例]

100

0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0

[出力例]

■参照サイト
AtCoder Regular Contest 137

2022年3月24日2022年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題C (最高のトッピングにしような) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. なお, 初回提出版では, MLE(メモリ制限超過)となったので, MLE回避するように修正して, 再提出している.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc027
// 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--)
LL dp[303][606], pd[303][606]; // dp[303][303][606] だと, MLE となるので, 修正.
int t[303], h[303];

int main(){
    
    // 1. 入力情報.
    int X, Y, N;
    scanf("%d %d %d", &X, &Y, &N);
    rep(i, N) scanf("%d %d", &t[i], &h[i]);
    
    // 2. dp更新.
    rep(i, N){
        // 初期化.
        rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = -1;
        pd[0][0] = 0;
        
        // 前回分反映.
        rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = max(pd[j][k], dp[j][k]);
        
        // 今回分反映.
        rep(j, min(i + 1, X)){
            rep(k, X + Y + 1){
                int nk = k - t[i];
                if(nk >= 0 && pd[j][nk] != -1){
                    dp[j + 1][k] = max(dp[j + 1][k], pd[j + 1][k]);
                    dp[j + 1][k] = max(dp[j + 1][k], pd[j][nk] + h[i]);
                }
            }
        }
    }
    
    // 3. 最大値.
    LL ans = 0;
    rep(j, X + 1) rep(k, X + Y + 1) ans = max(ans, dp[j][k]);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc027

// 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--)

LL dp[303][606], pd[303][606]; // dp[303][303][606] だと, MLE となるので, 修正.

int t[303], h[303];

int main(){

// 1. 入力情報.

int X, Y, N;

scanf("%d %d %d", &X, &Y, &N);

rep(i, N) scanf("%d %d", &t[i], &h[i]);

// 2. dp更新.

rep(i, N){

// 初期化.

rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = -1;

pd[0][0] = 0;

// 前回分反映.

rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = max(pd[j][k], dp[j][k]);

// 今回分反映.

rep(j, min(i + 1, X)){

rep(k, X + Y + 1){

int nk = k - t[i];

if(nk >= 0 && pd[j][nk] != -1){

dp[j + 1][k] = max(dp[j + 1][k], pd[j + 1][k]);

dp[j + 1][k] = max(dp[j + 1][k], pd[j][nk] + h[i]);

}

// 3. 最大値.

LL ans = 0;

rep(j, X + 1) rep(k, X + Y + 1) ans = max(ans, dp[j][k]);

// 4. 出力.

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

return 0;

}

[入力例]
3 5
4
3 30
3 40
5 60
7 80

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

[入力例]
3 3
4
3 30
3 40
5 60
7 80

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

[入力例]
1 5
4
3 30
3 40
5 60
7 80

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

[入力例]
6 12
4
3 30
3 40
5 60
7 80

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

[入力例]
1 1
1
1 11

[出力例]
11

[入力例]
7 15
10
7 100
2 33
6 66
4 44
8 55
1 9
12 111
10 178
7 77
5 55

[出力例]
333

[入力例]
12 33
25
3 642
2 174
10 129
6 1234
12 471
18 1013
10 207
6 642
3 1034
11 516
3 1075
9 201
9 1056
7 198
6 121
2 515
19 234
20 1111
3 924
5 770
2 677
4 1060
6 298
3 839
12 1010

[出力例]
10000

[入力例]
32 123
50
5 2237
11 527
12 69740
2 22416
8 77783
5 105904
12 122429
15 36253
7 115045
7 22468
12 108751
20 105233
4 34947
13 69463
5 5796
12 69023
3 31396
19 64113
8 30591
2 112723
7 113855
5 74920
17 63139
10 123438
19 26368
18 114828
3 8975
12 92652
25 117114
13 82653
5 106809
11 94419
17 54726
19 85275
16 91535
10 115684
7 101791
8 91513
3 122995
6 5408
7 79431
8 48599
19 115048
20 106513
11 64312
5 6456
7 102500
3 27527
19 23909
15 2042

[出力例]
2000000

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

[入力例]

3 5

3 30

3 40

5 60

7 80

[出力例]

100

※AtCoderテストケースより

[入力例]

3 3

3 30

3 40

5 60

7 80

[出力例]

※AtCoderテストケースより

[入力例]

1 5

3 30

3 40

5 60

7 80

[出力例]

※AtCoderテストケースより

[入力例]

6 12

3 30

3 40

5 60

7 80

[出力例]

210

※AtCoderテストケースより

[入力例]

1 1

1 11

[出力例]

[入力例]

7 15

7 100

2 33

6 66

4 44

8 55

1 9

12 111

10 178

7 77

5 55

[出力例]

333

[入力例]

12 33

3 642

2 174

10 129

6 1234

12 471

18 1013

10 207

6 642

3 1034

11 516

3 1075

9 201

9 1056

7 198

6 121

2 515

19 234

20 1111

3 924

5 770

2 677

4 1060

6 298

3 839

12 1010

[出力例]

10000

[入力例]

32 123

5 2237

11 527

12 69740

2 22416

8 77783

5 105904

12 122429

15 36253

7 115045

7 22468

12 108751

20 105233

4 34947

13 69463

5 5796

12 69023

3 31396

19 64113

8 30591

2 112723

7 113855

5 74920

17 63139

10 123438

19 26368

18 114828

3 8975

12 92652

25 117114

13 82653

5 106809

11 94419

17 54726

19 85275

16 91535

10 115684

7 101791

8 91513

3 122995

6 5408

7 79431

8 48599

19 115048

20 106513

11 64312

5 6456

7 102500

3 27527

19 23909

15 2042

[出力例]

2000000

■参照サイト
AtCoder Regular Contest 027

2022年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, ダイクストラ法(応用版) と尺取り法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc025
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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()
const LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[3030];

int main(){
    
    // 1. 入力情報.
    int N, M, R, T;
    scanf("%d %d %d %d", &N, &M, &R, &T);
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        --a;
        --b;
        G[a].pb(edge{b, (LL)c});
        G[b].pb(edge{a, (LL)c});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* m){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(m[cn]) continue;
            m[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 最短経路のリスト作成.
    vvl v(N);
    rep(i, N){
        LL d[N];
        int memo[N];
        rep(j, N) d[j] = INF, memo[j] = 0;
        dijkstra(i, d, memo);
        rep(j, N) if(i != j) v[i].pb(d[j]);
        sort(all(v[i]));
    }
    /*
    for(auto &p : v){
        for(auto &q : p) printf("%d ", q);
        puts("\n-----");
    }
    */
    
    // 4. 組み合わせを集計.
    LL ans = 0;
    rep(i, N){
        // ウサギ, カメ の 最短経路長 を 評価.
        // -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に 注意.
        int r = 0;
        rep(l, N - 1){
            LL Y = v[i][l], X = v[i][r];
            while(X * T <= Y * R && r <= N - 2) X = v[i][++r];
            ans += (LL)(N - 1 - r);
        }
    }
    
    // 5. カメの速さ が ウサギの速さ よりも速かった場合.
    if(T > R) ans -= (LL)N * (LL)(N - 1);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://www.slideshare.net/chokudai/arc025

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

#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()

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[3030];

int main(){

// 1. 入力情報.

int N, M, R, T;

scanf("%d %d %d %d", &N, &M, &R, &T);

rep(i, M){

int a, b, c;

scanf("%d %d %d", &a, &b, &c);

--a;

--b;

G[a].pb(edge{b, (LL)c});

G[b].pb(edge{a, (LL)c});

}

// 2. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* m){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 2-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 2-4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 2-5. 訪問済みフラグ設定.

if(m[cn]) continue;

m[cn]++;

// 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

};

// 3. 最短経路のリスト作成.

vvl v(N);

rep(i, N){

LL d[N];

int memo[N];

rep(j, N) d[j] = INF, memo[j] = 0;

dijkstra(i, d, memo);

rep(j, N) if(i != j) v[i].pb(d[j]);

sort(all(v[i]));

}

for(auto &p : v){

for(auto &q : p) printf("%d ", q);

puts("\n-----");

}

// 4. 組み合わせを集計.

LL ans = 0;

rep(i, N){

// ウサギ, カメの最短経路長を評価.

// -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に注意.

int r = 0;

rep(l, N - 1){

LL Y = v[i][l], X = v[i][r];

while(X * T <= Y * R && r <= N - 2) X = v[i][++r];

ans += (LL)(N - 1 - r);

}

// 5. カメの速さがウサギの速さよりも速かった場合.

if(T > R) ans -= (LL)N * (LL)(N - 1);

// 6. 出力.

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

return 0;

}

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

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

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

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

[入力例]
3 3 1 2
1 2 5
2 3 8
1 3 7

[出力例]
6

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

[出力例]
12

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

[出力例]
50

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

[出力例]
50

[入力例]
12 18 7 6
1 2 10
1 8 5
2 7 8
2 3 7
2 11 3
11 12 11
3 4 2
4 12 5
4 6 3
3 5 10
5 6 1
5 10 2
6 10 3
7 10 2
7 9 3
9 10 5
8 9 1
7 8 2

[出力例]
565

[入力例]

4 5 2 1

1 2 4

1 3 3

1 4 6

2 3 5

3 4 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4 7 7

1 2 1

2 3 1

3 4 1

4 5 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1 2

1 2 5

2 3 8

1 3 7

[出力例]

[入力例]

4 6 2 3

1 2 2

1 3 5

1 4 3

2 3 3

2 4 5

3 4 2

[出力例]

[入力例]

5 7 2 5

1 2 6

1 3 5

2 3 2

3 5 3

2 5 1

2 4 7

4 5 4

[出力例]

[入力例]

6 8 5 4

1 2 8

2 3 2

1 3 5

3 4 3

2 4 10

4 5 5

2 6 7

[出力例]

[入力例]

12 18 7 6

1 2 10

1 8 5

2 7 8

2 3 7

2 11 3

11 12 11

3 4 2

4 12 5

4 6 3

3 5 10

5 6 1

5 10 2

6 10 3

7 10 2

7 9 3

9 10 5

8 9 1

7 8 2

[出力例]

565

■参照サイト
AtCoder Regular Contest 025

2022年3月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題C (だれじゃ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 計算量を削減するために, 累積和を使い, 出現回数をチェックしていくロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc024
// 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 pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
int sCum[101010][26];

int main(){
    
    // 1. 入力情報.
    int N, K;
    char c[101010];
    scanf("%d %d", &N, &K);
    scanf("%s", c);
    
    // 2. 累積和.
    rep(i, N){
        rep(j, 26) sCum[i + 1][j] = sCum[i][j];
        sCum[i + 1][c[i] - 'a']++;
    }
    
    // 3. ペアを保存.
    // -> {出現回数, 位置} を 保存.
    map<string, vi> m;
    rep(i, N - K + 1){
        string sCount;
        rep(j, 26) sCount += to_string(sCum[i + K][j] - sCum[i][j]);
        m[sCount].pb(i);
    }
    
    // 4. sort.
    for(auto &p : m) sort(all(p.b));
    
    // 5. 判定.
    bool ok = false;
    for(auto &p : m){
        // printf("p.a=%s p.b.front()=%d p.b.back()=%d\n", p.a.c_str(), p.b.front(), p.b.back());
        if(abs(p.b.front() - p.b.back()) >= K) ok = true;
        if(ok)                                 break;
    }
    
    // 6. 出力.
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc024

// 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 pb push_back

#define a first

#define b second

#define all(x) x.begin(), x.end()

int sCum[101010][26];

int main(){

// 1. 入力情報.

int N, K;

char c[101010];

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

scanf("%s", c);

// 2. 累積和.

rep(i, N){

rep(j, 26) sCum[i + 1][j] = sCum[i][j];

sCum[i + 1][c[i] - 'a']++;

}

// 3. ペアを保存.

// -> {出現回数, 位置} を保存.

map<string, vi> m;

rep(i, N - K + 1){

string sCount;

rep(j, 26) sCount += to_string(sCum[i + K][j] - sCum[i][j]);

m[sCount].pb(i);

}

// 4. sort.

for(auto &p : m) sort(all(p.b));

// 5. 判定.

bool ok = false;

for(auto &p : m){

// printf("p.a=%s p.b.front()=%d p.b.back()=%d\n", p.a.c_str(), p.b.front(), p.b.back());

if(abs(p.b.front() - p.b.back()) >= K) ok = true;

if(ok) break;

}

// 6. 出力.

printf("%s\n", ok ? "YES" : "NO");

return 0;

}

[入力例]
8 3
abcdbcae

[出力例]
YES

[入力例]
7 4
abcdcba

[出力例]
NO

[入力例]
8 1
issample

[出力例]
YES

[入力例]
30 5
lujvpsozzdwiveigvtkusfrknrddwe

[出力例]
NO

[入力例]
22 11
abracadabraabracadabra

[出力例]
YES

[入力例]
100 10
wxxmdlhtjcpzbwjhbgfynhntmwiequmpfaoczyfyjccacshwizahrfryrsdleglzmuynpieidylytonbngrzzvnukkwczgjjphbb

[出力例]
YES

[入力例]
500 25
csqeiypjxtpaadtrnvusdnleqpizvhywlfkgyzmpjgzfpbjauuxeisxcyxsbfxmoohtiohigcbhouoxkicfrpytvrxhmnrxkkfwplvdsnpzkaivlserltkhaypwclyirghuzuyhtbxioxydpckpmweygptacpcgccsqgtpcevigribhtsndqinktmredwjqkldnxnecjapwmyehsghfipfwxuhezinndyhmyipbgkjcyrsjadnxqmnntlgnafuzjlqgfbcpsiusbvylapckjuvgjutjvpajbnlhcsowtclxkdyxfieqzwkovrrdbaxqwvwqceqvmlkpdglwuzwfxkhmnfnwmqfpvwgvrvslzryzgurifqdvivcrgidfaadddegvrdvxiokhgxpteqnojvldecfzdeifgfbccccdeqggghiiinppqrssttvtvaksxptqdrfxenqzhyjldpwwrjabivtapnxaxlsgrieztkzsubvfzbnqj

[出力例]
YES

[入力例]

8 3

abcdbcae

[出力例]

YES

[入力例]

7 4

abcdcba

[出力例]

[入力例]

8 1

issample

[出力例]

YES

[入力例]

30 5

lujvpsozzdwiveigvtkusfrknrddwe

[出力例]

[入力例]

22 11

abracadabraabracadabra

[出力例]

YES

[入力例]

100 10

wxxmdlhtjcpzbwjhbgfynhntmwiequmpfaoczyfyjccacshwizahrfryrsdleglzmuynpieidylytonbngrzzvnukkwczgjjphbb

[出力例]

YES

[入力例]

500 25

csqeiypjxtpaadtrnvusdnleqpizvhywlfkgyzmpjgzfpbjauuxeisxcyxsbfxmoohtiohigcbhouoxkicfrpytvrxhmnrxkkfwplvdsnpzkaivlserltkhaypwclyirghuzuyhtbxioxydpckpmweygptacpcgccsqgtpcevigribhtsndqinktmredwjqkldnxnecjapwmyehsghfipfwxuhezinndyhmyipbgkjcyrsjadnxqmnntlgnafuzjlqgfbcpsiusbvylapckjuvgjutjvpajbnlhcsowtclxkdyxfieqzwkovrrdbaxqwvwqceqvmlkpdglwuzwfxkhmnfnwmqfpvwgvrvslzryzgurifqdvivcrgidfaadddegvrdvxiokhgxpteqnojvldecfzdeifgfbccccdeqggghiiinppqrssttvtvaksxptqdrfxenqzhyjldpwwrjabivtapnxaxlsgrieztkzsubvfzbnqj

[出力例]

YES

■参照サイト
AtCoder Regular Contest 024

2022年3月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題C (増築王高橋君) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 二分探索(応用版, 桁数オーバーフロー注意)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc021
// 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--)
LL a[101010], d[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%lld %d", &K, &N);
    rep(i, N) scanf("%lld %lld", &a[i], &d[i]);
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. 最後に選んだ増築費用を, m として, 合計 K 回 以上に出来るか？
        LL k = 0;
        rep(i, N) if(m >= a[i]) k += (m - a[i] + d[i]) / d[i];
        
        // 2-2. 判定結果.
        return (k >= K);
    };
    
    // 3. 二分探索で確認してみる.
    // -> 関数 f 内での オーバーフロー注意？
    LL l = 0, h = 2e12 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, N){
        if(h >= a[i]){
            // 建物 i の 増築回数.
            LL q = (h - a[i] + d[i]) / d[i];
            
            // 増築価格更新.
            // -> オーバーフロー注意？
            ans += (a[i] * q) + (q - 1) * q / 2 * d[i];
            
            // 増築回数 の 減算.
            K -= q;
        }
    }
    
    // 5. 残分.
    // -> K が マイナスのケースも考慮.
    ans += h * K;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc021

// 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--)

LL a[101010], d[101010];

int main(){

// 1. 入力情報.

int N;

LL K;

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

rep(i, N) scanf("%lld %lld", &a[i], &d[i]);

// 2. 評価関数.

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

// 2-1. 最後に選んだ増築費用を, m として, 合計 K 回以上に出来るか？

LL k = 0;

rep(i, N) if(m >= a[i]) k += (m - a[i] + d[i]) / d[i];

// 2-2. 判定結果.

return (k >= K);

};

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

// -> 関数 f 内でのオーバーフロー注意？

LL l = 0, h = 2e12 + 1;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 4. 集計.

LL ans = 0;

rep(i, N){

if(h >= a[i]){

// 建物 i の増築回数.

LL q = (h - a[i] + d[i]) / d[i];

// 増築価格更新.

// -> オーバーフロー注意？

ans += (a[i] * q) + (q - 1) * q / 2 * d[i];

// 増築回数の減算.

K -= q;

}

// 5. 残分.

// -> K がマイナスのケースも考慮.

ans += h * K;

// 6. 出力.

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

return 0;

}

[入力例]
4
3
10 3
12 4
15 5

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

[入力例]
8
4
1 1
10 1
100 1
1000 1

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

[入力例]
15
3
10 1
5 3
7 4

[出力例]
179

[入力例]
12
5
6 7
1 5
7 1
7 3
11 9

[出力例]
97

[入力例]
35
10
3 3
13 17
20 2
5 16
12 15
7 11
10 23
5 19
17 22
2 15

[出力例]
682

[入力例]
2022
15
28 103
63 88
20 122
118 23
111 41
19 37
77 114
50 89
54 56
14 79
3 42
95 80
74 38
59 40
122 108

[出力例]
7603076

[入力例]
20220322
20
777 943
582 728
1000 522
703 623
117 1133
305 821
1177 1001
1324 621
680 575
527 243
951 665
543 426
574 509
720 1173
87 84
603 293
692 737
704 567
93 78
190 1092

[出力例]
3692618300173731

100

101

102

103

104

105

106

107

108

109

110

[入力例]

10 3

12 4

15 5

[出力例]

※AtCoderテストケースより

[入力例]

1 1

10 1

100 1

1000 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1

5 3

7 4

[出力例]

179

[入力例]

6 7

1 5

7 1

7 3

11 9

[出力例]

[入力例]

3 3

13 17

20 2

5 16

12 15

7 11

10 23

5 19

17 22

2 15

[出力例]

682

[入力例]

2022

28 103

63 88

20 122

118 23

111 41

19 37

77 114

50 89

54 56

14 79

3 42

95 80

74 38

59 40

122 108

[出力例]

7603076

[入力例]

20220322

777 943

582 728

1000 522

703 623

117 1133

305 821

1177 1001

1324 621

680 575

527 243

951 665

543 426

574 509

720 1173

87 84

603 293

692 737

704 567

93 78

190 1092

[出力例]

3692618300173731

■参照サイト
AtCoder Regular Contest 021

2022年3月20日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 答えが計算可能なことに, 不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc140/editorial.pdf
// 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 p[101010], q[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &p[i + 1]);
        q[p[i + 1]] = i + 1;
    }
    
    // 2. 集計.
    LL ans = 0;
    multiset<int> S, T;
    S.insert(0);
    S.insert(0);
    T.insert(N + 1);
    T.insert(N + 1);
    repr(i, N, 1){
        // 追加.
        int at = q[i];
        S.insert(at);
        T.insert(at);
        
        // 集合 S で, 一番大きい要素, 二番目に大きい要素 を 設定.
        auto sItr = S.lower_bound(at);
        --sItr;
        int sMax1 = *sItr;
        --sItr;
        int sMax2 = *sItr;
        
        // 集合 T で, 一番小さい要素, 二番目に小さい要素 を 設定.
        auto tItr = T.lower_bound(at);
        ++tItr;
        int tMin1 = *tItr;
        ++tItr;
        int tMin2 = *tItr;
        
        // 加算.
        LL cur = (LL)(sMax1 - sMax2) * (LL)(tMin1 - at) + (LL)(at - sMax1) * (LL)(tMin2 - tMin1);
        // printf("sMax1=%d sMax2=%d tMin1=%d tMin2=%d at=%d cur=%lld\n", sMax1, sMax2, tMin1, tMin2, at, cur);
        ans += (LL)i * cur;
    }
    
    // 3. 出力.
    printf("%lld", ans);
    return 0;
    
}

// 解き直し.

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

// 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 p[101010], q[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%d", &p[i + 1]);

q[p[i + 1]] = i + 1;

}

// 2. 集計.

LL ans = 0;

multiset<int> S, T;

S.insert(0);

T.insert(N + 1);

repr(i, N, 1){

// 追加.

int at = q[i];

S.insert(at);

T.insert(at);

// 集合 S で, 一番大きい要素, 二番目に大きい要素を設定.

auto sItr = S.lower_bound(at);

--sItr;

int sMax1 = *sItr;

--sItr;

int sMax2 = *sItr;

// 集合 T で, 一番小さい要素, 二番目に小さい要素を設定.

auto tItr = T.lower_bound(at);

++tItr;

int tMin1 = *tItr;

++tItr;

int tMin2 = *tItr;

// 加算.

LL cur = (LL)(sMax1 - sMax2) * (LL)(tMin1 - at) + (LL)(at - sMax1) * (LL)(tMin2 - tMin1);

// printf("sMax1=%d sMax2=%d tMin1=%d tMin2=%d at=%d cur=%lld\n", sMax1, sMax2, tMin1, tMin2, at, cur);

ans += (LL)i * cur;

}

// 3. 出力.

printf("%lld", ans);

return 0;

}

[入力例]
3
2 3 1

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

[入力例]
5
1 2 3 4 5

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

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

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

[入力例]
2
1 2

[出力例]
1

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

[出力例]
313

[入力例]
50
30 2 47 45 21 22 36 9 38 34 42 6 12 25 40 44 48 43 4 31 1 46 26 32 29 10 24 18 39 28 20 35 33 17 41 27 15 5 3 16 14 13 50 23 37 11 49 7 8 19

[出力例]
50685

[入力例]
500
377 148 304 214 25 117 54 93 176 65 52 185 498 436 420 412 365 153 409 10 218 104 99 141 184 250 62 11 90 437 26 46 350 228 398 139 376 361 380 466 288 3 279 140 108 340 423 367 208 385 158 63 277 446 478 271 440 323 337 439 318 491 364 308 5 40 322 269 127 237 303 390 276 387 258 4 328 315 346 424 389 143 285 333 6 459 8 273 164 101 201 111 188 356 120 53 110 81 313 225 247 317 255 150 28 434 467 464 403 371 60 112 488 292 402 357 426 235 226 106 332 421 198 351 425 254 195 31 13 219 383 260 173 494 363 163 186 246 345 94 204 449 309 166 15 335 352 314 211 232 455 114 443 115 147 233 165 89 282 64 142 240 430 413 72 203 71 294 224 167 121 79 59 388 453 362 170 1 36 135 14 396 190 347 393 399 41 457 193 159 448 321 395 220 287 368 378 493 354 267 476 245 391 102 408 187 43 284 431 486 22 298 468 251 252 359 341 180 48 179 316 35 116 427 401 217 128 319 16 87 126 207 76 33 349 202 155 21 261 311 75 404 131 484 84 24 500 256 348 156 161 381 97 230 382 435 289 66 206 327 133 344 263 137 212 44 428 32 86 2 305 253 229 134 400 296 405 290 61 334 236 91 172 80 98 372 394 241 414 302 306 264 418 268 485 370 38 70 100 17 223 410 373 419 162 95 171 169 310 221 29 18 496 295 473 58 227 145 407 49 462 450 441 358 312 154 411 125 499 136 461 23 192 96 123 366 55 301 174 88 210 438 30 68 360 353 336 331 375 326 160 320 286 479 458 415 417 330 37 105 481 281 119 422 83 205 259 447 77 452 470 249 73 168 149 278 243 12 69 272 124 463 152 291 483 56 42 406 178 231 416 300 432 222 132 343 182 197 45 293 213 274 191 454 200 355 270 487 78 183 181 109 74 477 122 244 451 480 307 57 474 374 177 239 129 146 248 39 429 460 138 471 379 92 27 324 9 209 215 342 262 433 175 50 445 238 196 444 283 242 492 19 189 469 82 497 266 67 369 490 103 51 475 495 465 113 34 472 144 265 392 339 442 299 199 329 338 456 151 85 118 325 107 489 386 275 384 482 280 7 257 297 194 234 216 397 47 157 130 20

[出力例]
60354172

[入力例]
2500
785 1950 694 1393 942 878 2101 1097 2338 1174 438 1467 221 1083 2248 742 1956 1876 2244 1339 81 2123 1524 1792 1021 2187 596 1144 600 1235 1210 2295 841 954 110 45 1772 528 1067 444 1714 2028 1085 2062 1191 196 1674 2022 1920 2442 2334 1115 2321 1780 1497 867 1117 2266 1087 2090 468 2257 1842 498 1878 983 34 1634 885 2004 1830 1317 295 1349 2138 1395 1599 2252 2136 1249 347 979 2125 1943 1630 1949 429 218 2160 2450 820 855 1676 719 418 861 1007 200 1863 493 327 1877 2238 1265 1367 1932 931 504 1639 1417 285 1795 1438 999 1530 480 1214 1070 1471 94 1036 2463 2206 1605 1289 1105 476 1457 374 53 639 832 1185 1867 1702 278 889 2030 1088 1018 2223 1638 2247 1407 247 510 2434 2065 1004 1506 784 614 738 86 189 836 707 324 1518 448 1570 345 1974 1283 570 1903 1308 291 1684 245 557 1914 256 1340 423 2289 1957 127 1489 85 1014 388 106 523 1999 1343 1162 2305 401 809 1366 2424 1700 2058 571 2005 194 2271 2003 1195 730 1855 161 822 2083 1472 70 1732 144 458 1757 799 925 1890 2464 1291 1813 1124 1409 260 236 1147 467 1479 51 1505 13 333 124 1759 471 1694 1344 1485 1831 1583 1628 2258 833 62 1827 383 972 1944 96 1824 2000 1360 488 1029 342 1545 355 1851 868 1064 1072 1001 2194 1951 1929 2116 788 746 1326 1899 1767 831 1113 2362 1377 1069 2038 1983 294 562 46 1695 2222 443 1777 1157 1227 1282 2200 579 269 1193 459 2129 919 1516 1653 215 1763 2015 1402 83 599 370 14 362 876 1712 973 1212 1190 219 1661 829 2453 927 1864 741 157 959 697 709 1137 2085 1076 1820 938 1882 1724 1213 1175 457 1705 2290 2272 2190 460 2072 1173 638 966 1966 1509 529 2198 2093 864 1410 507 1710 1131 2240 1754 1374 19 1874 653 1028 1345 1180 1561 1720 1602 2346 1199 601 622 924 627 319 2088 764 2416 1941 1948 1519 2468 930 205 1595 865 371 1541 702 906 819 2051 2373 2390 316 2366 2437 1743 1002 613 2404 1352 1677 1900 2211 2158 1267 305 947 138 2011 2150 2422 1209 470 1013 904 1722 309 1187 329 102 2393 1277 2188 1810 2361 279 2104 1106 1594 574 1019 1660 146 1290 213 1947 430 2241 2302 180 1839 893 626 1779 1525 1536 2349 2273 1721 495 1387 112 1140 2403 1838 623 882 337 1424 1625 224 520 692 214 783 361 380 923 669 1324 1111 1741 798 2353 1726 2301 266 619 1650 212 1556 1698 1287 1815 1391 63 2130 1805 1959 209 284 2 2245 1774 1486 1433 552 2178 732 899 610 1907 3 814 1789 1434 139 665 1053 1736 1224 1987 2391 962 679 597 1840 598 774 1733 1552 501 308 2192 114 888 2175 1010 1852 808 1463 1513 1219 33 823 358 2280 1023 2455 280 1383 804 1927 556 1794 2291 1332 620 2007 892 1646 1522 699 703 916 662 1880 79 1022 1152 612 1181 1451 775 346 898 558 1689 801 1269 1231 1885 874 1857 339 325 2498 2254 1784 235 2127 349 1662 71 1973 857 1406 58 1156 126 1107 2243 67 2159 2182 1544 1295 489 1223 2318 1870 1844 676 1627 2406 2328 1296 1641 113 2119 1125 321 1758 508 2025 1454 132 500 1033 1919 691 2451 2228 1149 949 1217 1799 2343 1370 1829 2294 1821 2106 990 2102 1037 1738 1244 2304 1154 854 2121 1469 1431 1112 717 1620 968 2298 1444 364 1917 1955 1618 1584 2377 395 1791 1640 1461 300 1008 1165 223 708 2396 1163 2135 1823 901 72 165 1276 939 1849 1593 174 109 2486 191 2091 815 1167 974 1574 1723 826 1122 1657 2173 1970 4 913 917 384 1633 406 2137 2071 1281 2363 159 1517 1527 252 25 1372 2205 1555 1094 301 1945 375 1664 1379 960 690 2429 675 928 1672 1381 1581 1697 1134 550 1652 1713 1926 2212 2285 1197 2151 704 1101 618 509 2407 830 270 739 428 1755 2024 149 2439 56 10 203 2133 2355 714 1998 1474 2374 1538 437 910 2397 1568 1009 583 441 234 103 2053 1846 1215 1776 2332 805 1845 2419 1311 426 720 576 382 2491 434 122 394 2232 1788 341 420 1453 1309 1709 451 2460 549 2475 880 503 2112 204 2400 244 581 274 1888 1207 2099 532 313 2069 1063 1992 2331 2063 1323 150 1024 1891 73 630 2270 1504 1632 1783 1104 2357 2214 1502 644 766 554 589 828 148 825 834 1095 29 1756 729 240 193 1055 1680 2394 1447 1145 178 1378 1881 982 1911 2210 1232 633 171 1673 1785 2359 2231 2048 683 2170 183 2490 2227 1427 18 1737 2103 2499 1262 1158 564 1682 2284 1904 449 1533 2381 2147 2484 2440 1335 2447 2480 162 1272 1858 1411 2410 1222 1439 945 379 2234 173 522 1571 2113 762 338 995 76 1166 1750 1984 187 1194 531 1728 230 229 1426 963 314 2013 185 1760 1671 1139 228 534 2436 1868 1564 2032 2327 1691 1127 1590 2191 894 1396 1035 1601 2128 1373 296 1790 1921 2380 1531 1740 1442 1925 773 657 1940 2168 757 357 478 1643 634 1108 2431 1141 1116 68 142 1543 254 650 494 1196 956 2329 1092 353 1218 870 875 1298 2261 170 722 141 712 1693 2446 1635 2307 485 1699 1869 951 846 2213 2287 2084 421 1853 992 517 1871 521 1537 42 303 518 1979 2189 265 1082 1186 1030 2452 572 386 2299 2408 1305 344 759 1077 1716 288 603 1663 251 1202 2268 2097 1142 354 1161 322 1675 1466 706 2172 965 461 1164 2311 210 2131 994 1686 607 2177 1727 2313 217 1293 1751 527 65 1579 220 2250 575 1735 2145 1996 725 1958 117 1521 2277 2385 793 2308 747 397 2274 1328 172 844 985 896 680 155 998 543 1368 1278 415 60 1084 17 2255 312 537 1261 2368 2282 735 2476 2309 1254 1535 1093 267 758 259 2193 883 116 1357 2215 1707 1553 2441 2183 1045 1796 1875 2076 918 2322 1415 2449 1251 5 718 1047 1425 376 677 1850 1136 1081 290 2111 2494 343 2479 1408 1171 2208 1894 1336 1764 2345 1245 1832 368 821 1997 1889 1109 1264 1394 2209 688 1170 1622 104 1569 2059 621 206 40 2296 1354 967 1268 1995 1576 511 2398 1960 580 800 1184 1612 2082 1416 47 1616 1648 2239 239 791 1146 463 1747 282 728 2432 891 1964 933 863 1459 915 1449 2417 1971 1240 1865 332 869 1135 1746 1437 1440 497 271 969 1886 1749 1032 1060 439 1651 1400 1048 232 26 2387 392 1333 1132 2010 1450 1797 175 1739 78 1573 334 2221 547 1835 585 642 1355 255 2461 1507 1906 2086 1300 936 553 1967 1418 1837 2249 283 84 2392 566 253 1860 1255 743 23 1793 763 120 1508 981 737 750 606 297 2375 381 1771 1392 1401 90 991 2456 1976 2496 1811 2224 540 1809 2352 2140 1183 286 1090 1346 1896 276 2060 671 797 2369 2482 292 1577 2413 997 2251 2161 1990 1938 1499 582 275 525 1347 2339 1916 1969 1246 559 2225 1054 1302 839 569 152 914 1031 769 2386 1562 1582 1205 695 446 2046 404 890 1334 77 237 372 1554 2040 2493 1399 2471 1079 1589 472 1478 1273 1934 1419 1312 356 41 1065 1814 2035 1520 2019 1912 929 238 95 156 1405 2166 105 1704 107 565 8 2372 473 1985 1706 1325 2107 2124 2014 140 845 1242 1089 505 932 755 1703 1511 733 1361 1715 1315 2066 751 2152 69 721 2002 1455 168 957 2412 1609 2364 2283 88 2047 611 1056 2155 1523 31 262 1526 1879 340 377 2425 1614 2379 1390 182 2333 756 1610 802 307 1512 99 701 1436 483 405 1898 28 2050 2389 648 1498 1624 181 66 306 2089 1848 135 1924 273 177 1825 2037 2288 587 2033 2448 2267 1297 1369 1243 43 1 1559 64 1192 1986 1005 2197 1314 2199 1119 1977 1429 2203 514 2149 1384 2078 1443 2180 1364 1993 887 776 1761 840 2080 943 2105 560 302 2418 555 2045 1188 82 131 1611 197 1266 1071 1550 961 970 1613 2041 2202 1435 944 1256 129 97 2320 1621 920 1656 490 1968 1120 842 538 1778 1380 1631 2039 1565 1606 1580 2246 1854 315 1670 111 32 466 1130 1567 1363 2169 1398 1362 226 818 1994 242 2061 1600 310 1049 2216 2314 716 1413 977 811 2337 1389 563 827 912 359 1385 1597 2459 2204 1375 1169 654 378 2122 749 1456 1241 1915 723 2281 996 2336 1587 629 55 258 748 851 2454 1052 1203 2286 2143 2077 264 948 693 241 1476 1280 2438 2371 1893 1801 866 1422 1954 2263 80 2036 636 153 1252 1669 796 1342 2264 2276 1586 52 1843 2079 222 2195 2017 1233 852 1981 1098 903 2382 2043 1414 2430 849 795 179 134 1572 2259 1388 978 2016 993 1234 980 643 1464 2340 1039 1745 591 1782 2469 1668 2120 1636 2146 790 1062 1348 568 2132 656 2021 673 631 2472 1762 1228 593 1040 860 647 136 909 2029 1096 1787 2176 2457 1321 1818 431 515 1274 616 1253 1226 1769 442 464 661 1826 1304 2443 810 940 1046 435 1692 1204 1766 813 2383 895 360 188 1129 9 1623 645 526 519 1806 1221 640 1798 2324 1006 2162 1200 658 1460 2341 588 2421 1591 61 778 649 1902 1484 1532 216 1872 1563 533 496 462 1884 859 744 133 1027 2074 502 1972 1493 789 373 440 2070 2462 687 425 1946 145 1428 101 1645 685 2465 2073 1991 335 897 1110 506 263 363 760 137 257 1980 862 1816 1619 705 1011 202 664 2351 479 348 1292 663 2365 872 884 907 158 1331 2142 396 37 2196 2326 926 1322 1462 477 2445 422 2144 921 1557 2049 328 2219 1468 536 419 535 779 781 49 1988 710 2096 1942 544 410 1482 1817 1404 2034 2444 1441 492 1936 681 545 752 922 736 1800 1341 2265 1465 2233 59 986 1933 670 1114 2098 123 1285 89 1074 1310 369 2376 2171 2237 2358 1935 387 2157 1198 1148 1803 7 577 1275 36 1327 1487 1121 2134 326 768 1059 953 1448 624 1989 93 198 400 2064 2100 1073 1731 2201 1103 1491 16 1247 512 770 1753 2500 2297 2087 1744 1909 27 1592 248 424 777 30 1432 243 1470 1051 1861 609 908 1748 1208 1458 1201 1248 761 287 1928 2052 1802 75 765 2154 812 713 900 1607 154 2020 1494 2181 1679 2300 277 674 1892 2370 1359 1102 2485 454 1481 1804 1042 567 311 1873 163 2141 231 2488 1020 391 911 1534 1236 792 1337 586 1216 261 1365 413 1316 1263 1123 233 689 1329 298 1666 176 2164 1965 2354 1307 225 121 628 1962 1649 2068 1558 1421 2497 1220 772 1765 806 1356 1717 847 2094 1729 646 1588 98 2184 491 2483 1629 414 682 499 484 700 1540 1901 678 835 602 1017 1834 147 1138 1176 119 2207 2217 1681 1617 399 964 143 989 2367 432 955 1603 1299 2347 843 935 2185 2310 2095 1475 1529 2179 2126 184 684 1615 186 1351 1034 2262 2110 2388 2163 786 2167 20 780 1133 1012 1690 1515 2018 856 1445 595 1930 1229 641 2415 1725 486 541 853 2487 1546 734 946 1038 1303 1178 1542 2378 416 1688 1608 1091 1382 2356 1931 2008 1126 2275 1866 652 551 44 2139 1403 1250 2075 1781 1151 2235 2306 2081 436 1412 2001 592 2420 24 366 1452 987 390 1923 686 2481 1397 455 594 2148 1100 1847 2054 1473 1500 2492 879 417 289 1128 2402 1856 1118 433 1841 753 1883 637 1177 1575 452 1514 1598 1978 1708 659 1496 1078 2458 2186 731 590 524 573 1260 975 2315 1353 1016 2426 2256 1271 617 548 2220 199 160 299 2292 1446 352 1510 1953 2109 208 715 2115 2427 1819 192 660 2466 1143 1313 934 1050 1922 952 1480 2006 1961 2253 1718 22 1168 988 666 971 330 1155 1975 632 1905 447 2401 2405 1211 1043 1752 1812 1279 201 1160 2348 1773 169 1153 92 1086 1044 1807 635 465 2495 1284 281 651 474 11 2319 2395 304 1836 1206 787 1338 1730 1318 1742 817 958 2044 367 2031 403 1696 393 1306 1080 1350 469 1862 1058 794 850 1503 2316 2067 1066 1659 128 1808 1833 2260 1179 1585 1822 937 2153 2042 578 667 1477 546 268 803 2114 950 1483 608 516 2474 941 2026 2242 625 1913 227 2384 1654 2118 848 2174 249 2350 164 1239 1230 1376 50 1897 1495 2055 1423 1665 724 1288 2303 2478 398 450 1658 858 318 905 2342 2325 6 453 1549 1939 1061 1952 711 2323 48 487 2269 873 1330 409 561 456 1734 1701 1026 35 824 2435 1719 74 1420 871 2428 696 118 1319 1828 1182 740 745 976 350 1687 530 2344 1041 408 881 2057 39 1238 385 54 2312 21 427 2467 2423 246 12 130 1320 807 2165 877 1501 250 1551 293 2156 1908 475 2409 2009 1015 1490 445 1068 389 1768 1172 2330 323 1159 481 1937 1647 1895 125 1225 1358 1548 411 1642 1770 542 1859 2317 2279 605 1301 1566 668 402 2226 2278 2012 837 1667 604 2236 211 167 1918 1626 272 1711 2027 2335 190 1258 726 2399 1596 2293 412 1539 1560 615 816 1644 38 1547 1604 1637 1982 1488 336 1683 1492 782 1786 672 2108 2473 2230 320 754 207 1430 902 1910 584 1685 727 1528 2470 1237 1000 2117 482 771 1678 2056 2489 331 1257 1150 1887 365 2218 838 1578 100 151 984 1025 1259 886 166 513 1189 2023 317 767 2229 1386 1075 1099 1286 2433 2360 108 1655 1003 2411 91 351 1294 87 195 539 655 2414 1270 15 698 57 407 1057 2477 1775 1963 115 1371 2092

[出力例]
7740144875

[入力例]

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

8 2 7 3 4 5 6 1

[出力例]

136

※AtCoderテストケースより

[入力例]

1 2

[出力例]

[入力例]

5 7 4 1 10 9 6 3 2 8

[出力例]

313

[入力例]

30 2 47 45 21 22 36 9 38 34 42 6 12 25 40 44 48 43 4 31 1 46 26 32 29 10 24 18 39 28 20 35 33 17 41 27 15 5 3 16 14 13 50 23 37 11 49 7 8 19

[出力例]

50685

[入力例]

500

377 148 304 214 25 117 54 93 176 65 52 185 498 436 420 412 365 153 409 10 218 104 99 141 184 250 62 11 90 437 26 46 350 228 398 139 376 361 380 466 288 3 279 140 108 340 423 367 208 385 158 63 277 446 478 271 440 323 337 439 318 491 364 308 5 40 322 269 127 237 303 390 276 387 258 4 328 315 346 424 389 143 285 333 6 459 8 273 164 101 201 111 188 356 120 53 110 81 313 225 247 317 255 150 28 434 467 464 403 371 60 112 488 292 402 357 426 235 226 106 332 421 198 351 425 254 195 31 13 219 383 260 173 494 363 163 186 246 345 94 204 449 309 166 15 335 352 314 211 232 455 114 443 115 147 233 165 89 282 64 142 240 430 413 72 203 71 294 224 167 121 79 59 388 453 362 170 1 36 135 14 396 190 347 393 399 41 457 193 159 448 321 395 220 287 368 378 493 354 267 476 245 391 102 408 187 43 284 431 486 22 298 468 251 252 359 341 180 48 179 316 35 116 427 401 217 128 319 16 87 126 207 76 33 349 202 155 21 261 311 75 404 131 484 84 24 500 256 348 156 161 381 97 230 382 435 289 66 206 327 133 344 263 137 212 44 428 32 86 2 305 253 229 134 400 296 405 290 61 334 236 91 172 80 98 372 394 241 414 302 306 264 418 268 485 370 38 70 100 17 223 410 373 419 162 95 171 169 310 221 29 18 496 295 473 58 227 145 407 49 462 450 441 358 312 154 411 125 499 136 461 23 192 96 123 366 55 301 174 88 210 438 30 68 360 353 336 331 375 326 160 320 286 479 458 415 417 330 37 105 481 281 119 422 83 205 259 447 77 452 470 249 73 168 149 278 243 12 69 272 124 463 152 291 483 56 42 406 178 231 416 300 432 222 132 343 182 197 45 293 213 274 191 454 200 355 270 487 78 183 181 109 74 477 122 244 451 480 307 57 474 374 177 239 129 146 248 39 429 460 138 471 379 92 27 324 9 209 215 342 262 433 175 50 445 238 196 444 283 242 492 19 189 469 82 497 266 67 369 490 103 51 475 495 465 113 34 472 144 265 392 339 442 299 199 329 338 456 151 85 118 325 107 489 386 275 384 482 280 7 257 297 194 234 216 397 47 157 130 20

[出力例]

60354172

[入力例]

2500

785 1950 694 1393 942 878 2101 1097 2338 1174 438 1467 221 1083 2248 742 1956 1876 2244 1339 81 2123 1524 1792 1021 2187 596 1144 600 1235 1210 2295 841 954 110 45 1772 528 1067 444 1714 2028 1085 2062 1191 196 1674 2022 1920 2442 2334 1115 2321 1780 1497 867 1117 2266 1087 2090 468 2257 1842 498 1878 983 34 1634 885 2004 1830 1317 295 1349 2138 1395 1599 2252 2136 1249 347 979 2125 1943 1630 1949 429 218 2160 2450 820 855 1676 719 418 861 1007 200 1863 493 327 1877 2238 1265 1367 1932 931 504 1639 1417 285 1795 1438 999 1530 480 1214 1070 1471 94 1036 2463 2206 1605 1289 1105 476 1457 374 53 639 832 1185 1867 1702 278 889 2030 1088 1018 2223 1638 2247 1407 247 510 2434 2065 1004 1506 784 614 738 86 189 836 707 324 1518 448 1570 345 1974 1283 570 1903 1308 291 1684 245 557 1914 256 1340 423 2289 1957 127 1489 85 1014 388 106 523 1999 1343 1162 2305 401 809 1366 2424 1700 2058 571 2005 194 2271 2003 1195 730 1855 161 822 2083 1472 70 1732 144 458 1757 799 925 1890 2464 1291 1813 1124 1409 260 236 1147 467 1479 51 1505 13 333 124 1759 471 1694 1344 1485 1831 1583 1628 2258 833 62 1827 383 972 1944 96 1824 2000 1360 488 1029 342 1545 355 1851 868 1064 1072 1001 2194 1951 1929 2116 788 746 1326 1899 1767 831 1113 2362 1377 1069 2038 1983 294 562 46 1695 2222 443 1777 1157 1227 1282 2200 579 269 1193 459 2129 919 1516 1653 215 1763 2015 1402 83 599 370 14 362 876 1712 973 1212 1190 219 1661 829 2453 927 1864 741 157 959 697 709 1137 2085 1076 1820 938 1882 1724 1213 1175 457 1705 2290 2272 2190 460 2072 1173 638 966 1966 1509 529 2198 2093 864 1410 507 1710 1131 2240 1754 1374 19 1874 653 1028 1345 1180 1561 1720 1602 2346 1199 601 622 924 627 319 2088 764 2416 1941 1948 1519 2468 930 205 1595 865 371 1541 702 906 819 2051 2373 2390 316 2366 2437 1743 1002 613 2404 1352 1677 1900 2211 2158 1267 305 947 138 2011 2150 2422 1209 470 1013 904 1722 309 1187 329 102 2393 1277 2188 1810 2361 279 2104 1106 1594 574 1019 1660 146 1290 213 1947 430 2241 2302 180 1839 893 626 1779 1525 1536 2349 2273 1721 495 1387 112 1140 2403 1838 623 882 337 1424 1625 224 520 692 214 783 361 380 923 669 1324 1111 1741 798 2353 1726 2301 266 619 1650 212 1556 1698 1287 1815 1391 63 2130 1805 1959 209 284 2 2245 1774 1486 1433 552 2178 732 899 610 1907 3 814 1789 1434 139 665 1053 1736 1224 1987 2391 962 679 597 1840 598 774 1733 1552 501 308 2192 114 888 2175 1010 1852 808 1463 1513 1219 33 823 358 2280 1023 2455 280 1383 804 1927 556 1794 2291 1332 620 2007 892 1646 1522 699 703 916 662 1880 79 1022 1152 612 1181 1451 775 346 898 558 1689 801 1269 1231 1885 874 1857 339 325 2498 2254 1784 235 2127 349 1662 71 1973 857 1406 58 1156 126 1107 2243 67 2159 2182 1544 1295 489 1223 2318 1870 1844 676 1627 2406 2328 1296 1641 113 2119 1125 321 1758 508 2025 1454 132 500 1033 1919 691 2451 2228 1149 949 1217 1799 2343 1370 1829 2294 1821 2106 990 2102 1037 1738 1244 2304 1154 854 2121 1469 1431 1112 717 1620 968 2298 1444 364 1917 1955 1618 1584 2377 395 1791 1640 1461 300 1008 1165 223 708 2396 1163 2135 1823 901 72 165 1276 939 1849 1593 174 109 2486 191 2091 815 1167 974 1574 1723 826 1122 1657 2173 1970 4 913 917 384 1633 406 2137 2071 1281 2363 159 1517 1527 252 25 1372 2205 1555 1094 301 1945 375 1664 1379 960 690 2429 675 928 1672 1381 1581 1697 1134 550 1652 1713 1926 2212 2285 1197 2151 704 1101 618 509 2407 830 270 739 428 1755 2024 149 2439 56 10 203 2133 2355 714 1998 1474 2374 1538 437 910 2397 1568 1009 583 441 234 103 2053 1846 1215 1776 2332 805 1845 2419 1311 426 720 576 382 2491 434 122 394 2232 1788 341 420 1453 1309 1709 451 2460 549 2475 880 503 2112 204 2400 244 581 274 1888 1207 2099 532 313 2069 1063 1992 2331 2063 1323 150 1024 1891 73 630 2270 1504 1632 1783 1104 2357 2214 1502 644 766 554 589 828 148 825 834 1095 29 1756 729 240 193 1055 1680 2394 1447 1145 178 1378 1881 982 1911 2210 1232 633 171 1673 1785 2359 2231 2048 683 2170 183 2490 2227 1427 18 1737 2103 2499 1262 1158 564 1682 2284 1904 449 1533 2381 2147 2484 2440 1335 2447 2480 162 1272 1858 1411 2410 1222 1439 945 379 2234 173 522 1571 2113 762 338 995 76 1166 1750 1984 187 1194 531 1728 230 229 1426 963 314 2013 185 1760 1671 1139 228 534 2436 1868 1564 2032 2327 1691 1127 1590 2191 894 1396 1035 1601 2128 1373 296 1790 1921 2380 1531 1740 1442 1925 773 657 1940 2168 757 357 478 1643 634 1108 2431 1141 1116 68 142 1543 254 650 494 1196 956 2329 1092 353 1218 870 875 1298 2261 170 722 141 712 1693 2446 1635 2307 485 1699 1869 951 846 2213 2287 2084 421 1853 992 517 1871 521 1537 42 303 518 1979 2189 265 1082 1186 1030 2452 572 386 2299 2408 1305 344 759 1077 1716 288 603 1663 251 1202 2268 2097 1142 354 1161 322 1675 1466 706 2172 965 461 1164 2311 210 2131 994 1686 607 2177 1727 2313 217 1293 1751 527 65 1579 220 2250 575 1735 2145 1996 725 1958 117 1521 2277 2385 793 2308 747 397 2274 1328 172 844 985 896 680 155 998 543 1368 1278 415 60 1084 17 2255 312 537 1261 2368 2282 735 2476 2309 1254 1535 1093 267 758 259 2193 883 116 1357 2215 1707 1553 2441 2183 1045 1796 1875 2076 918 2322 1415 2449 1251 5 718 1047 1425 376 677 1850 1136 1081 290 2111 2494 343 2479 1408 1171 2208 1894 1336 1764 2345 1245 1832 368 821 1997 1889 1109 1264 1394 2209 688 1170 1622 104 1569 2059 621 206 40 2296 1354 967 1268 1995 1576 511 2398 1960 580 800 1184 1612 2082 1416 47 1616 1648 2239 239 791 1146 463 1747 282 728 2432 891 1964 933 863 1459 915 1449 2417 1971 1240 1865 332 869 1135 1746 1437 1440 497 271 969 1886 1749 1032 1060 439 1651 1400 1048 232 26 2387 392 1333 1132 2010 1450 1797 175 1739 78 1573 334 2221 547 1835 585 642 1355 255 2461 1507 1906 2086 1300 936 553 1967 1418 1837 2249 283 84 2392 566 253 1860 1255 743 23 1793 763 120 1508 981 737 750 606 297 2375 381 1771 1392 1401 90 991 2456 1976 2496 1811 2224 540 1809 2352 2140 1183 286 1090 1346 1896 276 2060 671 797 2369 2482 292 1577 2413 997 2251 2161 1990 1938 1499 582 275 525 1347 2339 1916 1969 1246 559 2225 1054 1302 839 569 152 914 1031 769 2386 1562 1582 1205 695 446 2046 404 890 1334 77 237 372 1554 2040 2493 1399 2471 1079 1589 472 1478 1273 1934 1419 1312 356 41 1065 1814 2035 1520 2019 1912 929 238 95 156 1405 2166 105 1704 107 565 8 2372 473 1985 1706 1325 2107 2124 2014 140 845 1242 1089 505 932 755 1703 1511 733 1361 1715 1315 2066 751 2152 69 721 2002 1455 168 957 2412 1609 2364 2283 88 2047 611 1056 2155 1523 31 262 1526 1879 340 377 2425 1614 2379 1390 182 2333 756 1610 802 307 1512 99 701 1436 483 405 1898 28 2050 2389 648 1498 1624 181 66 306 2089 1848 135 1924 273 177 1825 2037 2288 587 2033 2448 2267 1297 1369 1243 43 1 1559 64 1192 1986 1005 2197 1314 2199 1119 1977 1429 2203 514 2149 1384 2078 1443 2180 1364 1993 887 776 1761 840 2080 943 2105 560 302 2418 555 2045 1188 82 131 1611 197 1266 1071 1550 961 970 1613 2041 2202 1435 944 1256 129 97 2320 1621 920 1656 490 1968 1120 842 538 1778 1380 1631 2039 1565 1606 1580 2246 1854 315 1670 111 32 466 1130 1567 1363 2169 1398 1362 226 818 1994 242 2061 1600 310 1049 2216 2314 716 1413 977 811 2337 1389 563 827 912 359 1385 1597 2459 2204 1375 1169 654 378 2122 749 1456 1241 1915 723 2281 996 2336 1587 629 55 258 748 851 2454 1052 1203 2286 2143 2077 264 948 693 241 1476 1280 2438 2371 1893 1801 866 1422 1954 2263 80 2036 636 153 1252 1669 796 1342 2264 2276 1586 52 1843 2079 222 2195 2017 1233 852 1981 1098 903 2382 2043 1414 2430 849 795 179 134 1572 2259 1388 978 2016 993 1234 980 643 1464 2340 1039 1745 591 1782 2469 1668 2120 1636 2146 790 1062 1348 568 2132 656 2021 673 631 2472 1762 1228 593 1040 860 647 136 909 2029 1096 1787 2176 2457 1321 1818 431 515 1274 616 1253 1226 1769 442 464 661 1826 1304 2443 810 940 1046 435 1692 1204 1766 813 2383 895 360 188 1129 9 1623 645 526 519 1806 1221 640 1798 2324 1006 2162 1200 658 1460 2341 588 2421 1591 61 778 649 1902 1484 1532 216 1872 1563 533 496 462 1884 859 744 133 1027 2074 502 1972 1493 789 373 440 2070 2462 687 425 1946 145 1428 101 1645 685 2465 2073 1991 335 897 1110 506 263 363 760 137 257 1980 862 1816 1619 705 1011 202 664 2351 479 348 1292 663 2365 872 884 907 158 1331 2142 396 37 2196 2326 926 1322 1462 477 2445 422 2144 921 1557 2049 328 2219 1468 536 419 535 779 781 49 1988 710 2096 1942 544 410 1482 1817 1404 2034 2444 1441 492 1936 681 545 752 922 736 1800 1341 2265 1465 2233 59 986 1933 670 1114 2098 123 1285 89 1074 1310 369 2376 2171 2237 2358 1935 387 2157 1198 1148 1803 7 577 1275 36 1327 1487 1121 2134 326 768 1059 953 1448 624 1989 93 198 400 2064 2100 1073 1731 2201 1103 1491 16 1247 512 770 1753 2500 2297 2087 1744 1909 27 1592 248 424 777 30 1432 243 1470 1051 1861 609 908 1748 1208 1458 1201 1248 761 287 1928 2052 1802 75 765 2154 812 713 900 1607 154 2020 1494 2181 1679 2300 277 674 1892 2370 1359 1102 2485 454 1481 1804 1042 567 311 1873 163 2141 231 2488 1020 391 911 1534 1236 792 1337 586 1216 261 1365 413 1316 1263 1123 233 689 1329 298 1666 176 2164 1965 2354 1307 225 121 628 1962 1649 2068 1558 1421 2497 1220 772 1765 806 1356 1717 847 2094 1729 646 1588 98 2184 491 2483 1629 414 682 499 484 700 1540 1901 678 835 602 1017 1834 147 1138 1176 119 2207 2217 1681 1617 399 964 143 989 2367 432 955 1603 1299 2347 843 935 2185 2310 2095 1475 1529 2179 2126 184 684 1615 186 1351 1034 2262 2110 2388 2163 786 2167 20 780 1133 1012 1690 1515 2018 856 1445 595 1930 1229 641 2415 1725 486 541 853 2487 1546 734 946 1038 1303 1178 1542 2378 416 1688 1608 1091 1382 2356 1931 2008 1126 2275 1866 652 551 44 2139 1403 1250 2075 1781 1151 2235 2306 2081 436 1412 2001 592 2420 24 366 1452 987 390 1923 686 2481 1397 455 594 2148 1100 1847 2054 1473 1500 2492 879 417 289 1128 2402 1856 1118 433 1841 753 1883 637 1177 1575 452 1514 1598 1978 1708 659 1496 1078 2458 2186 731 590 524 573 1260 975 2315 1353 1016 2426 2256 1271 617 548 2220 199 160 299 2292 1446 352 1510 1953 2109 208 715 2115 2427 1819 192 660 2466 1143 1313 934 1050 1922 952 1480 2006 1961 2253 1718 22 1168 988 666 971 330 1155 1975 632 1905 447 2401 2405 1211 1043 1752 1812 1279 201 1160 2348 1773 169 1153 92 1086 1044 1807 635 465 2495 1284 281 651 474 11 2319 2395 304 1836 1206 787 1338 1730 1318 1742 817 958 2044 367 2031 403 1696 393 1306 1080 1350 469 1862 1058 794 850 1503 2316 2067 1066 1659 128 1808 1833 2260 1179 1585 1822 937 2153 2042 578 667 1477 546 268 803 2114 950 1483 608 516 2474 941 2026 2242 625 1913 227 2384 1654 2118 848 2174 249 2350 164 1239 1230 1376 50 1897 1495 2055 1423 1665 724 1288 2303 2478 398 450 1658 858 318 905 2342 2325 6 453 1549 1939 1061 1952 711 2323 48 487 2269 873 1330 409 561 456 1734 1701 1026 35 824 2435 1719 74 1420 871 2428 696 118 1319 1828 1182 740 745 976 350 1687 530 2344 1041 408 881 2057 39 1238 385 54 2312 21 427 2467 2423 246 12 130 1320 807 2165 877 1501 250 1551 293 2156 1908 475 2409 2009 1015 1490 445 1068 389 1768 1172 2330 323 1159 481 1937 1647 1895 125 1225 1358 1548 411 1642 1770 542 1859 2317 2279 605 1301 1566 668 402 2226 2278 2012 837 1667 604 2236 211 167 1918 1626 272 1711 2027 2335 190 1258 726 2399 1596 2293 412 1539 1560 615 816 1644 38 1547 1604 1637 1982 1488 336 1683 1492 782 1786 672 2108 2473 2230 320 754 207 1430 902 1910 584 1685 727 1528 2470 1237 1000 2117 482 771 1678 2056 2489 331 1257 1150 1887 365 2218 838 1578 100 151 984 1025 1259 886 166 513 1189 2023 317 767 2229 1386 1075 1099 1286 2433 2360 108 1655 1003 2411 91 351 1294 87 195 539 655 2414 1270 15 698 57 407 1057 2477 1775 1963 115 1371 2092

[出力例]

7740144875

■参照サイト
AtCoder Beginner Contest 140

2022年3月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題C (高橋君と国家) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc029
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using T3 = tuple<int, 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 all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<T3> t;
    rep(i, N){
        int c;
        scanf("%d", &c);
        t.emplace_back(c, 0, i + 1);
    }
    rep(i, M){
        int a, b, r;
        scanf("%d %d %d", &a, &b, &r);
        t.emplace_back(r, a, b);
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL ans = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        int c = get<0>(t[i]); // コスト.
        
        // 3-2. 辺を追加するか？
        if(!uf.same(u, v)){
            // 辺を追加.
            uf.unite(u, v);
            
            // コスト更新.
            ans += (LL)c;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc029

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using T3 = tuple<int, 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 all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vector<T3> t;

rep(i, N){

int c;

scanf("%d", &c);

t.emplace_back(c, 0, i + 1);

}

rep(i, M){

int a, b, r;

scanf("%d %d %d", &a, &b, &r);

t.emplace_back(r, a, b);

}

// 2. sort.

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL ans = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]); // 頂点.

int v = get<2>(t[i]); // 頂点.

int c = get<0>(t[i]); // コスト.

// 3-2. 辺を追加するか？

if(!uf.same(u, v)){

// 辺を追加.

uf.unite(u, v);

// コスト更新.

ans += (LL)c;

}

// 4. 出力.

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

return 0;

}

[入力例]
7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

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

[入力例]
3 3
50
50
50
1 2 60
1 3 60
2 3 60

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

[入力例]
5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

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

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

[出力例]
6

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

[出力例]
11

[入力例]
10 15
51
86
103
40
72
92
108
39
22
16
1 2 17
1 3 18
1 5 12
2 3 17
2 8 27
3 10 18
4 5 29
4 6 8
5 6 16
4 10 21
6 9 5
7 8 11
7 9 20
7 10 1
8 9 8

[出力例]
111

100

101

102

103

104

105

106

107

108

[入力例]

7 8

1 2 40

1 3 50

1 4 60

2 5 90

3 4 80

4 5 110

5 6 60

6 7 50

[出力例]

350

※AtCoderテストケースより

[入力例]

3 3

1 2 60

1 3 60

2 3 60

[出力例]

150

※AtCoderテストケースより

[入力例]

5 7

1 3 20

1 4 70

1 5 30

2 3 30

2 4 90

3 4 40

4 5 80

[出力例]

160

※AtCoderテストケースより

[入力例]

3 3

1 3 1

2 3 2

1 2 6

[出力例]

[入力例]

3 3

1 2 9

1 3 8

2 3 3

[出力例]

[入力例]

10 15

103

108

1 2 17

1 3 18

1 5 12

2 3 17

2 8 27

3 10 18

4 5 29

4 6 8

5 6 16

4 10 21

6 9 5

7 8 11

7 9 20

7 10 1

8 9 8

[出力例]

111

■参照サイト
AtCoder Regular Contest 029
Union-Find木
 競プロ典型 90 問の問題049

2022年3月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題C (アットコーダー王国の交通事情) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc035
// 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--)
const LL INF = 202020202020202020;
LL d[404][404];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) rep(j, N) if(i != j) d[i][j] = INF;
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        --a, --b;
        d[a][b] = c;
        d[b][a] = c;
    }
    
    // 2. Warshall–Floyd法(※各頂点間の最短距離を保存).
    rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    
    // 3. クエリ回答.
    int K;
    scanf("%d", &K);
    rep(_, K){
        // 3-1. 道路を新たに建設.
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        --x, --y;
        
        // 3-2. 最短距離更新.
        rep(i, N) rep(j, N) d[i][j] = min({d[i][j], d[i][x] + d[y][j] + (LL)z, d[i][y] + d[x][j] + (LL)z});
        
        // 3-3. 幸福度.
        LL ans = 0;
        rep(i, N) repx(j, i + 1, N) ans += d[i][j];
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc035

// 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--)

const LL INF = 202020202020202020;

LL d[404][404];

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

rep(i, N) rep(j, N) if(i != j) d[i][j] = INF;

rep(i, M){

int a, b, c;

scanf("%d %d %d", &a, &b, &c);

--a, --b;

d[a][b] = c;

d[b][a] = c;

}

// 2. Warshall–Floyd法(※各頂点間の最短距離を保存).

rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

// 3. クエリ回答.

int K;

scanf("%d", &K);

rep(_, K){

// 3-1. 道路を新たに建設.

int x, y, z;

scanf("%d %d %d", &x, &y, &z);

--x, --y;

// 3-2. 最短距離更新.

rep(i, N) rep(j, N) d[i][j] = min({d[i][j], d[i][x] + d[y][j] + (LL)z, d[i][y] + d[x][j] + (LL)z});

// 3-3. 幸福度.

LL ans = 0;

rep(i, N) repx(j, i + 1, N) ans += d[i][j];

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

}

return 0;

}

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

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

[入力例]
8 16
8 7 38
2 8 142
5 2 722
8 6 779
4 6 820
1 3 316
1 7 417
8 3 41
1 4 801
3 2 126
4 2 71
8 4 738
4 3 336
7 5 717
5 6 316
2 1 501
10
6 1 950
6 1 493
1 6 308
3 4 298
2 5 518
1 5 402
4 7 625
7 6 124
3 8 166
2 4 708

[出力例]
13649
12878
11954
11954
11280
11058
11058
8099
8099
8099
※AtCoderテストケースより

[入力例]
10 12
2 1 30
2 8 33
2 10 37
10 8 32
10 9 25
8 9 41
9 3 72
3 4 111
6 4 55
6 7 123
5 6 210
5 1 108
10
5 1 100
5 6 222
5 7 321
4 9 170
8 3 111
5 2 123
2 6 333
8 4 210
5 4 234
8 6 345

[出力例]
8338
8338
8314
8145
8143
8108
8108
8105
8074
8074

[入力例]

4 3

1 2 1

2 3 1

3 4 10

3 4 1

1 4 1

[出力例]

※AtCoderテストケースより

[入力例]

8 16

8 7 38

2 8 142

5 2 722

8 6 779

4 6 820

1 3 316

1 7 417

8 3 41

1 4 801

3 2 126

4 2 71

8 4 738

4 3 336

7 5 717

5 6 316

2 1 501

6 1 950

6 1 493

1 6 308

3 4 298

2 5 518

1 5 402

4 7 625

7 6 124

3 8 166

2 4 708

[出力例]

13649

12878

11954

11280

11058

8099

※AtCoderテストケースより

[入力例]

10 12

2 1 30

2 8 33

2 10 37

10 8 32

10 9 25

8 9 41

9 3 72

3 4 111

6 4 55

6 7 123

5 6 210

5 1 108

5 1 100

5 6 222

5 7 321

4 9 170

8 3 111

5 2 123

2 6 333

8 4 210

5 4 234

8 6 345

[出力例]

8338

8314

8145

8143

8108

8105

8074

■参照サイト
AtCoder Regular Contest 035

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

C++の練習を兼ねて, AtCoder Beginner Contest 140 の 問題F (Many Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 137 の 問題A (Coprime Pair) ～ 問題B (Count 1’s) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題C (最高のトッピングにしような) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の 問題C (ウサギとカメ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の 問題C (だれじゃ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の 問題C (増築王高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の 問題C (高橋君と国家) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の 問題C (アットコーダー王国の交通事情) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 140 の問題F (Many Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題A (Coprime Pair) ～問題B (Count 1’s) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題C (最高のトッピングにしような) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題C (だれじゃ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題C (増築王高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題C (高橋君と国家) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題C (アットコーダー王国の交通事情) を解いてみた.