C++ | 個人用メモ帳

2021年11月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題C (Martial artist) ～問題D (Teleportation) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int memo[202020];
LL t[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int k;
        scanf("%lld %d", &t[i], &k);
        rep(j, k){
            int a;
            scanf("%d", &a);
            a--;
            G[i].pb(a);
        }
    }
    
    // 2. 技 N 習得に必要な 技 を探索.
    queue<int> q;
    memo[N - 1]++;
    for(auto &e : G[N - 1]) q.push(e), memo[e] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto &e : G[u]){
            if(!memo[e]){
                q.push(e);
                memo[e] = 1;
            }
        }
    }
    
    // 3. 必要な時間.
    LL ans = 0;
    rep(i, N) if(memo[i]) ans += t[i];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int memo[202020];

LL t[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int k;

scanf("%lld %d", &t[i], &k);

rep(j, k){

int a;

scanf("%d", &a);

a--;

G[i].pb(a);

}

// 2. 技 N 習得に必要な技を探索.

queue<int> q;

memo[N - 1]++;

for(auto &e : G[N - 1]) q.push(e), memo[e] = 1;

while(!q.empty()){

int u = q.front();

q.pop();

for(auto &e : G[u]){

if(!memo[e]){

q.push(e);

memo[e] = 1;

}

// 3. 必要な時間.

LL ans = 0;

rep(i, N) if(memo[i]) ans += t[i];

// 4. 出力.

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

return 0;

}

[入力例]
3
3 0
5 1 1
7 1 1

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

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

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

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

[出力例]
27

[入力例]
20
10 0
20 1 1
75 1 1
59 2 1 3
10 2 1 2
1 2 1 2
118 4 1 2 4 5
3 1 1
95 2 5 6
1 2 8 9
88 1 10
31 2 5 7
68 3 2 4 6
22 2 10 11
76 3 1 3 5
82 5 1 5 8 13 14
89 5 2 3 8 11 13
122 1 1
5 8 1 2 4 5 9 10 11 13
29 5 1 5 10 11 16

[出力例]
563

[入力例]

3 0

5 1 1

7 1 1

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 0

1000000000 4 1 2 3 4

[出力例]

5000000000

※AtCoderテストケースより

[入力例]

5 0

7 1 1

1 2 1 2

6 2 2 3

5 1 1

9 3 1 2 4

3 2 4 5

[出力例]

[入力例]

10 0

20 1 1

75 1 1

59 2 1 3

10 2 1 2

1 2 1 2

118 4 1 2 4 5

3 1 1

95 2 5 6

1 2 8 9

88 1 10

31 2 5 7

68 3 2 4 6

22 2 10 11

76 3 1 3 5

82 5 1 5 8 13 14

89 5 2 3 8 11 13

122 1 1

5 8 1 2 4 5 9 10 11 13

29 5 1 5 10 11 16

[出力例]

563

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
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--)
LL x[505], y[505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 魔法を覚える.
    set<P> st;
    rep(i, N){
        rep(j, N){
            if(i != j){
                // ベクトル(街i -> 街j).
                LL dx = x[j] - x[i];
                LL dy = y[j] - y[i];
                
                // 最大公約数で割る.
                LL g = __gcd(abs(dx), abs(dy));
                dx /= g;
                dy /= g;
                
                // 保存.
                st.insert({dx, dy});
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", st.size());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

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

LL x[505], y[505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld", &x[i], &y[i]);

// 2. 魔法を覚える.

set<P> st;

rep(i, N){

rep(j, N){

if(i != j){

// ベクトル(街i -> 街j).

LL dx = x[j] - x[i];

LL dy = y[j] - y[i];

// 最大公約数で割る.

LL g = __gcd(abs(dx), abs(dy));

dx /= g;

dy /= g;

// 保存.

st.insert({dx, dy});

}

// 3. 出力.

printf("%d\n", st.size());

return 0;

}

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

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

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

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

[入力例]
4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

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

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

[出力例]
84

[入力例]
20
15 4
1 12
2 13
10 3
24 17
23 15
17 21
7 12
16 17
3 14
22 14
5 13
3 12
4 15
21 13
17 3
5 16
20 12
6 8
19 11

[出力例]
208

[入力例]

1 2

3 6

7 4

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 2

4 2

[出力例]

※AtCoderテストケースより

[入力例]

0 0

0 1000000000

1000000000 0

1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

11 9

6 3

4 5

5 2

6 5

11 3

10 8

3 2

2 12

2 2

11 5

8 7

[出力例]

[入力例]

15 4

1 12

2 13

10 3

24 17

23 15

17 21

7 12

16 17

3 14

22 14

5 13

3 12

4 15

21 13

17 3

5 16

20 12

6 8

19 11

[出力例]

208

■参照サイト
AtCoder Beginner Contest 226

2021年11月8日2021年11月8日

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

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題L (K番目の絶対値) を解いてみた.

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

本家のサイト第八回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202109-open/editorial/2398
// 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[303030], b[303030];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 数列 R.
    rep(i, N) b[i + 1] = b[i] + a[i];
    
    // 3. sort.
    sort(b, b + N + 1);
    
    // 4. 評価関数.
    auto f = [&](LL x) -> bool {
        // 4-1. 尺取り法(x以下となる個数).
        int l = 0, r = 0;
        LL ret = 0;
        while(l <= N){
            while(r <= N){
                // インクリメント.
                if(b[r] - b[l] <= x) r++;
                else                 break;
            }
            
            // カウントアップ.
            ret += (r - l - 1);
            
            // インクリメント.
            l++;
        }
        
        // 4-2. 判定結果.
        return (ret >= K);
    };
    
    // 5. 二分探索で確認してみる.
    LL l = -1, h = 6e14 + 1, m;
    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);
    }
    
    // 6. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202109-open/editorial/2398

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

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 数列 R.

rep(i, N) b[i + 1] = b[i] + a[i];

// 3. sort.

sort(b, b + N + 1);

// 4. 評価関数.

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

// 4-1. 尺取り法(x以下となる個数).

int l = 0, r = 0;

LL ret = 0;

while(l <= N){

while(r <= N){

// インクリメント.

if(b[r] - b[l] <= x) r++;

else break;

}

// カウントアップ.

ret += (r - l - 1);

// インクリメント.

l++;

}

// 4-2. 判定結果.

return (ret >= K);

};

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

LL l = -1, h = 6e14 + 1, m;

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

}

// 6. 出力.

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

return 0;

}

[入力例]
2 2
2 -3

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

[入力例]
5 10
1000000000 1000000000 1000000000 1000000000 1000000000

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

[入力例]
7 22
3 -1 4 -1 5 -9 2

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

[入力例]
15 33
32 89 -114 7 11 70 -30 92 103 87 -102 87 -61 -54 105

[出力例]
63

[入力例]
31 415
926 -53 -589 79 323 84 626 -43 38 -327 950 28 -841 971 69 -399 375 105 820 -97 494 459 230 -781 -640 628 -620 89 -986 280 348

[出力例]
2198

[入力例]
100 2021
102159 -114672 -107217 36327 -30669 83426 100571 -107216 34635 49074 6480 69233 -20769 49179 77058 32784 3814 49473 108653 111466 -101954 74824 94331 1096 37935 14938 56747 37252 78588 -59162 16030 -119391 -112213 64159 -20735 -71260 84542 82010 24428 -108375 21886 97121 58639 -7085 4652 55226 84540 -74340 74777 33412 115085 45328 12828 81365 57887 -101089 114624 -123313 112767 16693 30257 17764 99508 53818 68003 90477 -101189 -84645 110629 79772 93927 23542 71964 -2518 114356 121609 -3079 66812 62063 79294 102395 -88583 93473 71863 25654 54837 53117 -24088 85838 -101354 -10345 67201 -117253 86515 39071 -101652 -32421 -123185 32292 75329

[出力例]
658798

[入力例]
1000 202020
-509 751 86 935 -1048 510 225 -29 -1080 -1050 -740 513 -1137 -402 29 293 915 -895 -351 -497 480 959 230 1221 -453 1125 137 1060 -1019 557 -930 628 36 178 258 842 278 -355 621 534 -199 -162 -136 -5 76 905 695 -1158 633 1178 634 -1207 921 641 409 639 1086 254 1177 -426 -1093 -520 300 1085 1034 -413 -863 71 -608 -542 958 -248 -446 -32 -95 645 -499 -69 921 946 -1231 -279 265 857 112 -262 -1193 189 -1076 556 925 -834 -90 -392 444 758 -973 425 -565 212 -187 -254 947 -590 -221 177 782 -990 600 434 596 596 -406 -753 936 -573 160 1072 43 450 -1217 -659 540 -1097 954 642 121 819 1178 962 891 951 -371 -792 790 370 -248 -320 716 -37 -830 -279 776 -234 621 997 -385 625 526 310 646 943 -910 27 186 -798 770 -1077 656 -481 889 968 -302 -30 -171 -978 804 479 1137 875 -1176 -479 1050 1085 -279 -299 1225 47 695 -214 -647 -993 243 -613 56 127 208 -22 939 1212 -949 -271 -794 1062 765 -874 -245 -511 130 921 868 291 1082 1179 774 721 383 -464 222 -513 620 1126 -445 442 -669 -1109 1207 -246 77 -634 106 75 176 753 303 824 -541 -881 -416 953 -1083 982 907 115 -1036 326 -910 -862 965 -128 989 -236 -450 -55 39 199 92 363 948 526 771 1172 939 239 -1086 39 1136 -1186 312 14 788 207 1028 80 1135 -1138 -279 104 425 52 -393 766 714 849 898 703 289 279 245 -646 879 -799 -1052 -799 95 5 106 532 666 708 -1171 -668 -1155 -814 18 -222 -747 -198 1006 260 -232 -337 214 -865 897 494 422 -1215 491 976 933 1196 -463 995 794 395 -1075 1106 1173 1046 33 -714 -950 -784 1010 -1053 537 138 -699 -492 -514 1173 625 1233 -687 -374 149 250 -903 207 1031 905 -686 471 -738 780 610 -78 586 -736 -966 -1133 -940 1221 708 1103 1057 154 916 831 673 -782 1094 -1128 182 -208 1215 -342 412 560 -182 -1188 546 1095 -890 -177 876 -99 1146 852 916 -67 1109 618 147 12 600 1222 -113 857 685 -180 -575 366 673 202 736 -241 430 -1201 1216 189 664 -626 -273 -21 -871 74 484 -1195 567 1162 1120 -662 1003 709 547 917 -859 -574 -507 867 -242 964 723 -435 734 727 14 1230 442 712 -972 -75 -25 653 810 -589 -495 1180 0 821 1076 53 -447 -507 741 -980 1003 1158 -88 732 1183 470 -346 -72 555 36 87 1196 -1215 -1207 1115 662 377 238 192 -452 542 -1183 747 711 9 300 -1037 248 -1189 762 975 -419 1184 -745 828 287 788 -153 749 -40 -1192 508 1013 1180 -409 -9 -1136 -510 451 79 995 124 -512 -656 -984 870 -616 246 -485 751 306 550 -548 -4 274 -403 210 843 81 -66 292 1126 216 740 27 -495 1181 1095 -719 211 1101 634 -1047 -1062 841 410 4 -255 -33 1076 616 109 247 136 -150 -1210 -707 1145 865 48 1195 -901 148 474 -1208 1025 -1176 -462 827 1051 343 275 -937 605 -921 984 139 503 598 792 117 1054 147 -729 404 -508 -231 -942 556 -384 -790 956 723 1203 457 -500 877 969 -681 429 -95 -699 607 -726 -1149 115 816 -1177 -576 477 -38 344 261 1169 -493 907 944 -487 948 1007 -1216 183 1101 -573 -502 -1172 644 -539 634 769 -871 -989 -474 271 -1006 1214 -83 0 0 924 235 816 991 627 1088 -17 514 870 -115 1107 770 -609 170 723 1116 -1103 472 -769 -309 710 744 -208 547 1029 898 -625 -1026 -1011 -738 -330 -538 -792 -895 -995 1228 -136 282 -1189 -682 34 56 1081 346 662 -895 -404 105 -399 1054 881 -1117 855 125 487 584 -881 -540 -1185 681 37 338 991 366 -1106 -865 281 -721 250 -121 -553 1107 -469 849 -375 155 -871 397 178 -380 859 -950 -186 1033 887 979 228 528 188 -520 -206 -1049 -577 787 69 -1198 -374 -974 -869 358 675 574 -1122 -889 1041 421 -552 500 913 439 442 -374 874 -549 1187 1203 28 1178 -273 1190 -1195 -1188 419 -152 480 822 -1071 -802 349 -773 477 -403 1100 -1186 -132 11 -538 -1190 1116 -1217 45 1002 416 -1160 428 727 668 -969 -828 19 1148 135 484 502 11 -827 31 579 547 80 -682 637 786 1214 433 -882 733 -125 398 -174 930 678 144 -300 694 822 -193 -88 -423 121 755 -734 922 1015 887 759 -838 -760 147 1020 918 -765 -635 556 393 -1112 -1108 156 -955 670 425 1066 364 153 -191 993 15 163 -1077 -1020 575 1134 570 266 -408 -976 573 -107 -871 -405 619 -1227 479 -1220 122 -44 608 136 1027 854 -912 -375 7 107 586 846 0 -393 271 648 88 -298 60 -221 -342 -267 777 199 179 -855 -1123 -372 -608 -6 496 866 -176 608 -451 -1102 1008 1044 84 -332 215 -448 415 -322 599 -794 -167 1225 1129 42 -200 -428 331 -133 1169 1084 355 -664 -243 910 327 506 -614 990 -1173 -1102 839 -468 688 -632 323 137 -1198 -722 767 1186 80 404 189 674 -993 1220 1049 -790 538 -800 919 -1005 -854 308 669 642 633 427 -925 537 1082 1006 -484 200 355 287 -883 229 387 510 620 -541 -1016 -753 1059 -950 386 -683 869 811 823 474 6 -397 -1033 153 729 396 303 190 975 -337 -129 -803 -656 172 -299 30 212 501 -370 -76 -816 252 1020 936 946 609 464 662 0 -244 -577

[出力例]
25901

[入力例]
2000 777777
111718 48853 -70944 45179 -24450 85276 -109356 120321 -2819 -116431 59046 -85212 -82495 117451 -96884 -41741 31206 88482 56390 21518 65966 73825 69036 35329 112576 -97079 75466 116324 83112 -104166 45721 -48126 16354 114788 62269 -27975 -30075 107628 86164 19695 -31927 -53113 37380 17625 36363 57322 94613 103444 48753 82053 62365 48139 -34706 115293 90210 86999 119131 30451 93971 66422 39935 123019 76172 -86911 -43655 -28306 -37248 -78074 35080 -372 -52475 -73621 -81818 20473 -22554 101405 47506 91229 -103835 35000 92228 20196 11545 -73619 27456 -100519 24198 -81057 5048 27623 -86562 -63610 16641 33606 -1615 51332 13357 43226 -38077 -31730 41439 -112525 -6193 111338 84580 -79143 58252 -26998 102637 106285 -91216 48007 -36022 -109928 47415 105768 73892 42319 112923 64593 -100568 990 -110500 65579 -29296 -97174 -111989 12287 -9139 49952 64274 54766 -114428 64153 -112395 103523 -109715 103083 111887 2944 -45370 56906 43172 94901 60156 82056 12246 25942 8117 -58881 904 97108 29285 85079 -30628 62112 87050 29519 -86088 -41791 64026 -87450 -103391 46399 87 -80582 106517 104961 -16902 8909 -101797 20375 -60332 -67031 -121263 41983 -62454 75202 50602 42104 64429 75827 -44951 106659 -54616 -45338 -113952 -1974 23246 48495 -70859 55043 121593 50071 -112333 -11524 74912 49038 -83259 33440 -25754 -75607 20440 10869 107915 29559 -71555 -13185 77967 -76311 40926 121938 63277 53109 -47895 -75522 -56071 100421 50649 15992 109052 66867 17355 -71269 -93149 90208 104861 87419 24259 -54250 -39812 118670 98152 -3893 119579 93087 -108729 -101896 -14004 92218 86324 -74933 95274 10688 106110 21005 -98692 16594 -35680 60657 65307 23148 12641 18041 -29137 81884 43459 108279 112740 106591 -68286 109999 41213 -36819 26786 39565 77665 -121081 -19953 110934 -63028 98570 20779 -114470 82309 -94951 107231 93260 32682 115413 46077 18016 72577 15855 105647 107160 18284 38184 -91555 -34326 93372 -116699 81961 -116742 -101878 17333 71100 -6093 42546 55474 22946 85500 50746 -66761 103319 104645 105074 51124 58895 49438 53002 102142 -113565 6157 -113407 120922 107943 123149 117850 -114556 94153 3194 -67494 11854 33332 -118778 -51792 74372 -82311 -29593 35321 -100637 -120701 96796 1257 2915 -44850 51152 79166 30959 63135 16130 55377 -53223 119445 13972 72973 67532 110894 36964 -60644 114431 33648 103465 -36965 -38110 30374 -23660 -111526 -43249 11578 86845 79321 -97678 60758 59164 89557 15436 -72982 -19203 -32110 100098 -70836 -92065 102689 -122050 47417 -25837 57768 -80614 85332 19610 70690 45508 73417 -112157 -79379 -67160 33672 6207 55124 60869 -86093 15753 2232 72102 -16320 -66695 41394 -65 15645 105103 18923 -87245 -59571 -82877 38111 2980 29980 98842 40451 105963 -60510 65659 -641 99723 55734 77838 73092 15077 8165 70668 102267 -117745 -83398 -83711 40879 -74812 -104496 -105708 23574 26712 86573 96930 52356 39479 112740 67575 117735 91293 312 -41615 30308 88807 57366 -86011 -98350 107518 -73312 -47574 5773 73861 5003 120032 -9602 39249 3008 83256 123276 -9869 -34350 41263 -63904 59400 44822 92087 76823 84310 85447 122765 -6692 73772 43041 -27053 112730 49404 82837 -16394 -30184 55481 -1811 83609 47162 83264 70567 -15264 -14205 107529 51486 114551 56994 -83681 -37364 67242 -7535 -109681 -98768 42770 109814 -121938 -118905 18192 -17095 115687 32596 -17350 115515 6537 85509 -47937 73963 -7978 -10836 -10949 -73367 97968 67237 -108887 43555 18161 -12452 66100 93144 115523 17565 104435 87572 -7301 2829 24 93876 57143 -98167 119650 4438 37809 75400 95058 -60708 -80850 26727 -56752 -93281 -35631 12509 -31981 -55057 -76074 -61792 -100389 68954 76623 39386 -52151 -13626 87992 36256 -67116 -1731 -39714 15829 -92701 -36615 53169 43500 52645 -55404 -105736 62864 -119549 21243 -87500 121259 -55592 -22295 33996 -30720 -42361 17334 27886 32663 -122322 -72984 44174 -63 -57016 64953 107051 -24404 -25384 -41389 57735 -59759 51247 -48161 24668 59346 -29648 -701 11559 2337 100740 35402 98919 -61693 80337 -38000 -32691 66200 60498 -109017 54498 70454 -99984 -80848 119375 13078 46755 -10486 -92667 -40085 60412 -32863 13862 70143 -51212 -104639 -104656 -52336 -14495 101735 -36589 -39115 14521 -97421 -44077 4837 65416 -97303 -100309 44089 5060 -113037 60901 44510 -6066 122427 92461 78739 -57685 54338 99582 12956 45167 95864 102281 59741 -101862 -2536 -18158 -9698 73521 14152 77406 33882 72973 23742 101438 27089 -112869 -5233 -110073 90795 -78452 -119751 25730 98453 109164 -91778 69751 115964 -36295 77566 53222 -29787 -59671 75117 17458 -46713 -66267 97159 -2140 96538 -12071 -70673 66480 52555 42267 18007 74783 -17613 110818 30986 -113535 80602 14681 100823 -79150 -103817 -3081 3032 45737 97873 56703 -41070 14043 78169 -23170 -113406 100129 65410 43774 86455 -44998 -26452 -103217 -94001 -118709 85740 84797 65511 -39806 -35998 65823 -38818 83049 -68830 -83054 25363 -109058 42230 -13049 31718 -57656 83562 74024 120328 65904 77166 41949 106460 -17897 -21559 22285 58974 -34085 -19242 123017 3017 61440 114294 -29128 28899 108055 -50111 55303 35969 -18151 31588 -74964 98011 -20204 49078 -96211 -21391 99353 119446 25960 29666 36061 79533 55918 -70565 76692 122009 20879 83711 -35776 27614 120709 25617 62332 122239 108711 75043 93608 83061 20933 85547 2506 10306 31649 86146 44610 -25767 17370 -95770 120529 -74530 36813 98098 115375 -47060 100892 -105477 42111 11892 -93840 26637 95232 14335 -43481 17103 -106857 95012 -105688 79481 -29905 22764 20294 48215 80687 -116344 -79391 60620 95084 103214 -84434 121832 15485 63052 -92451 -44886 839 104638 -118693 81834 37326 64899 -42941 62386 117706 -83817 113582 9109 122109 12824 119403 61690 -30163 -29622 74690 4478 -99951 117493 -11696 17611 92353 4813 -17473 66182 114345 15939 -66350 35456 -107836 101929 10300 119865 40904 -38404 54601 -75724 87704 -14772 5494 -97957 44993 61131 -24281 94735 40132 12077 68883 80871 104548 104801 43346 22402 84253 82485 60905 -93385 173 10326 -44765 74539 86390 93558 92089 -105980 118162 -117504 86362 -60054 -6898 108585 1647 54953 51744 56021 68047 56707 -122346 101509 -51355 35863 75328 -35080 30531 -30151 11087 -95055 -60860 92385 -31169 250 93456 -100307 -36597 -94398 85354 42829 72261 -1357 -80342 -82195 2406 34022 -116418 65322 36400 5771 96195 -110128 71024 -1342 74030 45181 -7449 -91502 68791 -13851 22910 64362 75649 -13790 -102618 -9056 -22814 9135 100342 104713 -118787 -79959 75890 96055 107182 7798 93712 11009 -13924 -117961 88324 -30284 20364 72470 -104422 107392 -35360 60057 92631 89618 -43245 74814 19105 -119343 45229 -47666 82507 39088 54341 121929 -117102 82821 10109 -118514 -46717 -55202 -83108 -54977 63910 -27099 -45689 27339 70310 82727 75510 95791 44843 3603 29458 71867 -14328 -5655 -89762 -48980 -84502 64855 89249 2137 68469 -40565 67119 -27335 12698 43256 -5144 119769 -45541 111373 -70757 48467 -104302 -35349 -12414 -8109 -96411 103032 19332 107044 106582 111142 119787 -6779 -57685 -97960 58296 44746 -11927 39740 68629 6132 23120 13136 -76815 -71529 4054 90148 50558 -93060 10080 88419 24725 79666 62057 -96335 -16510 83602 -85819 -32133 9452 63297 -100039 115750 46320 -36892 54759 71868 7663 107225 -21660 -94893 3391 121318 56322 -95811 9616 86909 116219 -41504 107800 -29894 69750 -109418 38566 4307 39644 -103215 119630 -7568 -1780 -56703 8380 -41962 106836 25920 76790 -42782 -17834 -37286 39438 -76857 -102099 81985 113702 -14970 -6971 78210 3493 111390 30135 -21635 36197 -62917 35088 -70925 -17804 -68123 -68547 58657 45081 64410 72615 -90315 67183 -26525 47492 96270 8837 122908 43622 70558 -87635 -86054 -30271 -98005 -5961 -75645 56253 106526 -7891 101338 -71712 102067 31232 -33062 -11382 7578 -34194 76266 -87824 72094 84383 118681 -114901 57526 44450 89588 513 -97100 85006 102760 7034 -33223 101639 -4657 19592 103418 60594 122525 103906 79032 114706 3067 -102813 -71536 81760 -56484 44393 -95423 6033 60948 -28051 -112287 106734 -27094 97336 107726 -11223 82730 110686 -2715 -99188 95612 92653 -56505 -50612 -1867 39104 38246 3902 92449 -85799 119149 19758 68074 99422 -94649 -110166 -24661 111876 -96016 -115474 -52937 67591 -68227 -121847 -100440 102024 28973 40113 -28666 -38244 76780 -49586 120382 102639 62432 5372 -6593 -60296 66134 -108036 96595 20761 3791 -33723 25001 111794 101990 -115003 116245 84810 92006 88897 -116163 77265 21327 22795 101094 55368 114341 30135 -117626 94269 95613 -13907 -70551 28741 -3486 -48560 -1943 -21253 82930 -94840 85447 -71657 105955 -104915 -55691 -91620 -11009 -112557 100876 1287 15725 4766 66801 -65910 32771 -98372 -30284 -6628 67873 -68587 86368 53944 -70131 51013 107769 68891 -40000 -3233 -24324 96846 75054 98860 91819 39046 -45137 102656 -21914 -78657 -74417 46854 5200 -23053 -56177 -45726 684 53250 40803 26562 44546 -75976 -39917 38414 -57595 -1138 111654 110865 -97181 -110652 -33506 -14171 94357 52533 -93615 -115592 -114679 -43370 99250 63650 118088 -23835 -19286 86653 -20627 69729 58614 56133 -76089 116882 13886 8156 12343 107930 121441 -79006 35519 -117403 -25703 60293 -100518 -119156 -41241 64235 39087 31847 -38299 -20967 -85539 47066 108202 -72933 120187 70276 29606 77407 -117134 34005 -67448 59058 82518 36668 -42147 3492 102949 120083 113191 -50154 6237 26028 19857 -52477 -31099 86860 39912 122884 79286 37098 -19553 59356 26518 -78613 88837 -121051 -29231 -19916 92035 41033 28658 94972 68099 44997 -29794 -51101 -5738 32660 -122596 77479 16316 -106468 -12787 7965 99614 110786 11964 -7357 110944 117760 76869 11008 30527 84916 65824 -62276 12388 -40040 -97730 -50485 108332 -117838 -54600 2249 59546 54059 49681 -73867 -116447 13936 -106149 -23215 32506 -111261 -104029 -63370 52930 -93110 -106165 107528 -58387 11690 -115855 -79344 -32051 -22997 -93266 25622 67891 16282 11027 -47328 96598 -109126 9420 19491 81147 -49007 63205 -99850 -82993 -73160 -35085 -96911 41702 -105124 8790 21512 25014 -105555 -110176 50341 -86573 52695 -106137 29605 -86570 -34619 98063 29406 31556 57456 85157 86298 -76043 -110968 27080 -52355 -72077 33767 72734 103353 -54193 -29985 -122532 4129 1155 23539 -98256 42644 -42193 96023 53905 -631 122668 61008 -117687 -36699 118289 43043 -84727 45884 62477 114538 8340 108366 -81703 85255 -55245 -19058 66038 32991 71812 -69277 -64229 -48722 47619 -52120 -111969 118035 49565 30062 85936 13353 -88313 79721 97357 -47821 -18184 -14350 49465 -73449 100477 -40931 46002 -40153 -115984 118245 10708 8761 16100 63563 -103839 28238 16080 36772 -27271 59976 -52235 43627 39017 -99342 -30771 117029 -104775 -106162 -65586 -10612 114148 28061 -56525 111689 -76075 -262 -20854 112100 -120357 98862 86304 53818 122368 93333 117517 -25288 -96626 -74077 41112 -29859 96372 1539 -67830 -29243 -10545 43067 123243 676 65429 97311 103696 16431 -103309 111648 41397 86015 -70966 -28974 -56069 5321 58848 53298 -60949 104956 -102189 -112320 86178 57471 -29674 82409 21002 89775 -81026 103778 -101119 -16237 105248 56770 -8208 -64352 -103095 70072 -57320 -64578 31261 120315 -85181 92628 87957 68572 33597 -12477 41247 -30530 -24902 -61364 25098 83502 2039 46001 -82100 50985 -47397 52102 40804 9079 -2391 -24150 74260 108326 92979 37758 117234 46945 -57372 65924 97037 9600 53338 101907 17313 -104169 -116339 -55005 100440 -13320 -99520 -20550 -109671 22973 84471 -29284 -90713 81807 44496 74726 -80488 44262 -35419 10749 84198 -84635 -18537 121146 108312 16690 115729 75536 65098 -25702 20964 -58631 -36271 -27879 -63030 16369 97462 89703 88274 -56502 47327 112962 -83995 94413 66095 -55522 105439 70506 -60497 80590 -86778 49396 21681 -1986 -56646 -32013 -73698 32509 112698 -53210 41595 31783 -87208 18544 -99088 -95043 74001 17337 59237 -39970 82828 -58215 -24018 82698 -57250 43736 17996 118452 -18792 111876 35066 19558 9540 116823 -53620 -33933 -123264 68243 -83442 72639 54539 72349 30048 109637 -55025 115994 -78569 65374 -77960 28921 28962 -13860 63406 -72914 -25786 -36633 -11246 112430 -102753 -44516 35593 57856 -67749 -87727 42855 58034 18820 -93372 61681 -49382 -48058 -66576 -116236 57005 90325 -72292 95823 -16381 111073 -109036 60855 -117437 -14912 -3090 99335 109857 -83343 15860 -89119 -29245 -97079 53745 80436 114278 121048 109258 85245 -22454 -72468 95963 -95071 30494 76640 46560 53533 17441 42242 63288 93333 44190 44587 -72904 50403 15933 -35106 -36433 83136 -23432 -79990 -111083 -89483 110361 -41190 -19603 -28061 102033 -40272 -95211 64721 -68712 55248 109488 73625 -43160 115 40849 -8155 23886 -83633 101788 -7186 112227 -60 33837 -48880 25585 94165 -105556 25721 48749 122946 33362 -63329 43383 34533 43504 23976 77775 -31988 30654 105623 79052 55905 -45020 122110 -20870 -25686 106278 -29222 45524 -98108 90603 -73719 -42109 1010 39585 -85549 -72605 -112017 -32665 3435 -5990 77317 -58124 -79916 39689 -107173 -116720 -32521 -9845 83939 115856 99113 -25589 5338 -47278 -47200 -55249 108093 -42169 -34153 114984 99523 3520 21892 16646 8131 70296 100426 -92742 -43561 -110236 -45505 -63914 36917 -98372 67957 -111126 18722 -117518 36503 106131 -51912 -23641 -21071 -80800 37285 -44029 -121691 -117986 89100 -93976 111679 68073 103870 -54110 21164 -104843 60747 -54196 6525 -17826 -41814 118298 17325 26051 -6307 15024 23489 -14666

[出力例]
5616244

[入力例]

2 2

2 -3

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

1000000000 1000000000 1000000000 1000000000 1000000000

[出力例]

3000000000

※AtCoderのテストケースより

[入力例]

7 22

3 -1 4 -1 5 -9 2

[出力例]

※AtCoderのテストケースより

[入力例]

15 33

32 89 -114 7 11 70 -30 92 103 87 -102 87 -61 -54 105

[出力例]

[入力例]

31 415

926 -53 -589 79 323 84 626 -43 38 -327 950 28 -841 971 69 -399 375 105 820 -97 494 459 230 -781 -640 628 -620 89 -986 280 348

[出力例]

2198

[入力例]

100 2021

102159 -114672 -107217 36327 -30669 83426 100571 -107216 34635 49074 6480 69233 -20769 49179 77058 32784 3814 49473 108653 111466 -101954 74824 94331 1096 37935 14938 56747 37252 78588 -59162 16030 -119391 -112213 64159 -20735 -71260 84542 82010 24428 -108375 21886 97121 58639 -7085 4652 55226 84540 -74340 74777 33412 115085 45328 12828 81365 57887 -101089 114624 -123313 112767 16693 30257 17764 99508 53818 68003 90477 -101189 -84645 110629 79772 93927 23542 71964 -2518 114356 121609 -3079 66812 62063 79294 102395 -88583 93473 71863 25654 54837 53117 -24088 85838 -101354 -10345 67201 -117253 86515 39071 -101652 -32421 -123185 32292 75329

[出力例]

658798

[入力例]

1000 202020

-509 751 86 935 -1048 510 225 -29 -1080 -1050 -740 513 -1137 -402 29 293 915 -895 -351 -497 480 959 230 1221 -453 1125 137 1060 -1019 557 -930 628 36 178 258 842 278 -355 621 534 -199 -162 -136 -5 76 905 695 -1158 633 1178 634 -1207 921 641 409 639 1086 254 1177 -426 -1093 -520 300 1085 1034 -413 -863 71 -608 -542 958 -248 -446 -32 -95 645 -499 -69 921 946 -1231 -279 265 857 112 -262 -1193 189 -1076 556 925 -834 -90 -392 444 758 -973 425 -565 212 -187 -254 947 -590 -221 177 782 -990 600 434 596 596 -406 -753 936 -573 160 1072 43 450 -1217 -659 540 -1097 954 642 121 819 1178 962 891 951 -371 -792 790 370 -248 -320 716 -37 -830 -279 776 -234 621 997 -385 625 526 310 646 943 -910 27 186 -798 770 -1077 656 -481 889 968 -302 -30 -171 -978 804 479 1137 875 -1176 -479 1050 1085 -279 -299 1225 47 695 -214 -647 -993 243 -613 56 127 208 -22 939 1212 -949 -271 -794 1062 765 -874 -245 -511 130 921 868 291 1082 1179 774 721 383 -464 222 -513 620 1126 -445 442 -669 -1109 1207 -246 77 -634 106 75 176 753 303 824 -541 -881 -416 953 -1083 982 907 115 -1036 326 -910 -862 965 -128 989 -236 -450 -55 39 199 92 363 948 526 771 1172 939 239 -1086 39 1136 -1186 312 14 788 207 1028 80 1135 -1138 -279 104 425 52 -393 766 714 849 898 703 289 279 245 -646 879 -799 -1052 -799 95 5 106 532 666 708 -1171 -668 -1155 -814 18 -222 -747 -198 1006 260 -232 -337 214 -865 897 494 422 -1215 491 976 933 1196 -463 995 794 395 -1075 1106 1173 1046 33 -714 -950 -784 1010 -1053 537 138 -699 -492 -514 1173 625 1233 -687 -374 149 250 -903 207 1031 905 -686 471 -738 780 610 -78 586 -736 -966 -1133 -940 1221 708 1103 1057 154 916 831 673 -782 1094 -1128 182 -208 1215 -342 412 560 -182 -1188 546 1095 -890 -177 876 -99 1146 852 916 -67 1109 618 147 12 600 1222 -113 857 685 -180 -575 366 673 202 736 -241 430 -1201 1216 189 664 -626 -273 -21 -871 74 484 -1195 567 1162 1120 -662 1003 709 547 917 -859 -574 -507 867 -242 964 723 -435 734 727 14 1230 442 712 -972 -75 -25 653 810 -589 -495 1180 0 821 1076 53 -447 -507 741 -980 1003 1158 -88 732 1183 470 -346 -72 555 36 87 1196 -1215 -1207 1115 662 377 238 192 -452 542 -1183 747 711 9 300 -1037 248 -1189 762 975 -419 1184 -745 828 287 788 -153 749 -40 -1192 508 1013 1180 -409 -9 -1136 -510 451 79 995 124 -512 -656 -984 870 -616 246 -485 751 306 550 -548 -4 274 -403 210 843 81 -66 292 1126 216 740 27 -495 1181 1095 -719 211 1101 634 -1047 -1062 841 410 4 -255 -33 1076 616 109 247 136 -150 -1210 -707 1145 865 48 1195 -901 148 474 -1208 1025 -1176 -462 827 1051 343 275 -937 605 -921 984 139 503 598 792 117 1054 147 -729 404 -508 -231 -942 556 -384 -790 956 723 1203 457 -500 877 969 -681 429 -95 -699 607 -726 -1149 115 816 -1177 -576 477 -38 344 261 1169 -493 907 944 -487 948 1007 -1216 183 1101 -573 -502 -1172 644 -539 634 769 -871 -989 -474 271 -1006 1214 -83 0 0 924 235 816 991 627 1088 -17 514 870 -115 1107 770 -609 170 723 1116 -1103 472 -769 -309 710 744 -208 547 1029 898 -625 -1026 -1011 -738 -330 -538 -792 -895 -995 1228 -136 282 -1189 -682 34 56 1081 346 662 -895 -404 105 -399 1054 881 -1117 855 125 487 584 -881 -540 -1185 681 37 338 991 366 -1106 -865 281 -721 250 -121 -553 1107 -469 849 -375 155 -871 397 178 -380 859 -950 -186 1033 887 979 228 528 188 -520 -206 -1049 -577 787 69 -1198 -374 -974 -869 358 675 574 -1122 -889 1041 421 -552 500 913 439 442 -374 874 -549 1187 1203 28 1178 -273 1190 -1195 -1188 419 -152 480 822 -1071 -802 349 -773 477 -403 1100 -1186 -132 11 -538 -1190 1116 -1217 45 1002 416 -1160 428 727 668 -969 -828 19 1148 135 484 502 11 -827 31 579 547 80 -682 637 786 1214 433 -882 733 -125 398 -174 930 678 144 -300 694 822 -193 -88 -423 121 755 -734 922 1015 887 759 -838 -760 147 1020 918 -765 -635 556 393 -1112 -1108 156 -955 670 425 1066 364 153 -191 993 15 163 -1077 -1020 575 1134 570 266 -408 -976 573 -107 -871 -405 619 -1227 479 -1220 122 -44 608 136 1027 854 -912 -375 7 107 586 846 0 -393 271 648 88 -298 60 -221 -342 -267 777 199 179 -855 -1123 -372 -608 -6 496 866 -176 608 -451 -1102 1008 1044 84 -332 215 -448 415 -322 599 -794 -167 1225 1129 42 -200 -428 331 -133 1169 1084 355 -664 -243 910 327 506 -614 990 -1173 -1102 839 -468 688 -632 323 137 -1198 -722 767 1186 80 404 189 674 -993 1220 1049 -790 538 -800 919 -1005 -854 308 669 642 633 427 -925 537 1082 1006 -484 200 355 287 -883 229 387 510 620 -541 -1016 -753 1059 -950 386 -683 869 811 823 474 6 -397 -1033 153 729 396 303 190 975 -337 -129 -803 -656 172 -299 30 212 501 -370 -76 -816 252 1020 936 946 609 464 662 0 -244 -577

[出力例]

25901

[入力例]

2000 777777

111718 48853 -70944 45179 -24450 85276 -109356 120321 -2819 -116431 59046 -85212 -82495 117451 -96884 -41741 31206 88482 56390 21518 65966 73825 69036 35329 112576 -97079 75466 116324 83112 -104166 45721 -48126 16354 114788 62269 -27975 -30075 107628 86164 19695 -31927 -53113 37380 17625 36363 57322 94613 103444 48753 82053 62365 48139 -34706 115293 90210 86999 119131 30451 93971 66422 39935 123019 76172 -86911 -43655 -28306 -37248 -78074 35080 -372 -52475 -73621 -81818 20473 -22554 101405 47506 91229 -103835 35000 92228 20196 11545 -73619 27456 -100519 24198 -81057 5048 27623 -86562 -63610 16641 33606 -1615 51332 13357 43226 -38077 -31730 41439 -112525 -6193 111338 84580 -79143 58252 -26998 102637 106285 -91216 48007 -36022 -109928 47415 105768 73892 42319 112923 64593 -100568 990 -110500 65579 -29296 -97174 -111989 12287 -9139 49952 64274 54766 -114428 64153 -112395 103523 -109715 103083 111887 2944 -45370 56906 43172 94901 60156 82056 12246 25942 8117 -58881 904 97108 29285 85079 -30628 62112 87050 29519 -86088 -41791 64026 -87450 -103391 46399 87 -80582 106517 104961 -16902 8909 -101797 20375 -60332 -67031 -121263 41983 -62454 75202 50602 42104 64429 75827 -44951 106659 -54616 -45338 -113952 -1974 23246 48495 -70859 55043 121593 50071 -112333 -11524 74912 49038 -83259 33440 -25754 -75607 20440 10869 107915 29559 -71555 -13185 77967 -76311 40926 121938 63277 53109 -47895 -75522 -56071 100421 50649 15992 109052 66867 17355 -71269 -93149 90208 104861 87419 24259 -54250 -39812 118670 98152 -3893 119579 93087 -108729 -101896 -14004 92218 86324 -74933 95274 10688 106110 21005 -98692 16594 -35680 60657 65307 23148 12641 18041 -29137 81884 43459 108279 112740 106591 -68286 109999 41213 -36819 26786 39565 77665 -121081 -19953 110934 -63028 98570 20779 -114470 82309 -94951 107231 93260 32682 115413 46077 18016 72577 15855 105647 107160 18284 38184 -91555 -34326 93372 -116699 81961 -116742 -101878 17333 71100 -6093 42546 55474 22946 85500 50746 -66761 103319 104645 105074 51124 58895 49438 53002 102142 -113565 6157 -113407 120922 107943 123149 117850 -114556 94153 3194 -67494 11854 33332 -118778 -51792 74372 -82311 -29593 35321 -100637 -120701 96796 1257 2915 -44850 51152 79166 30959 63135 16130 55377 -53223 119445 13972 72973 67532 110894 36964 -60644 114431 33648 103465 -36965 -38110 30374 -23660 -111526 -43249 11578 86845 79321 -97678 60758 59164 89557 15436 -72982 -19203 -32110 100098 -70836 -92065 102689 -122050 47417 -25837 57768 -80614 85332 19610 70690 45508 73417 -112157 -79379 -67160 33672 6207 55124 60869 -86093 15753 2232 72102 -16320 -66695 41394 -65 15645 105103 18923 -87245 -59571 -82877 38111 2980 29980 98842 40451 105963 -60510 65659 -641 99723 55734 77838 73092 15077 8165 70668 102267 -117745 -83398 -83711 40879 -74812 -104496 -105708 23574 26712 86573 96930 52356 39479 112740 67575 117735 91293 312 -41615 30308 88807 57366 -86011 -98350 107518 -73312 -47574 5773 73861 5003 120032 -9602 39249 3008 83256 123276 -9869 -34350 41263 -63904 59400 44822 92087 76823 84310 85447 122765 -6692 73772 43041 -27053 112730 49404 82837 -16394 -30184 55481 -1811 83609 47162 83264 70567 -15264 -14205 107529 51486 114551 56994 -83681 -37364 67242 -7535 -109681 -98768 42770 109814 -121938 -118905 18192 -17095 115687 32596 -17350 115515 6537 85509 -47937 73963 -7978 -10836 -10949 -73367 97968 67237 -108887 43555 18161 -12452 66100 93144 115523 17565 104435 87572 -7301 2829 24 93876 57143 -98167 119650 4438 37809 75400 95058 -60708 -80850 26727 -56752 -93281 -35631 12509 -31981 -55057 -76074 -61792 -100389 68954 76623 39386 -52151 -13626 87992 36256 -67116 -1731 -39714 15829 -92701 -36615 53169 43500 52645 -55404 -105736 62864 -119549 21243 -87500 121259 -55592 -22295 33996 -30720 -42361 17334 27886 32663 -122322 -72984 44174 -63 -57016 64953 107051 -24404 -25384 -41389 57735 -59759 51247 -48161 24668 59346 -29648 -701 11559 2337 100740 35402 98919 -61693 80337 -38000 -32691 66200 60498 -109017 54498 70454 -99984 -80848 119375 13078 46755 -10486 -92667 -40085 60412 -32863 13862 70143 -51212 -104639 -104656 -52336 -14495 101735 -36589 -39115 14521 -97421 -44077 4837 65416 -97303 -100309 44089 5060 -113037 60901 44510 -6066 122427 92461 78739 -57685 54338 99582 12956 45167 95864 102281 59741 -101862 -2536 -18158 -9698 73521 14152 77406 33882 72973 23742 101438 27089 -112869 -5233 -110073 90795 -78452 -119751 25730 98453 109164 -91778 69751 115964 -36295 77566 53222 -29787 -59671 75117 17458 -46713 -66267 97159 -2140 96538 -12071 -70673 66480 52555 42267 18007 74783 -17613 110818 30986 -113535 80602 14681 100823 -79150 -103817 -3081 3032 45737 97873 56703 -41070 14043 78169 -23170 -113406 100129 65410 43774 86455 -44998 -26452 -103217 -94001 -118709 85740 84797 65511 -39806 -35998 65823 -38818 83049 -68830 -83054 25363 -109058 42230 -13049 31718 -57656 83562 74024 120328 65904 77166 41949 106460 -17897 -21559 22285 58974 -34085 -19242 123017 3017 61440 114294 -29128 28899 108055 -50111 55303 35969 -18151 31588 -74964 98011 -20204 49078 -96211 -21391 99353 119446 25960 29666 36061 79533 55918 -70565 76692 122009 20879 83711 -35776 27614 120709 25617 62332 122239 108711 75043 93608 83061 20933 85547 2506 10306 31649 86146 44610 -25767 17370 -95770 120529 -74530 36813 98098 115375 -47060 100892 -105477 42111 11892 -93840 26637 95232 14335 -43481 17103 -106857 95012 -105688 79481 -29905 22764 20294 48215 80687 -116344 -79391 60620 95084 103214 -84434 121832 15485 63052 -92451 -44886 839 104638 -118693 81834 37326 64899 -42941 62386 117706 -83817 113582 9109 122109 12824 119403 61690 -30163 -29622 74690 4478 -99951 117493 -11696 17611 92353 4813 -17473 66182 114345 15939 -66350 35456 -107836 101929 10300 119865 40904 -38404 54601 -75724 87704 -14772 5494 -97957 44993 61131 -24281 94735 40132 12077 68883 80871 104548 104801 43346 22402 84253 82485 60905 -93385 173 10326 -44765 74539 86390 93558 92089 -105980 118162 -117504 86362 -60054 -6898 108585 1647 54953 51744 56021 68047 56707 -122346 101509 -51355 35863 75328 -35080 30531 -30151 11087 -95055 -60860 92385 -31169 250 93456 -100307 -36597 -94398 85354 42829 72261 -1357 -80342 -82195 2406 34022 -116418 65322 36400 5771 96195 -110128 71024 -1342 74030 45181 -7449 -91502 68791 -13851 22910 64362 75649 -13790 -102618 -9056 -22814 9135 100342 104713 -118787 -79959 75890 96055 107182 7798 93712 11009 -13924 -117961 88324 -30284 20364 72470 -104422 107392 -35360 60057 92631 89618 -43245 74814 19105 -119343 45229 -47666 82507 39088 54341 121929 -117102 82821 10109 -118514 -46717 -55202 -83108 -54977 63910 -27099 -45689 27339 70310 82727 75510 95791 44843 3603 29458 71867 -14328 -5655 -89762 -48980 -84502 64855 89249 2137 68469 -40565 67119 -27335 12698 43256 -5144 119769 -45541 111373 -70757 48467 -104302 -35349 -12414 -8109 -96411 103032 19332 107044 106582 111142 119787 -6779 -57685 -97960 58296 44746 -11927 39740 68629 6132 23120 13136 -76815 -71529 4054 90148 50558 -93060 10080 88419 24725 79666 62057 -96335 -16510 83602 -85819 -32133 9452 63297 -100039 115750 46320 -36892 54759 71868 7663 107225 -21660 -94893 3391 121318 56322 -95811 9616 86909 116219 -41504 107800 -29894 69750 -109418 38566 4307 39644 -103215 119630 -7568 -1780 -56703 8380 -41962 106836 25920 76790 -42782 -17834 -37286 39438 -76857 -102099 81985 113702 -14970 -6971 78210 3493 111390 30135 -21635 36197 -62917 35088 -70925 -17804 -68123 -68547 58657 45081 64410 72615 -90315 67183 -26525 47492 96270 8837 122908 43622 70558 -87635 -86054 -30271 -98005 -5961 -75645 56253 106526 -7891 101338 -71712 102067 31232 -33062 -11382 7578 -34194 76266 -87824 72094 84383 118681 -114901 57526 44450 89588 513 -97100 85006 102760 7034 -33223 101639 -4657 19592 103418 60594 122525 103906 79032 114706 3067 -102813 -71536 81760 -56484 44393 -95423 6033 60948 -28051 -112287 106734 -27094 97336 107726 -11223 82730 110686 -2715 -99188 95612 92653 -56505 -50612 -1867 39104 38246 3902 92449 -85799 119149 19758 68074 99422 -94649 -110166 -24661 111876 -96016 -115474 -52937 67591 -68227 -121847 -100440 102024 28973 40113 -28666 -38244 76780 -49586 120382 102639 62432 5372 -6593 -60296 66134 -108036 96595 20761 3791 -33723 25001 111794 101990 -115003 116245 84810 92006 88897 -116163 77265 21327 22795 101094 55368 114341 30135 -117626 94269 95613 -13907 -70551 28741 -3486 -48560 -1943 -21253 82930 -94840 85447 -71657 105955 -104915 -55691 -91620 -11009 -112557 100876 1287 15725 4766 66801 -65910 32771 -98372 -30284 -6628 67873 -68587 86368 53944 -70131 51013 107769 68891 -40000 -3233 -24324 96846 75054 98860 91819 39046 -45137 102656 -21914 -78657 -74417 46854 5200 -23053 -56177 -45726 684 53250 40803 26562 44546 -75976 -39917 38414 -57595 -1138 111654 110865 -97181 -110652 -33506 -14171 94357 52533 -93615 -115592 -114679 -43370 99250 63650 118088 -23835 -19286 86653 -20627 69729 58614 56133 -76089 116882 13886 8156 12343 107930 121441 -79006 35519 -117403 -25703 60293 -100518 -119156 -41241 64235 39087 31847 -38299 -20967 -85539 47066 108202 -72933 120187 70276 29606 77407 -117134 34005 -67448 59058 82518 36668 -42147 3492 102949 120083 113191 -50154 6237 26028 19857 -52477 -31099 86860 39912 122884 79286 37098 -19553 59356 26518 -78613 88837 -121051 -29231 -19916 92035 41033 28658 94972 68099 44997 -29794 -51101 -5738 32660 -122596 77479 16316 -106468 -12787 7965 99614 110786 11964 -7357 110944 117760 76869 11008 30527 84916 65824 -62276 12388 -40040 -97730 -50485 108332 -117838 -54600 2249 59546 54059 49681 -73867 -116447 13936 -106149 -23215 32506 -111261 -104029 -63370 52930 -93110 -106165 107528 -58387 11690 -115855 -79344 -32051 -22997 -93266 25622 67891 16282 11027 -47328 96598 -109126 9420 19491 81147 -49007 63205 -99850 -82993 -73160 -35085 -96911 41702 -105124 8790 21512 25014 -105555 -110176 50341 -86573 52695 -106137 29605 -86570 -34619 98063 29406 31556 57456 85157 86298 -76043 -110968 27080 -52355 -72077 33767 72734 103353 -54193 -29985 -122532 4129 1155 23539 -98256 42644 -42193 96023 53905 -631 122668 61008 -117687 -36699 118289 43043 -84727 45884 62477 114538 8340 108366 -81703 85255 -55245 -19058 66038 32991 71812 -69277 -64229 -48722 47619 -52120 -111969 118035 49565 30062 85936 13353 -88313 79721 97357 -47821 -18184 -14350 49465 -73449 100477 -40931 46002 -40153 -115984 118245 10708 8761 16100 63563 -103839 28238 16080 36772 -27271 59976 -52235 43627 39017 -99342 -30771 117029 -104775 -106162 -65586 -10612 114148 28061 -56525 111689 -76075 -262 -20854 112100 -120357 98862 86304 53818 122368 93333 117517 -25288 -96626 -74077 41112 -29859 96372 1539 -67830 -29243 -10545 43067 123243 676 65429 97311 103696 16431 -103309 111648 41397 86015 -70966 -28974 -56069 5321 58848 53298 -60949 104956 -102189 -112320 86178 57471 -29674 82409 21002 89775 -81026 103778 -101119 -16237 105248 56770 -8208 -64352 -103095 70072 -57320 -64578 31261 120315 -85181 92628 87957 68572 33597 -12477 41247 -30530 -24902 -61364 25098 83502 2039 46001 -82100 50985 -47397 52102 40804 9079 -2391 -24150 74260 108326 92979 37758 117234 46945 -57372 65924 97037 9600 53338 101907 17313 -104169 -116339 -55005 100440 -13320 -99520 -20550 -109671 22973 84471 -29284 -90713 81807 44496 74726 -80488 44262 -35419 10749 84198 -84635 -18537 121146 108312 16690 115729 75536 65098 -25702 20964 -58631 -36271 -27879 -63030 16369 97462 89703 88274 -56502 47327 112962 -83995 94413 66095 -55522 105439 70506 -60497 80590 -86778 49396 21681 -1986 -56646 -32013 -73698 32509 112698 -53210 41595 31783 -87208 18544 -99088 -95043 74001 17337 59237 -39970 82828 -58215 -24018 82698 -57250 43736 17996 118452 -18792 111876 35066 19558 9540 116823 -53620 -33933 -123264 68243 -83442 72639 54539 72349 30048 109637 -55025 115994 -78569 65374 -77960 28921 28962 -13860 63406 -72914 -25786 -36633 -11246 112430 -102753 -44516 35593 57856 -67749 -87727 42855 58034 18820 -93372 61681 -49382 -48058 -66576 -116236 57005 90325 -72292 95823 -16381 111073 -109036 60855 -117437 -14912 -3090 99335 109857 -83343 15860 -89119 -29245 -97079 53745 80436 114278 121048 109258 85245 -22454 -72468 95963 -95071 30494 76640 46560 53533 17441 42242 63288 93333 44190 44587 -72904 50403 15933 -35106 -36433 83136 -23432 -79990 -111083 -89483 110361 -41190 -19603 -28061 102033 -40272 -95211 64721 -68712 55248 109488 73625 -43160 115 40849 -8155 23886 -83633 101788 -7186 112227 -60 33837 -48880 25585 94165 -105556 25721 48749 122946 33362 -63329 43383 34533 43504 23976 77775 -31988 30654 105623 79052 55905 -45020 122110 -20870 -25686 106278 -29222 45524 -98108 90603 -73719 -42109 1010 39585 -85549 -72605 -112017 -32665 3435 -5990 77317 -58124 -79916 39689 -107173 -116720 -32521 -9845 83939 115856 99113 -25589 5338 -47278 -47200 -55249 108093 -42169 -34153 114984 99523 3520 21892 16646 8131 70296 100426 -92742 -43561 -110236 -45505 -63914 36917 -98372 67957 -111126 18722 -117518 36503 106131 -51912 -23641 -21071 -80800 37285 -44029 -121691 -117986 89100 -93976 111679 68073 103870 -54110 21164 -104843 60747 -54196 6525 -17826 -41814 118298 17325 26051 -6307 15024 23489 -14666

[出力例]

5616244

■参照サイト
第八回アルゴリズム実技検定

2021年11月7日

C++ の動作確認をしてみた（５７４）

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題I (/2 and *3) を解いてみた.

■感想.
1. 問題Iは, 解説見る前に, AC版に到達出来たので, とりあえず良かったと思う.
2. 個人的には, 2で割る操作と 3倍する操作を分離できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第八回アルゴリズム実技検定の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PQ = priority_queue<LL, vector<LL>, greater<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--)

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 2で割る.
    PQ pq;
    int div2 = 0;
    rep(i, N){
        // 2-1. 数列情報.
        LL a;
        scanf("%lld", &a);
        
        // 2-2. 奇数になるまで, 2 で 割る.
        while(a % 2 == 0) a >>= 1, ++div2;
        
        // 2-3. 保存.
        pq.push(a);
    }
    
    // 3. 3倍.
    while(!pq.empty()){
        // 3-1. 終了条件.
        if(!div2) break;
        
        // 3-2. キューから取り出す.
        LL u = pq.top();
        pq.pop();
        
        // 3-3. 3倍.
        u *= 3;
        
        // 3-4. キューに追加
        pq.push(u);
        
        // 3-5. デクリメント.
        --div2;
    }
    
    // 4. 出力.
    printf("%lld\n", pq.top());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using PQ = priority_queue<LL, vector<LL>, greater<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--)

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 2で割る.

PQ pq;

int div2 = 0;

rep(i, N){

// 2-1. 数列情報.

LL a;

scanf("%lld", &a);

// 2-2. 奇数になるまで, 2 で割る.

while(a % 2 == 0) a >>= 1, ++div2;

// 2-3. 保存.

pq.push(a);

}

// 3. 3倍.

while(!pq.empty()){

// 3-1. 終了条件.

if(!div2) break;

// 3-2. キューから取り出す.

LL u = pq.top();

pq.pop();

// 3-3. 3倍.

u *= 3;

// 3-4. キューに追加

pq.push(u);

// 3-5. デクリメント.

--div2;

}

// 4. 出力.

printf("%lld\n", pq.top());

return 0;

}

[入力例]
3
18 21 46

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

[入力例]
5
3 5 7 11 13

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

[入力例]
1
536870912

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

[入力例]
5
6 12 17 24 36

[出力例]
27

[入力例]
12
16 1 11 7 19 10 3 15 10 6 11 20

[出力例]
7

[入力例]
30
903 4290 11651 6886 4522 2051 10537 6389 5615 7252 9955 1271 1500 3320 10305 1957 11754 361 11525 4677 7771 4114 9434 1573 12190 4413 1301 8567 11140 10215

[出力例]
2709

[入力例]
100
255177 539352 114111 116333 152352 254504 507854 158966 459971 136120 74089 218327 473688 211109 270243 106665 423847 395159 435763 105068 480932 217352 322191 146281 352761 391665 175844 24650 275489 120678 102108 457467 75147 183166 26946 232776 285580 525317 393712 531017 384839 50644 95325 314673 81191 410352 541072 482715 433486 287690 259208 130243 465146 417073 20032 156768 215758 88464 535952 137665 279363 401952 139894 474428 281928 6139 205849 25453 395731 125696 97106 349578 245913 324326 55309 477551 467515 44086 287975 447198 451891 157839 335931 222970 339594 115481 195777 438773 514460 96718 52502 229128 267207 418456 152736 139526 272765 496086 306578 349271

[出力例]
209289

[入力例]

18 21 46

[出力例]

※AtCoderのテストケースより

[入力例]

3 5 7 11 13

[出力例]

※AtCoderのテストケースより

[入力例]

536870912

[出力例]

68630377364883

※AtCoderのテストケースより

[入力例]

6 12 17 24 36

[出力例]

[入力例]

16 1 11 7 19 10 3 15 10 6 11 20

[出力例]

[入力例]

903 4290 11651 6886 4522 2051 10537 6389 5615 7252 9955 1271 1500 3320 10305 1957 11754 361 11525 4677 7771 4114 9434 1573 12190 4413 1301 8567 11140 10215

[出力例]

2709

[入力例]

100

255177 539352 114111 116333 152352 254504 507854 158966 459971 136120 74089 218327 473688 211109 270243 106665 423847 395159 435763 105068 480932 217352 322191 146281 352761 391665 175844 24650 275489 120678 102108 457467 75147 183166 26946 232776 285580 525317 393712 531017 384839 50644 95325 314673 81191 410352 541072 482715 433486 287690 259208 130243 465146 417073 20032 156768 215758 88464 535952 137665 279363 401952 139894 474428 281928 6139 205849 25453 395731 125696 97106 349578 245913 324326 55309 477551 467515 44086 287975 447198 451891 157839 335931 222970 339594 115481 195777 438773 514460 96718 52502 229128 267207 418456 152736 139526 272765 496086 306578 349271

[出力例]

209289

■参照サイト
第八回アルゴリズム実技検定

2021年11月6日

C++ の動作確認をしてみた（５７３）

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題G (K番目の要素) を解いてみた.

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

本家のサイト第八回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 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], b[101010], c[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, l = 0, h = 0, m;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
        h = max(h, b[i] + (a[i] - 1) * c[i]);
    }
    h = 2 * h + 1;
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. 各数列 で, m以下となる個数.
        LL ret = 0;
        rep(i, N){
            if(m < b[i]) continue;
            
            // 最大, a[i]個 までの 制約事項があるので, 注意.
            ret += min(a[i], (m - b[i]) / c[i] + 1);
        }
        
        // 2-2. 判定結果.
        return (ret < K);
    };
    
    // 3. 二分探索で確認してみる.
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 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], b[101010], c[101010];

int main(){

// 1. 入力情報.

int N;

LL K, l = 0, h = 0, m;

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

rep(i, N){

scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);

h = max(h, b[i] + (a[i] - 1) * c[i]);

}

h = 2 * h + 1;

// 2. 評価関数.

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

// 2-1. 各数列で, m以下となる個数.

LL ret = 0;

rep(i, N){

if(m < b[i]) continue;

// 最大, a[i]個までの制約事項があるので, 注意.

ret += min(a[i], (m - b[i]) / c[i] + 1);

}

// 2-2. 判定結果.

return (ret < K);

};

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

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

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

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 10
4 1000000000 1000000000
6 1000000000 1000000000

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

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

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

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

[出力例]
12

[入力例]
15 72
9 16 23
11 12 7
10 16 23
7 2 4
10 10 2
25 17 11
17 14 19
5 16 23
12 3 9
15 12 5
13 7 21
1 15 20
15 5 12
8 4 24
16 2 15

[出力例]
61

[入力例]

2 4

3 2 2

2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

2 10

4 1000000000 1000000000

6 1000000000 1000000000

[出力例]

6000000000

※AtCoderのテストケースより

[入力例]

5 10

3 1 4

1 5 9

2 6 5

3 5 8

9 7 9

[出力例]

※AtCoderのテストケースより

[入力例]

10 30

7 6 3

1 2 5

9 6 1

11 2 7

2 6 7

1 6 3

10 2 7

8 6 2

2 2 5

12 4 1

[出力例]

[入力例]

15 72

9 16 23

11 12 7

10 16 23

7 2 4

10 10 2

25 17 11

17 14 19

5 16 23

12 3 9

15 12 5

13 7 21

1 15 20

15 5 12

8 4 24

16 2 15

[出力例]

■参照サイト
第八回アルゴリズム実技検定

2021年11月5日2021年11月5日

C++ の動作確認をしてみた（５７２）

C++の練習を兼ねて, AtCoder Grand Contest 055 の問題A (ABC Identity) を解いてみた.

■感想.
1. 問題Aは, 実装に苦労したものの, 解説見る前に, AC版に到達出来たので, とりあえず良かったと思う.
2. 個人的には, ６個以下の部分列に分解できるという性質が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 055 の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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 ans[606060];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    char x[606060];
    scanf("%s", x);
    string s(x);
    
    // 2. 部分列に分解.
    int idx = 0;
    rep(i, 6){
        // インクリメント.
        idx++;
        
        // 出現位置.
        vvi pos(3);
        rep(j, N * 3){
            if(!ans[j]){
                if(s[j] == 'A') pos[0].pb(j);
                if(s[j] == 'B') pos[1].pb(j);
                if(s[j] == 'C') pos[2].pb(j);
            }
        }
        
        // 6通り確認.
        int maxT = -1, maxAt = -1;
        vvi ok;
        vi z(3);
        iota(all(z), 0);
        do{
            // 'A', 'B', 'C' の 出現位置.
            vi at;
            
            // 変数用意.
            int count = 0;
            int pz0 = pos[z[0]].size();
            int pz2 = pos[z[2]].size();
            
            // 矛盾している場合.
            if(!pz0 || !pz2) break;
            
            // 対象文字を何文字取れるか.
            rep(j, pz0){
                // 左から一番遠い位置.
                int at0 = pos[z[0]][j];
                
                // 右から一番遠い位置.
                if(j + 1 > pz2) break;
                int at2 = pos[z[2]][pz2 - 1 - j];
                
                // 矛盾していたら終了.
                if(at2 < at0) break;
                
                // 中央部分の文字数をチェック.
                int l = lower_bound(all(pos[z[1]]), at0) - pos[z[1]].begin();
                int r = lower_bound(all(pos[z[1]]), at2) - pos[z[1]].begin();
                if(r - l <= count) break;
                
                // 文字数.
                count = j + 1;
            }
            
            // 最大値更新.
            if(maxT < count){
                maxT = count;
                maxAt = ok.size();
            }
            
            // z[0] を 保存.
            rep(j, count) at.pb(pos[z[0]][j]);
            
            // z[2] を 保存.
            rep(j, count) at.pb(pos[z[2]][pz2 - 1 - j]);
            
            // z[1] を 保存.
            int l = lower_bound(all(pos[z[1]]), pos[z[0]][count - 1]) - pos[z[1]].begin();
            repx(j, l, l + count) at.pb(pos[z[1]][j]);
            
            // 保存.
            ok.pb(at);
        }while(next_permutation(all(z)));
        
        // 訪問済みフラグ設定.
        // -> 一番文字列を長く取れた部分を設定.
        if(maxAt != -1){
            for(auto &o : ok[maxAt]){
                ans[o] = idx;
                s[o] = '_';
            }
        }
    }
    
    // 3. 出力.
    rep(i, N * 3) printf("%d", ans[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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 ans[606060];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

char x[606060];

scanf("%s", x);

string s(x);

// 2. 部分列に分解.

int idx = 0;

rep(i, 6){

// インクリメント.

idx++;

// 出現位置.

vvi pos(3);

rep(j, N * 3){

if(!ans[j]){

if(s[j] == 'A') pos[0].pb(j);

if(s[j] == 'B') pos[1].pb(j);

if(s[j] == 'C') pos[2].pb(j);

}

// 6通り確認.

int maxT = -1, maxAt = -1;

vvi ok;

vi z(3);

iota(all(z), 0);

do{

// 'A', 'B', 'C' の出現位置.

vi at;

// 変数用意.

int count = 0;

int pz0 = pos[z[0]].size();

int pz2 = pos[z[2]].size();

// 矛盾している場合.

if(!pz0 || !pz2) break;

// 対象文字を何文字取れるか.

rep(j, pz0){

// 左から一番遠い位置.

int at0 = pos[z[0]][j];

// 右から一番遠い位置.

if(j + 1 > pz2) break;

int at2 = pos[z[2]][pz2 - 1 - j];

// 矛盾していたら終了.

if(at2 < at0) break;

// 中央部分の文字数をチェック.

int l = lower_bound(all(pos[z[1]]), at0) - pos[z[1]].begin();

int r = lower_bound(all(pos[z[1]]), at2) - pos[z[1]].begin();

if(r - l <= count) break;

// 文字数.

count = j + 1;

}

// 最大値更新.

if(maxT < count){

maxT = count;

maxAt = ok.size();

}

// z[0] を保存.

rep(j, count) at.pb(pos[z[0]][j]);

// z[2] を保存.

rep(j, count) at.pb(pos[z[2]][pz2 - 1 - j]);

// z[1] を保存.

int l = lower_bound(all(pos[z[1]]), pos[z[0]][count - 1]) - pos[z[1]].begin();

repx(j, l, l + count) at.pb(pos[z[1]][j]);

// 保存.

ok.pb(at);

}while(next_permutation(all(z)));

// 訪問済みフラグ設定.

// -> 一番文字列を長く取れた部分を設定.

if(maxAt != -1){

for(auto &o : ok[maxAt]){

ans[o] = idx;

s[o] = '_';

}

// 3. 出力.

rep(i, N * 3) printf("%d", ans[i]);

return 0;

}

[入力例]
2
ABCCBA

[出力例]
111222

※但し, 上記のプログラムでは, 以下の内容が出力される.
112122

[入力例]
4
AABCBCAACBCB

[出力例]
111211241244

※但し, 上記のプログラムでは, 以下の内容が出力される.
111212221212

[入力例]
3
AAACCCBBB

[出力例]
111111111

[入力例]
7
BACBCACAABABCBCBBACAC

[出力例]
214221213141311432121

[入力例]
17
ABCCBCACACCCAACBABAABACCBCBBCBCABBBABCBAACBABAABACC

[出力例]
321121313111115212112122323324215114141523121221233

[入力例]
20
CCBCCACACABCBABABABBCCACBBABCBBCAAACAABACAABACCBBBCABCCABCAB

[出力例]
331332323214121212112212331323321112113413343112221321132132

[入力例]
333
ACCCCABABCCBCABACCBCCCAAACBAABCBCCBCBCCACCBBCCABACACBABCCAABCBAACBBACAAABABAABABBABCBBABBCBACCBAACCBABCCCCCCCABBBCACCACABACACABACBACAACCABACBACCBCCCAAAAACBCACAABAACCBBABCCBBACBABBBACBBCCCAACABBACACBBCCBBAABAACBCAABCCABABBBAABCAAABBBBBCCABACBAABCABBAAABCCABCACBCBBAACCAAACCBBBABBBBCAAABCCCCAACBBBBCABCCCBBCAACCAACACBBBBBABABBAACACAACCBBACBBCCAABBACBAACBCCCAAABAAACBCABBBBBBBCCCBACBBABBACACCABCBAAABACCBBCACBBACCCAAACBABBCAACCBABBBBCBCCCABCBBCACCBCACCCBBCBBABAACCBBAACBCCABBBCAABBCBBBACABBBBBABBACCAACCAACCCBAAAACABCACAACCACCAABAABBACACBACBBACCCACCABABABCABBAABCABBACACCACBBBCCBCCBABBACCCCCAAAABCACBACCCCCBBABABBCCACCAAAABBABBABCACABABCCBAABCACBACBAABBAAACCABABACABCCCACBCBAAAACBBABBACBBBCCAACCACCCACCBCBCBCCBAABBAABCBCCCBCBBBAAABCAAABACCCCCBACABABBAACBACBBAACABBBBCABABCAACBCACACACAABABBCCCAABACCACBABBBACABBACCCCBAAACBCABABAABCAACAACBBABCABBACCBAABAACABBCCBACBBABCCCCCCBACBACBCBAABAACBCBBBCCACBBCBBABBBAABCCCBBBCBACAAACCCBBCBBABBBAAACBABACABAACCBCABACBACABCBAACABCBBBBCBACAACCACBABBCCCCBCACBABBBCAAC

[出力例]
122221313223213122322211123113232232322122332213121231322113231123312111313113133132331332312231122313222222213332122121312121312312112213123122322211111232121131122331322331231333123322211213312123322331131123211322131333113211133333221312311321331113221321232331122111223331333321113222211233332132223321122112123333313133112161111223122113322312331211133323331213222222211123122322313113212333231122131223111333123221331123222212111321221311213111221223233112233121132221332212223132222232231133113311123333132131331131133233223131231223111311323232132233213223131131222112112322311111333321312311111223232211311333322322321313232112332131231233223331142526124111256452222311211231113322332333233131313312211221313331311122213222123333312321211223123112232111132121322313232323221211333221233231211123211233331222313212122132232231121321123312212232113312311213333331231231312212231311133231131121112213331113123222333113112111222312123212233132123123213122321311113123223323121133331323121113223

[入力例]
1000
ABBAACCCCBCCCBCCCBBBBAAABCAAABBCACBCAACCCACCCCACCCCCACBCCBAABCBBBCABABCACBBBCAAABAAAACBCCABABACCAABAABBCBABBBABBBBCCACBACCAACCACBCBCCCCBCBBACCACACACCBCBCCAAABBCCCCCACACABACBBAACAACABAAACBBACAABCACBBCABCACBCBBCBACABBCCABACBCACAACBAABCBBAAABBABABCBBBACBBBBACACAAAAABAABAACBBABABCAABCAAAABACBCBACCAAABBCCCCCBCCCBBABBABCBBCAACACBCBCCBBCBABACACBCCBACABCBACCCBBBAAAAABBCBBCBABBAACBBABBACCABABABAABACABBCBCBBBCBCBBACBCCACBBCACAABABCCABCAAAAAACCBBAAACCBBABCABBACACABCABBCBCCAACBAAAACCBBCAAAABABCBABBACACBABBABBBABCACBABABABCCBACCBAAAACAACCAABABBCACBBCBBACCCCCAACCACBCABCBACBACBABBCCCBCBBBAABCBABCBCCBBBCCACCBBCBCAAACACACBCCBCCACCBACBABABACCCCBBBCBACBAACBBBBBAAACACCAABBACBABACCBABACABBAABBABACBCBBACBCBAAABBAABABCCBCBBCACBCCBBBABCCAACAABBABCBABACCAABCACBACCBCBAACBBCACCBCCAACBBAABBBCABBBAAAAABAAABBCCCABBBAABCAACBBCACABCBCCBCACAAACABABCCCCBCACBABBABABAACBCBCBBBCBCACCABAABCCACBBCCABCCBCBCCABABCCCABBABCBBACCCCBABCACAABBBCCCBCBCABCACABCAAACBACABACCAABACBACBABBABABCAAAAAAACACBBABCAACCABABACCCAACBAAABBCCBBBBABBACCABAAABABACCACCCACCACCCCCCAABCBACAABCACACBBACBCCBCACCBCBBAAABBACBBBABABCAACCCBBAAAACCCACCCCABAABCCBCAACBCAAAACCCCBCCBCCAACCAACCAAACACCCCCCCCAACCABAAABAACACAAABCCACBBBCCBBABAABCBAAAABBBBBCBCCABBCCCCCCCAABAAACABABCBAACCBCCACAACBABAABCCAABBCBAABBCCACACABACBCCACBBCBACABCBACABBABCAABCBCCCAACCBBACAABCCBBAACACBBCAACBAABBBBBACBCBCBACACCCCACACAABAAAABBCCBCCBCABBCCCBACAACABAACCAAABBACBCCBCAAABBCCACCABBBCBBCCCCBACCBCBBBABCBACCBBCABACCBCBCBBACACBBBBABBBBBBCACBAACBBBBCACABACBACBCCACCBCABCBCACBCCCBABBAABBCBBAABBACBBAACCABAABBBCBCBBCBBAACCBAABBACCAABACACBBACCCBACCACBCAACCBBABACBABCCCACCCCACCACCBCBBBACBACBCBACCCAAAABCCAABCBBACCACAABABABCAABACBCCBCCCCCBCBBACCCCCBCABCBBBABBBBBBACACAACBABAABBACBCCBBCAAAACACBCBCABACACABAABABAAACBCABCAACCBCAAAAAABCCACBBCCCAABABCACAACBCACCBCBCABBACCCBBBCAACBCAAAABACAAABCCBABACCBBACBBABBABBCCCBAABACCCAABBCCCCCABACBABBAAAACABBACBABBCBAACCCCCACABBABABAAACCBAACAACCAAAABABBAACBCABCBBCBABAAAAABACACBAACABBCABABBBBCBABBBCBBCACBABBAACABBBCCABBABCBCCACBAABBBACABBABCABAACAACBBCAABABCCCBAABBACCCACCACCBBAABCAACCAABABCBBAAAAACCCABCABCBBBCCCBAACACBAABACACCACBBCCCBBACABACCACCABCCABCBBCAAAABCBCACAACCAABCACBBABBCCCCCCCCCCCCABCCCABCBAAACCBCCACBCCBCAACBBBACCCAABAABCBBACBCABACBCACACBCCACCCCAAAABCABBAABCCCAACACAACBBAAABCABBABCBABBAAAABAACBAAAABBBACBCBCABABCAABABABBABBACCCAAAAABBBCCAABBBCCBCBCCABCCBABBCAACCCBABABABBAABCCCBCCAABBBBACCBCBCBBCCBABBACCCBCABBBACCBCCACAABACCCABCABABBCBABBABCACBABBAACBBBCCACCAACCBBCBBBCACBCBABAABBBCCACBACCBBBCACACAACBBABCCAAABCBCCABBACCABBBAACACAAABAABACACBBABABABBCCAAABAAABACCAABBBBABCBBCABAABAABBBAACAABBBBBBABCCCCCBCBBCBBCCABACCABBABAAABCCBBCABAAABAABBCABCBBABBABBCBCAAACBCABBCCCCAAAACABCBBACABCBBABACBCBACBBCCCBACBBCBCBCCABCABBAACABAACCCCACBCCABCBCBCBCABABAAAACBABCABABACBABACBABACBBBACACBACCCBAABABBABCCCCBABBCACBACAABCCBBBBCBBCCAACAABCBBABABACCACCCCBABBBBABBBAAAAACCBCACCBCCBABBABCACACCABCAACCBBABAACACBCABAAAABACBBAAACBBCCAACAABCAABBCCACCACCBBACCABACCABBBBCCCBAAABABACBAACCBAACBBACBCCBCCCBCBACBBBCCBBBBACCCBACBBABBBBABABCCCBAAABBBBABBCABABAACBBBACBC

[出力例]
133112222322232223333111321113321232112221222212222212322311323332131321233321113111123221313122113113323133313333221231221122123232222323312212121223232211133222221212131233112112131112331211321233213212323323121332213123212112311323311133131323331233331212111113113112331313211321111312323122111332222232223313313233211212323223323131212322312132312223331111133233231331123313312213131311312133232333232331232212332121131322132111111223311122331321331212132133232211231111223321111313231331212313313331321231313132231223111121122113133212332331222221122123213231231231332223233311323132322333221223323211121212322322122312313131222233323123112333331112122113312313122313121331133131232331232311133113132232332123223331322112113313231312211321231223231123321223221123311333213331111131113322213331132112332121323223212111213132222321231331313112323233323212213113221233221322323221313222133132331222231321211333222323213212132111231213122113123123134141421111111212441421122141412221122111224422221221441211121214414451113111111332123133213131223121121311212233322312223232133111223333111311113233211213312133331111211211331133113331311111111331132333233131333211312221122323321233332222212113221111111332333132321233112113133123233211332212332211313132312113122123132123132232133212111331122313321122331312213312332222231212123131111313133233332211211213221112313313233113332231211213332211311322212211112311212223212311221323112121223131222232222221312331222213132312312113112132121312111232233221223322312233113233222121221223311233223113323131223111231131213311223231232111311113113112122231231212311133332113321223113133232321332312112111112122311111213212223222222313133123233223121122133331312121323131323323233312132133112133333321131221113323213133121311212132231112221331213333231333211232311223122322322111233231113322111113231232233331322312322123311111313223232333112331331133332322331213212212323333323131233132213232222123222122131232233132221132232121131233222313223213235144122144242111244514333233233112213223322121311222223332132131113331223231221232332311333112321233233213321311322221313232233221323112113333333333332133321312223313323133132231112333221221311231321231323231332333322221321122133322323223112221321121312112222122312222111231313212132212121121123332222211133221113313133213312113223331212121122133313322111123313131133121123331321112331332322123332132121131211213231211223111332332233113111323131212211133231233111323232231121332221313321123321112232322212212323112121211332221222123322111121311321221221112232211111121333331311311332123321121222133113212221221132131121121131322231321133332222321311232131121231312311333123113131332132112232122333323133213131313212122223121321212312123121231112323123331221211213333121132312322133111131133223221311212123323333121111211122222331323313312112132323321322331121223231321222212311222311332232213221133233233112332123321111333122212123122331223112313313331312311133111123331231121111212133312221111211321212231112313

[入力例]

ABCCBA

[出力例]

111222

※但し, 上記のプログラムでは, 以下の内容が出力される.

112122

[入力例]

AABCBCAACBCB

[出力例]

111211241244

※但し, 上記のプログラムでは, 以下の内容が出力される.

111212221212

[入力例]

AAACCCBBB

[出力例]

111111111

[入力例]

BACBCACAABABCBCBBACAC

[出力例]

214221213141311432121

[入力例]

ABCCBCACACCCAACBABAABACCBCBBCBCABBBABCBAACBABAABACC

[出力例]

321121313111115212112122323324215114141523121221233

[入力例]

CCBCCACACABCBABABABBCCACBBABCBBCAAACAABACAABACCBBBCABCCABCAB

[出力例]

331332323214121212112212331323321112113413343112221321132132

[入力例]

333

ACCCCABABCCBCABACCBCCCAAACBAABCBCCBCBCCACCBBCCABACACBABCCAABCBAACBBACAAABABAABABBABCBBABBCBACCBAACCBABCCCCCCCABBBCACCACABACACABACBACAACCABACBACCBCCCAAAAACBCACAABAACCBBABCCBBACBABBBACBBCCCAACABBACACBBCCBBAABAACBCAABCCABABBBAABCAAABBBBBCCABACBAABCABBAAABCCABCACBCBBAACCAAACCBBBABBBBCAAABCCCCAACBBBBCABCCCBBCAACCAACACBBBBBABABBAACACAACCBBACBBCCAABBACBAACBCCCAAABAAACBCABBBBBBBCCCBACBBABBACACCABCBAAABACCBBCACBBACCCAAACBABBCAACCBABBBBCBCCCABCBBCACCBCACCCBBCBBABAACCBBAACBCCABBBCAABBCBBBACABBBBBABBACCAACCAACCCBAAAACABCACAACCACCAABAABBACACBACBBACCCACCABABABCABBAABCABBACACCACBBBCCBCCBABBACCCCCAAAABCACBACCCCCBBABABBCCACCAAAABBABBABCACABABCCBAABCACBACBAABBAAACCABABACABCCCACBCBAAAACBBABBACBBBCCAACCACCCACCBCBCBCCBAABBAABCBCCCBCBBBAAABCAAABACCCCCBACABABBAACBACBBAACABBBBCABABCAACBCACACACAABABBCCCAABACCACBABBBACABBACCCCBAAACBCABABAABCAACAACBBABCABBACCBAABAACABBCCBACBBABCCCCCCBACBACBCBAABAACBCBBBCCACBBCBBABBBAABCCCBBBCBACAAACCCBBCBBABBBAAACBABACABAACCBCABACBACABCBAACABCBBBBCBACAACCACBABBCCCCBCACBABBBCAAC

[出力例]

122221313223213122322211123113232232322122332213121231322113231123312111313113133132331332312231122313222222213332122121312121312312112213123122322211111232121131122331322331231333123322211213312123322331131123211322131333113211133333221312311321331113221321232331122111223331333321113222211233332132223321122112123333313133112161111223122113322312331211133323331213222222211123122322313113212333231122131223111333123221331123222212111321221311213111221223233112233121132221332212223132222232231133113311123333132131331131133233223131231223111311323232132233213223131131222112112322311111333321312311111223232211311333322322321313232112332131231233223331142526124111256452222311211231113322332333233131313312211221313331311122213222123333312321211223123112232111132121322313232323221211333221233231211123211233331222313212122132232231121321123312212232113312311213333331231231312212231311133231131121112213331113123222333113112111222312123212233132123123213122321311113123223323121133331323121113223

[入力例]

1000

ABBAACCCCBCCCBCCCBBBBAAABCAAABBCACBCAACCCACCCCACCCCCACBCCBAABCBBBCABABCACBBBCAAABAAAACBCCABABACCAABAABBCBABBBABBBBCCACBACCAACCACBCBCCCCBCBBACCACACACCBCBCCAAABBCCCCCACACABACBBAACAACABAAACBBACAABCACBBCABCACBCBBCBACABBCCABACBCACAACBAABCBBAAABBABABCBBBACBBBBACACAAAAABAABAACBBABABCAABCAAAABACBCBACCAAABBCCCCCBCCCBBABBABCBBCAACACBCBCCBBCBABACACBCCBACABCBACCCBBBAAAAABBCBBCBABBAACBBABBACCABABABAABACABBCBCBBBCBCBBACBCCACBBCACAABABCCABCAAAAAACCBBAAACCBBABCABBACACABCABBCBCCAACBAAAACCBBCAAAABABCBABBACACBABBABBBABCACBABABABCCBACCBAAAACAACCAABABBCACBBCBBACCCCCAACCACBCABCBACBACBABBCCCBCBBBAABCBABCBCCBBBCCACCBBCBCAAACACACBCCBCCACCBACBABABACCCCBBBCBACBAACBBBBBAAACACCAABBACBABACCBABACABBAABBABACBCBBACBCBAAABBAABABCCBCBBCACBCCBBBABCCAACAABBABCBABACCAABCACBACCBCBAACBBCACCBCCAACBBAABBBCABBBAAAAABAAABBCCCABBBAABCAACBBCACABCBCCBCACAAACABABCCCCBCACBABBABABAACBCBCBBBCBCACCABAABCCACBBCCABCCBCBCCABABCCCABBABCBBACCCCBABCACAABBBCCCBCBCABCACABCAAACBACABACCAABACBACBABBABABCAAAAAAACACBBABCAACCABABACCCAACBAAABBCCBBBBABBACCABAAABABACCACCCACCACCCCCCAABCBACAABCACACBBACBCCBCACCBCBBAAABBACBBBABABCAACCCBBAAAACCCACCCCABAABCCBCAACBCAAAACCCCBCCBCCAACCAACCAAACACCCCCCCCAACCABAAABAACACAAABCCACBBBCCBBABAABCBAAAABBBBBCBCCABBCCCCCCCAABAAACABABCBAACCBCCACAACBABAABCCAABBCBAABBCCACACABACBCCACBBCBACABCBACABBABCAABCBCCCAACCBBACAABCCBBAACACBBCAACBAABBBBBACBCBCBACACCCCACACAABAAAABBCCBCCBCABBCCCBACAACABAACCAAABBACBCCBCAAABBCCACCABBBCBBCCCCBACCBCBBBABCBACCBBCABACCBCBCBBACACBBBBABBBBBBCACBAACBBBBCACABACBACBCCACCBCABCBCACBCCCBABBAABBCBBAABBACBBAACCABAABBBCBCBBCBBAACCBAABBACCAABACACBBACCCBACCACBCAACCBBABACBABCCCACCCCACCACCBCBBBACBACBCBACCCAAAABCCAABCBBACCACAABABABCAABACBCCBCCCCCBCBBACCCCCBCABCBBBABBBBBBACACAACBABAABBACBCCBBCAAAACACBCBCABACACABAABABAAACBCABCAACCBCAAAAAABCCACBBCCCAABABCACAACBCACCBCBCABBACCCBBBCAACBCAAAABACAAABCCBABACCBBACBBABBABBCCCBAABACCCAABBCCCCCABACBABBAAAACABBACBABBCBAACCCCCACABBABABAAACCBAACAACCAAAABABBAACBCABCBBCBABAAAAABACACBAACABBCABABBBBCBABBBCBBCACBABBAACABBBCCABBABCBCCACBAABBBACABBABCABAACAACBBCAABABCCCBAABBACCCACCACCBBAABCAACCAABABCBBAAAAACCCABCABCBBBCCCBAACACBAABACACCACBBCCCBBACABACCACCABCCABCBBCAAAABCBCACAACCAABCACBBABBCCCCCCCCCCCCABCCCABCBAAACCBCCACBCCBCAACBBBACCCAABAABCBBACBCABACBCACACBCCACCCCAAAABCABBAABCCCAACACAACBBAAABCABBABCBABBAAAABAACBAAAABBBACBCBCABABCAABABABBABBACCCAAAAABBBCCAABBBCCBCBCCABCCBABBCAACCCBABABABBAABCCCBCCAABBBBACCBCBCBBCCBABBACCCBCABBBACCBCCACAABACCCABCABABBCBABBABCACBABBAACBBBCCACCAACCBBCBBBCACBCBABAABBBCCACBACCBBBCACACAACBBABCCAAABCBCCABBACCABBBAACACAAABAABACACBBABABABBCCAAABAAABACCAABBBBABCBBCABAABAABBBAACAABBBBBBABCCCCCBCBBCBBCCABACCABBABAAABCCBBCABAAABAABBCABCBBABBABBCBCAAACBCABBCCCCAAAACABCBBACABCBBABACBCBACBBCCCBACBBCBCBCCABCABBAACABAACCCCACBCCABCBCBCBCABABAAAACBABCABABACBABACBABACBBBACACBACCCBAABABBABCCCCBABBCACBACAABCCBBBBCBBCCAACAABCBBABABACCACCCCBABBBBABBBAAAAACCBCACCBCCBABBABCACACCABCAACCBBABAACACBCABAAAABACBBAAACBBCCAACAABCAABBCCACCACCBBACCABACCABBBBCCCBAAABABACBAACCBAACBBACBCCBCCCBCBACBBBCCBBBBACCCBACBBABBBBABABCCCBAAABBBBABBCABABAACBBBACBC

[出力例]

133112222322232223333111321113321232112221222212222212322311323332131321233321113111123221313122113113323133313333221231221122123232222323312212121223232211133222221212131233112112131112331211321233213212323323121332213123212112311323311133131323331233331212111113113112331313211321111312323122111332222232223313313233211212323223323131212322312132312223331111133233231331123313312213131311312133232333232331232212332121131322132111111223311122331321331212132133232211231111223321111313231331212313313331321231313132231223111121122113133212332331222221122123213231231231332223233311323132322333221223323211121212322322122312313131222233323123112333331112122113312313122313121331133131232331232311133113132232332123223331322112113313231312211321231223231123321223221123311333213331111131113322213331132112332121323223212111213132222321231331313112323233323212213113221233221322323221313222133132331222231321211333222323213212132111231213122113123123134141421111111212441421122141412221122111224422221221441211121214414451113111111332123133213131223121121311212233322312223232133111223333111311113233211213312133331111211211331133113331311111111331132333233131333211312221122323321233332222212113221111111332333132321233112113133123233211332212332211313132312113122123132123132232133212111331122313321122331312213312332222231212123131111313133233332211211213221112313313233113332231211213332211311322212211112311212223212311221323112121223131222232222221312331222213132312312113112132121312111232233221223322312233113233222121221223311233223113323131223111231131213311223231232111311113113112122231231212311133332113321223113133232321332312112111112122311111213212223222222313133123233223121122133331312121323131323323233312132133112133333321131221113323213133121311212132231112221331213333231333211232311223122322322111233231113322111113231232233331322312322123311111313223232333112331331133332322331213212212323333323131233132213232222123222122131232233132221132232121131233222313223213235144122144242111244514333233233112213223322121311222223332132131113331223231221232332311333112321233233213321311322221313232233221323112113333333333332133321312223313323133132231112333221221311231321231323231332333322221321122133322323223112221321121312112222122312222111231313212132212121121123332222211133221113313133213312113223331212121122133313322111123313131133121123331321112331332322123332132121131211213231211223111332332233113111323131212211133231233111323232231121332221313321123321112232322212212323112121211332221222123322111121311321221221112232211111121333331311311332123321121222133113212221221132131121121131322231321133332222321311232131121231312311333123113131332132112232122333323133213131313212122223121321212312123121231112323123331221211213333121132312322133111131133223221311212123323333121111211122222331323313312112132323321322331121223231321222212311222311332232213221133233233112332123321111333122212123122331223112313313331312311133111123331231121111212133312221111211321212231112313

■参照サイト
AtCoder Grand Contest 055

2021年11月3日2021年11月3日

C++ の動作確認をしてみた（５７１）

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, AC版に到達出来た.
2. 個人的には, 戻りが発生する箇所の考え方など, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト京都大学プログラミングコンテスト 2021 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/kupc2021/editorial/2862
// 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--)
#define a first
#define b second
LL a[202020], b[202020];
int aCum[202020], bCum[202020], diff[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, int> im;
    im[0] = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        im[a[i]] = 0;
    }
    rep(i, N){
        scanf("%lld", &b[i]);
        im[b[i]] = 0;
    }
    
    // 2. 番号付け.
    map<int, LL> om;
    int idx = -1;
    for(auto &p : im) p.b = ++idx, om[idx] = p.a;
    
    // 3. 累積和.
    rep(i, N){
        aCum[im[a[i]]]++;
        bCum[im[b[i]]]++;
    }
    rep(i, 202020 - 1){
        // ガチャ.
        aCum[i + 1] += aCum[i];
        
        // コイン.
        bCum[i + 1] += bCum[i];
        
        // コイン - ガチャ.
        diff[i + 1] = bCum[i + 1] - aCum[i + 1];
    }
    
    // 4. 全探索.
    LL ans = 202020202020202020, l = 0, r = 0, o = 0;
    bool isPlus = true;
    rep(f, idx + 1){
        // 最終地点が, f の 場合.
        l = om[f] - om[0];
        r = (om[idx] - om[f]) * 2;
        
        // 符号がマイナスの場合は, 戻りが発生する.
        if(!isPlus) o += (om[f] - om[f - 1]) * 2;
        
        // 符号チェック.
        isPlus = (diff[f] < 0) ? false : true;
        
        // 最小値更新.
        ans = min(ans, l + r + o);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/kupc2021/editorial/2862

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

#define a first

#define b second

LL a[202020], b[202020];

int aCum[202020], bCum[202020], diff[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, int> im;

im[0] = 0;

rep(i, N){

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

im[a[i]] = 0;

}

rep(i, N){

scanf("%lld", &b[i]);

im[b[i]] = 0;

}

// 2. 番号付け.

map<int, LL> om;

int idx = -1;

for(auto &p : im) p.b = ++idx, om[idx] = p.a;

// 3. 累積和.

rep(i, N){

aCum[im[a[i]]]++;

bCum[im[b[i]]]++;

}

rep(i, 202020 - 1){

// ガチャ.

aCum[i + 1] += aCum[i];

// コイン.

bCum[i + 1] += bCum[i];

// コイン - ガチャ.

diff[i + 1] = bCum[i + 1] - aCum[i + 1];

}

// 4. 全探索.

LL ans = 202020202020202020, l = 0, r = 0, o = 0;

bool isPlus = true;

rep(f, idx + 1){

// 最終地点が, f の場合.

l = om[f] - om[0];

r = (om[idx] - om[f]) * 2;

// 符号がマイナスの場合は, 戻りが発生する.

if(!isPlus) o += (om[f] - om[f - 1]) * 2;

// 符号チェック.

isPlus = (diff[f] < 0) ? false : true;

// 最小値更新.

ans = min(ans, l + r + o);

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2
1 2
1 1000000000

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

[入力例]
5
2 8 9 10 13
3 5 6 12 15

[出力例]
22

※実際, 以下の行動で, 移動距離 22 となる.
座標  3 (コイン)
座標  2 (ガチャ)
座標  5 (コイン)
座標  6 (コイン)
座標  8 (ガチャ)
座標  9 (ガチャ)
座標 12 (コイン)
座標 13 (ガチャ)
座標 15 (コイン)
座標 10 (ガチャ)
-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]
8
1 6 23 50 55 63 83 100
11 15 31 35 72 88 93 97

[出力例]
189

※実際, 以下の行動で, 移動距離 189 となる.
座標  11 (コイン)
座標  15 (コイン)
座標   6 (ガチャ)
座標   1 (ガチャ)
座標  31 (コイン)
座標  23 (ガチャ)
座標  35 (コイン)
座標  50 (ガチャ)
座標  72 (コイン)
座標  88 (コイン)
座標  93 (コイン)
座標  97 (コイン)
座標 100 (ガチャ)
座標  83 (ガチャ)
座標  63 (ガチャ)
座標  55 (ガチャ)
-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]
15
3 8 14 32 34 35 51 57 73 80 83 88 95 98 100
10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]
181

※実際, 以下の行動で, 移動距離 181 となる.
座標  10 (コイン)
座標  18 (コイン)
座標  23 (コイン)
座標  14 (ガチャ)
座標   8 (ガチャ)
座標   3 (ガチャ)
座標  25 (コイン)
座標  27 (コイン)
座標  28 (コイン)
座標  32 (ガチャ)
座標  34 (ガチャ)
座標  35 (ガチャ)
座標  40 (コイン)
座標  44 (コイン)
座標  51 (ガチャ)
座標  57 (ガチャ)
座標  59 (コイン)
座標  64 (コイン)
座標  68 (コイン)
座標  73 (ガチャ)
座標  80 (ガチャ)
座標  82 (コイン)
座標  83 (ガチャ)
座標  88 (ガチャ)
座標 107 (コイン)
座標 111 (コイン)
座標 118 (コイン)
座標 100 (ガチャ)
座標  98 (ガチャ)
座標  95 (ガチャ)
-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]
10
688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568
663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]
951677784

※実際, 以下の行動で, 移動距離 951677784 となる.
座標 663823866 (コイン)
座標 681857178 (コイン)
座標 688454010 (ガチャ)
座標 695372079 (ガチャ)
座標 702347983 (コイン)
座標 700190565 (ガチャ)
座標 719953098 (コイン)
座標 721150465 (コイン)
座標 739169216 (ガチャ)
座標 757252320 (コイン)
座標 774871450 (コイン)
座標 787159174 (ガチャ)
座標 793136394 (ガチャ)
座標 796656444 (ガチャ)
座標 831521457 (コイン)
座標 849407523 (コイン)
座標 880851457 (コイン)
座標 869694568 (ガチャ)
座標 822191962 (ガチャ)
座標 814339966 (ガチャ)
-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

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

[入力例]

1 6 7 12

3 5 10 11

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 1000000000

[出力例]

1999999998

※AtCoderテストケースより

[入力例]

2 8 9 10 13

3 5 6 12 15

[出力例]

※実際, 以下の行動で, 移動距離 22 となる.

座標 3 (コイン)

座標 2 (ガチャ)

座標 5 (コイン)

座標 6 (コイン)

座標 8 (ガチャ)

座標 9 (ガチャ)

座標 12 (コイン)

座標 13 (ガチャ)

座標 15 (コイン)

座標 10 (ガチャ)

-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]

1 6 23 50 55 63 83 100

11 15 31 35 72 88 93 97

[出力例]

189

※実際, 以下の行動で, 移動距離 189 となる.

座標 11 (コイン)

座標 15 (コイン)

座標 6 (ガチャ)

座標 1 (ガチャ)

座標 31 (コイン)

座標 23 (ガチャ)

座標 35 (コイン)

座標 50 (ガチャ)

座標 72 (コイン)

座標 88 (コイン)

座標 93 (コイン)

座標 97 (コイン)

座標 100 (ガチャ)

座標 83 (ガチャ)

座標 63 (ガチャ)

座標 55 (ガチャ)

-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]

3 8 14 32 34 35 51 57 73 80 83 88 95 98 100

10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]

181

※実際, 以下の行動で, 移動距離 181 となる.

座標 10 (コイン)

座標 18 (コイン)

座標 23 (コイン)

座標 14 (ガチャ)

座標 8 (ガチャ)

座標 3 (ガチャ)

座標 25 (コイン)

座標 27 (コイン)

座標 28 (コイン)

座標 32 (ガチャ)

座標 34 (ガチャ)

座標 35 (ガチャ)

座標 40 (コイン)

座標 44 (コイン)

座標 51 (ガチャ)

座標 57 (ガチャ)

座標 59 (コイン)

座標 64 (コイン)

座標 68 (コイン)

座標 73 (ガチャ)

座標 80 (ガチャ)

座標 82 (コイン)

座標 83 (ガチャ)

座標 88 (ガチャ)

座標 107 (コイン)

座標 111 (コイン)

座標 118 (コイン)

座標 100 (ガチャ)

座標 98 (ガチャ)

座標 95 (ガチャ)

-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]

688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568

663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]

951677784

※実際, 以下の行動で, 移動距離 951677784 となる.

座標 663823866 (コイン)

座標 681857178 (コイン)

座標 688454010 (ガチャ)

座標 695372079 (ガチャ)

座標 702347983 (コイン)

座標 700190565 (ガチャ)

座標 719953098 (コイン)

座標 721150465 (コイン)

座標 739169216 (ガチャ)

座標 757252320 (コイン)

座標 774871450 (コイン)

座標 787159174 (ガチャ)

座標 793136394 (ガチャ)

座標 796656444 (ガチャ)

座標 831521457 (コイン)

座標 849407523 (コイン)

座標 880851457 (コイン)

座標 869694568 (ガチャ)

座標 822191962 (ガチャ)

座標 814339966 (ガチャ)

-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

■参照サイト
京都大学プログラミングコンテスト 2021

2021年11月1日

C++ の動作確認をしてみた（５７０）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題F (Problem where +s Separate Digits) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 確率, 期待値の考え方で, 解いていく方針が, 不思議な印象を受けたとともに, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2805
// 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 MOD = 998244353;
LL mPowP2[202020], mPowM2[202020], mPow10[202020], mCum[202020];

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string s(c);
    int N = s.size();
    
    // 2. 例外.
    if(N == 1){
        printf("%s\n", s.c_str());
        return 0;
    }
    
    // 3. 2, 10 の 冪乗.
    mPowP2[0] = mPowM2[0] = mPow10[0] = 1;
    rep(i, N + 1){
        mPowP2[i + 1] = (2 * mPowP2[i]) % MOD;
        mPowM2[i + 1] = (499122177 * mPowM2[i]) % MOD;
        mPow10[i + 1] = (10 * mPow10[i]) % MOD;
    }
    
    // 4. 累積和.
    // ex.
    // k = 1 -> 0 +                                                  (+     1 * 1 /  1)
    // k = 2 -> 1 * 1 / 2                                            (+    10 * 1 /  2)
    // k = 3 -> 1 * 1 / 2 + 10 * 1 / 4                               (+   100 * 1 /  4)
    // k = 4 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8                 (+  1000 * 1 /  8)
    // k = 5 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 + 1000 * 1 / 16 (+ 10000 * 1 / 16)
    // ...
    // -> 例外部分は, 後述の集計時に考慮すれば十分のはず.
    repx(i, 2, N + 1){
        mCum[i] += mCum[i - 1];
        mCum[i] %= MOD;
        mCum[i] += mPowM2[i - 1] * mPow10[i - 2];
        mCum[i] %= MOD;
    }
    
    // 5. 文字列 S の 各文字について, 集計.
    // -> 文字列 S の 右から k文字目 を x と 見て計算.
    LL ans = 0;
    repx(k, 1, N + 1){
        // 等比数列の和.
        int i = N - k;
        LL x = (LL)(s[i] - '0');
        ans += x * mCum[k];
        ans %= MOD;
        
        // 例外.
        ans += x * mPowM2[k - 1] * mPow10[k - 1];
        ans %= MOD;
    }
    
    // 6. 2 の |S| - 1 乗 を 乗ずる.
    ans *= mPowP2[N - 1];
    ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2805

// 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 MOD = 998244353;

LL mPowP2[202020], mPowM2[202020], mPow10[202020], mCum[202020];

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string s(c);

int N = s.size();

// 2. 例外.

if(N == 1){

printf("%s\n", s.c_str());

return 0;

}

// 3. 2, 10 の冪乗.

mPowP2[0] = mPowM2[0] = mPow10[0] = 1;

rep(i, N + 1){

mPowP2[i + 1] = (2 * mPowP2[i]) % MOD;

mPowM2[i + 1] = (499122177 * mPowM2[i]) % MOD;

mPow10[i + 1] = (10 * mPow10[i]) % MOD;

}

// 4. 累積和.

// ex.

// k = 1 -> 0 + (+ 1 * 1 / 1)

// k = 2 -> 1 * 1 / 2 (+ 10 * 1 / 2)

// k = 3 -> 1 * 1 / 2 + 10 * 1 / 4 (+ 100 * 1 / 4)

// k = 4 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 (+ 1000 * 1 / 8)

// k = 5 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 + 1000 * 1 / 16 (+ 10000 * 1 / 16)

// ...

// -> 例外部分は, 後述の集計時に考慮すれば十分のはず.

repx(i, 2, N + 1){

mCum[i] += mCum[i - 1];

mCum[i] %= MOD;

mCum[i] += mPowM2[i - 1] * mPow10[i - 2];

mCum[i] %= MOD;

}

// 5. 文字列 S の各文字について, 集計.

// -> 文字列 S の右から k文字目を x と見て計算.

LL ans = 0;

repx(k, 1, N + 1){

// 等比数列の和.

int i = N - k;

LL x = (LL)(s[i] - '0');

ans += x * mCum[k];

ans %= MOD;

// 例外.

ans += x * mPowM2[k - 1] * mPow10[k - 1];

ans %= MOD;

}

// 6. 2 の |S| - 1 乗を乗ずる.

ans *= mPowP2[N - 1];

ans %= MOD;

// 7. 出力.

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

return 0;

}

[入力例]
1234

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

[入力例]
1

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

[入力例]
31415926535897932384626433832795

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

[入力例]
11

[出力例]
13

[入力例]
111

[出力例]
138

[入力例]
2021

[出力例]
2344

[入力例]
20211101

[出力例]
23511616

[入力例]
2236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274

[出力例]
83041925

[入力例]

1234

[出力例]

1736

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

31415926535897932384626433832795

[出力例]

85607943

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

111

[出力例]

138

[入力例]

2021

[出力例]

2344

[入力例]

20211101

[出力例]

23511616

[入力例]

2236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274

[出力例]

83041925

■参照サイト
AtCoder Beginner Contest 224

2021年10月31日2021年10月31日

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

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題B (Painting with Many Orders) を解いてみた.

■感想.
1. 問題B は, 規則性を抽出できたので, AC版に到達できたと思う.
2. 個人的には, すべての黒いマスが, 少なくとも１つの白いマスに隣接しているという条件が含まれることで, より問題が, 面白くなっている印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト京都大学プログラミングコンテスト 2021 解説の各リンクをご覧下さい.

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

// 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--)
char ans[505][505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期化.
    rep(i, 505) rep(j, 505) ans[i][j] = '.';
    
    // 3. 編集.
    // ex.
    // N = 8
    // #######.
    // ........
    // #.#.#.#.
    // #...#.#.
    // #.###.#.
    // #.....#.
    // #.#####.
    // #.......
    // -> 上記のような出力を実現したい.
    // 3-1. 1行目, 1列目.
    rep(j, N - 1) ans[0][j] = '#';
    repx(i, 2, N) ans[i][0] = '#';
    
    // 3-2. 矩形範囲.
    // -> N = 8 ならば, 8 - 3 = 5 なので, 1, 3, 5 を 見る.
    if(N - 3 > 0){
        int n = N - 3;
        repex(a, 2 - (n % 2), N - 2, 2){
            // 行方向.
            repr(j, a + 1, 2) ans[a + 1][j] = '#';
            
            // 列方向.
            repr(i, a + 1, 2) ans[i][a + 1] = '#';
        }
    }
    
    // 4. 出力.
    rep(i, N){
        rep(j, N) printf("%c", ans[i][j]);
        puts("");
    }
    return 0;
    
}

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

char ans[505][505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期化.

rep(i, 505) rep(j, 505) ans[i][j] = '.';

// 3. 編集.

// ex.

// N = 8

// #######.

// ........

// #.#.#.#.

// #...#.#.

// #.###.#.

// #.....#.

// #.#####.

// #.......

// -> 上記のような出力を実現したい.

// 3-1. 1行目, 1列目.

rep(j, N - 1) ans[0][j] = '#';

repx(i, 2, N) ans[i][0] = '#';

// 3-2. 矩形範囲.

// -> N = 8 ならば, 8 - 3 = 5 なので, 1, 3, 5 を見る.

if(N - 3 > 0){

int n = N - 3;

repex(a, 2 - (n % 2), N - 2, 2){

// 行方向.

repr(j, a + 1, 2) ans[a + 1][j] = '#';

// 列方向.

repr(i, a + 1, 2) ans[i][a + 1] = '#';

}

// 4. 出力.

rep(i, N){

rep(j, N) printf("%c", ans[i][j]);

puts("");

}

return 0;

}

[入力例]
3

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
##.
...
#..

[入力例]
2

[出力例]
#.
..

[入力例]
4

[出力例]
###.
....
#.#.
#...

[入力例]
5

[出力例]
####.
.....
#..#.
#.##.
#....

[入力例]
6

[出力例]
#####.
......
#.#.#.
#...#.
#.###.
#.....

[入力例]
7

[出力例]
######.
.......
#..#.#.
#.##.#.
#....#.
#.####.
#......

[入力例]
8

[出力例]
#######.
........
#.#.#.#.
#...#.#.
#.###.#.
#.....#.
#.#####.
#.......

[入力例]
10

[出力例]
#########.
..........
#.#.#.#.#.
#...#.#.#.
#.###.#.#.
#.....#.#.
#.#####.#.
#.......#.
#.#######.
#.........

[入力例]

[出力例]

..#

#.#

...

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

##.

...

#..

[入力例]

[出力例]

[入力例]

[出力例]

###.

....

#.#.

#...

[入力例]

[出力例]

####.

.....

#..#.

#.##.

#....

[入力例]

[出力例]

#####.

......

#.#.#.

#...#.

#.###.

#.....

[入力例]

[出力例]

######.

.......

#..#.#.

#.##.#.

#....#.

#.####.

#......

[入力例]

[出力例]

#######.

........

#.#.#.#.

#...#.#.

#.###.#.

#.....#.

#.#####.

#.......

[入力例]

[出力例]

#########.

..........

#.#.#.#.#.

#...#.#.#.

#.###.#.#.

#.....#.#.

#.#####.#.

#.......#.

#.#######.

#.........

■参照サイト
京都大学プログラミングコンテスト 2021

2021年10月31日

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

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2814
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using T3 = tuple<int, int, int>;
using T4 = tuple<int, 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()
#define a first
#define b second
int dp[202020], rMax[202020], cMax[202020];

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    vector<T4> t;
    map<int, int> m;
    rep(i, N){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        t.emplace_back(a, r, c, i);
        m[a] = 0;
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. マスに記載された整数 X の並び替え.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 整数 X ごとに分類.
    vector<vector<T3>> u(idx + 1);
    for(auto &p : t){
        int a = get<0>(p);
        int r = get<1>(p);
        int c = get<2>(p);
        int j = get<3>(p);
        u[m[a]].emplace_back(r, c, j);
    }
    
    // 5. dp更新.
    repr(i, idx, 0){
        // dp更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            dp[j] = max(rMax[r], cMax[c]);
        }
        
        // rMax, cMax更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            rMax[r] = max(rMax[r], dp[j] + 1);
            cMax[c] = max(cMax[c], dp[j] + 1);
        }
    }
    
    // 6. 出力.
    rep(i, N) printf("%d\n", dp[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2814

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using T3 = tuple<int, int, int>;

using T4 = tuple<int, 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()

#define a first

#define b second

int dp[202020], rMax[202020], cMax[202020];

int main(){

// 1. 入力情報.

int H, W, N;

scanf("%d %d %d", &H, &W, &N);

vector<T4> t;

map<int, int> m;

rep(i, N){

int r, c, a;

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

t.emplace_back(a, r, c, i);

m[a] = 0;

}

// 2. sort.

sort(all(t));

// 3. マスに記載された整数 X の並び替え.

int idx = -1;

for(auto &p : m) p.b = ++idx;

// 4. 整数 X ごとに分類.

vector<vector<T3>> u(idx + 1);

for(auto &p : t){

int a = get<0>(p);

int r = get<1>(p);

int c = get<2>(p);

int j = get<3>(p);

u[m[a]].emplace_back(r, c, j);

}

// 5. dp更新.

repr(i, idx, 0){

// dp更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

dp[j] = max(rMax[r], cMax[c]);

}

// rMax, cMax更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

rMax[r] = max(rMax[r], dp[j] + 1);

cMax[c] = max(cMax[c], dp[j] + 1);

}

// 6. 出力.

rep(i, N) printf("%d\n", dp[i]);

return 0;

}

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

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

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

[出力例]
2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0
※AtCoderテストケースより

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

[出力例]
1
0
5
2
1
1
0
4
3
2
2
2
1
4
3
3
2
4

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

[出力例]
1
0
1
6
7
10
11
1
4
5
8
9
2
5
6
1
0
0
4
3
2
1
0
5
6
7
8
9
10
11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

[入力例]

3 3 7

1 1 4

1 2 7

2 1 3

2 3 5

3 1 2

3 2 5

3 3 5

[出力例]

※AtCoderテストケースより

[入力例]

5 7 20

2 7 8

2 6 4

4 1 9

1 5 4

2 2 7

5 5 2

1 7 2

4 6 6

1 4 1

2 1 10

5 6 9

5 3 3

3 7 9

3 6 3

4 3 4

3 3 10

4 2 1

3 5 4

1 2 6

4 7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 6 18

1 1 3

1 5 7

2 1 1

2 2 4

2 4 6

2 5 6

2 6 8

3 1 2

3 2 3

3 3 5

3 4 5

3 5 5

3 6 7

4 2 2

4 3 4

4 4 4

4 6 6

5 3 3

[出力例]

[入力例]

10 8 30

2 1 9

3 1 10

4 1 9

5 1 6

6 1 5

7 1 2

8 1 1

3 2 9

4 2 8

5 2 7

6 2 4

7 2 3

3 3 8

4 3 7

6 3 5

3 4 9

4 4 11

3 5 10

3 6 8

4 6 9

5 6 10

6 6 11

7 6 12

3 7 7

4 7 6

5 7 5

5 8 4

6 8 3

7 8 2

8 8 1

[出力例]

■参照サイト
AtCoder Beginner Contest 224

2021年10月30日2021年10月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題E (Red and Blue Tree) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc222/editorial/2751
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<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 pb push_back
const LL MOD = 998244353;
int a[101], c[1010];
LL dp[1010][101010];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    rep(i, M){
        scanf("%d", &a[i]);
        a[i]--;
    }
    vvi G(N);
    map<P, int> E;
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].pb(v);
        G[v].pb(u);
        
        // 辺 i は, (u[i], v[i]) or (v[i], u[i]) と 読み替え.
        E[{u, v}] = i;
        E[{v, u}] = i;
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                // 未訪問の頂点を処理.
                if(d[e])   continue;
                if(e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    
    // 3. 最短経路.
    auto f = [&](vvi &G, int g, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 g をキュー q に追加.
        q.push(g);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                if(d[e] == d[u] - 1){
                    // 距離が 1 小さい頂点を追加.
                    q.push(e);
                    
                    // 最短経路を構成する辺とみて, カウントアップ.
                    c[E[{e, u}]]++;
                }
            }
        }
        return;
    };
    
    // 4. 各辺を通過する数を計算.
    rep(i, M - 1){
        // 辺情報.
        int s = a[i];
        int g = a[i + 1];
        
        // 最短距離.
        int d[1010];
        rep(j, 1010) d[j] = 0;
        bfs(G, s, d);
        // puts("\n----- bfs start -----");
        // rep(j, N) printf("%d ", d[j]);
        // puts("\n----- bfs end -----");
        
        // 最短経路.
        f(G, g, d);
        // puts("----- shortest path start -----");
        // rep(j, N - 1) printf("%d ", c[j]);
        // puts("\n----- shortest path end -----");
    }
    
    // 5. 例外チェック.
    // -> (K + S) / 2 が 整数でない, 0未満.
    int S = 0;
    rep(i, N - 1) S += c[i];
    int x = (K + S) / 2;
    // printf("S=%d K=%d x=%d\n", S, K, x);
    if(x * 2 != K + S || x < 0){
        puts("0");
        return 0;
    }
    
    // 6. dp更新.
    rep(i, 1010) dp[i][0] = 1;
    rep(i, N - 1){
        // 前回分反映.
        if(i) rep(j, 101010) dp[i][j] = dp[i - 1][j];
        
        // 今回分反映.
        repr(j, 101009, 0){
            int at = j + c[i];
            if(at <= 101009){
                if(dp[i][j]){
                    dp[i][at] += dp[i][j];
                    dp[i][at] %= MOD;
                }
            }
        }
    }
    // rep(i, N - 1){
    //     rep(j, 10) printf("%lld ", dp[i][j]);
    //     puts("");
    // }
    
    // 7. 出力.
    printf("%lld\n", dp[N - 2][x]);
    return 0;
    
}

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

// 解き直し.

// https://atcoder.jp/contests/abc222/editorial/2751

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<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 pb push_back

const LL MOD = 998244353;

int a[101], c[1010];

LL dp[1010][101010];

int main(){

// 1. 入力情報.

int N, M, K;

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

rep(i, M){

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

a[i]--;

}

vvi G(N);

map<P, int> E;

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

u--;

v--;

G[u].pb(v);

G[v].pb(u);

// 辺 i は, (u[i], v[i]) or (v[i], u[i]) と読み替え.

E[{u, v}] = i;

E[{v, u}] = i;

}

// 2. bfs.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 空のキュー.

queue<int> q;

// 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &e : G[u]){

// 未訪問の頂点を処理.

if(d[e]) continue;

if(e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

// 3. 最短経路.

auto f = [&](vvi &G, int g, int* d){

// 空のキュー.

queue<int> q;

// 探索地点 g をキュー q に追加.

q.push(g);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &e : G[u]){

if(d[e] == d[u] - 1){

// 距離が 1 小さい頂点を追加.

q.push(e);

// 最短経路を構成する辺とみて, カウントアップ.

c[E[{e, u}]]++;

}

return;

};

// 4. 各辺を通過する数を計算.

rep(i, M - 1){

// 辺情報.

int s = a[i];

int g = a[i + 1];

// 最短距離.

int d[1010];

rep(j, 1010) d[j] = 0;

bfs(G, s, d);

// puts("\n----- bfs start -----");

// rep(j, N) printf("%d ", d[j]);

// puts("\n----- bfs end -----");

// 最短経路.

f(G, g, d);

// puts("----- shortest path start -----");

// rep(j, N - 1) printf("%d ", c[j]);

// puts("\n----- shortest path end -----");

}

// 5. 例外チェック.

// -> (K + S) / 2 が整数でない, 0未満.

int S = 0;

rep(i, N - 1) S += c[i];

int x = (K + S) / 2;

// printf("S=%d K=%d x=%d\n", S, K, x);

if(x * 2 != K + S || x < 0){

puts("0");

return 0;

}

// 6. dp更新.

rep(i, 1010) dp[i][0] = 1;

rep(i, N - 1){

// 前回分反映.

if(i) rep(j, 101010) dp[i][j] = dp[i - 1][j];

// 今回分反映.

repr(j, 101009, 0){

int at = j + c[i];

if(at <= 101009){

if(dp[i][j]){

dp[i][at] += dp[i][j];

dp[i][at] %= MOD;

}

// rep(i, N - 1){

// rep(j, 10) printf("%lld ", dp[i][j]);

// puts("");

// }

// 7. 出力.

printf("%lld\n", dp[N - 2][x]);

return 0;

}

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

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

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

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

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

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

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

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

[入力例]
2 2 1
2 1
1 2

[出力例]
1

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

[出力例]
8

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

[出力例]
226

[入力例]
21 77 6
18 9 4 6 8 18 9 9 15 7 4 19 15 19 7 20 9 7 1 16 14 6 13 10 14 16 5 1 7 7 15 18 18 10 15 5 2 19 1 1 9 7 9 16 18 5 8 17 18 12 1 3 18 20 10 9 9 18 16 14 8 15 12 15 6 11 5 2 2 12 14 1 19 12 21 13 10
7 1
4 1
6 1
2 3
2 5
2 7
7 8
11 10
12 10
9 10
9 8
9 16
16 17
18 17
8 13
13 15
13 14
8 19
19 20
19 21

[出力例]
12318

[入力例]
30 100 -8
4 8 16 20 19 2 28 29 12 14 22 13 9 29 24 17 24 1 17 19 19 2 20 10 2 25 9 21 5 4 11 27 20 6 28 24 6 29 27 22 16 8 23 5 21 27 5 1 29 26 30 11 10 20 4 20 28 22 19 19 8 6 14 1 5 5 14 25 4 29 3 29 19 21 24 30 8 24 7 28 3 21 18 4 6 5 17 2 15 29 12 5 29 13 18 7 22 3 23 2
1 5
2 1
15 1
14 1
4 1
3 1
3 13
3 12
12 22
12 23
16 15
17 15
16 27
16 26
26 29
26 28
2 30
2 6
2 7
7 24
25 7
5 8
9 5
18 14
14 19
4 10
4 11
20 11
21 11

[出力例]
5324136

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

[入力例]

4 5 0

2 3 2 1 4

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 10 10000

1 2 1 2 1 2 2 1 1 2

1 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

10 2 -1

1 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

[出力例]

126

※AtCoderテストケースより

[入力例]

5 8 -1

1 4 1 4 2 1 3 5

1 2

4 1

3 1

1 5

[出力例]

※AtCoderテストケースより

[入力例]

2 2 1

2 1

1 2

[出力例]

[入力例]

7 7 3

2 1 6 4 5 7 3

2 1

2 3

1 7

1 5

3 6

4 3

[出力例]

[入力例]

13 36 2

2 10 11 3 6 7 13 4 12 7 5 12 8 6 11 10 9 11 5 13 4 3 12 6 6 2 1 11 10 4 4 13 7 3 7 2

2 1

2 7

2 3

2 8

8 9

10 8

10 11

10 6

3 4

5 3

5 13

5 12

[出力例]

226

[入力例]

21 77 6

18 9 4 6 8 18 9 9 15 7 4 19 15 19 7 20 9 7 1 16 14 6 13 10 14 16 5 1 7 7 15 18 18 10 15 5 2 19 1 1 9 7 9 16 18 5 8 17 18 12 1 3 18 20 10 9 9 18 16 14 8 15 12 15 6 11 5 2 2 12 14 1 19 12 21 13 10

7 1

4 1

6 1

2 3

2 5

2 7

7 8

11 10

12 10

9 10

9 8

9 16

16 17

18 17

8 13

13 15

13 14

8 19

19 20

19 21

[出力例]

12318

[入力例]

30 100 -8

4 8 16 20 19 2 28 29 12 14 22 13 9 29 24 17 24 1 17 19 19 2 20 10 2 25 9 21 5 4 11 27 20 6 28 24 6 29 27 22 16 8 23 5 21 27 5 1 29 26 30 11 10 20 4 20 28 22 19 19 8 6 14 1 5 5 14 25 4 29 3 29 19 21 24 30 8 24 7 28 3 21 18 4 6 5 17 2 15 29 12 5 29 13 18 7 22 3 23 2

1 5

2 1

15 1

14 1

4 1

3 1

3 13

3 12

12 22

12 23

16 15

17 15

16 27

16 26

26 29

26 28

2 30

2 6

2 7

7 24

25 7

5 8

9 5

18 14

14 19

4 10

4 11

20 11

21 11

[出力例]

5324136

■参照サイト
エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）

C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題C (Martial artist) ～ 問題D (Teleportation) を解いてみた.

C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題L (K番目の絶対値) を解いてみた.

C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題I (/2 and *3) を解いてみた.

C++の練習を兼ねて, 第八回 アルゴリズム実技検定 の 問題G (K番目の要素) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 055 の 問題A (ABC Identity) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の 問題C (Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題F (Problem where +s Separate Digits) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の 問題B (Painting with Many Orders) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題E (Integers on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の 問題E (Red and Blue Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題C (Martial artist) ～問題D (Teleportation) を解いてみた.

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題L (K番目の絶対値) を解いてみた.

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題I (/2 and *3) を解いてみた.

C++の練習を兼ねて, 第八回アルゴリズム実技検定の問題G (K番目の要素) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 055 の問題A (ABC Identity) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題F (Problem where +s Separate Digits) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題B (Painting with Many Orders) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題E (Red and Blue Tree) を解いてみた.