C++ | 個人用メモ帳

2022年11月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 152 の問題C (Pivot) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc152/editorial/5118
// 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[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 解説通り.
    LL d = a[N - 1] - a[0], g = d, m = a[0];
    rep(i, N) g = __gcd(g, 2 * (a[i] - m));
    
    // 3. 出力.
    printf("%lld\n", m % g + d);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc152/editorial/5118

// 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[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 解説通り.

LL d = a[N - 1] - a[0], g = d, m = a[0];

rep(i, N) g = __gcd(g, 2 * (a[i] - m));

// 3. 出力.

printf("%lld\n", m % g + d);

return 0;

}

[入力例]
3
1 3 6

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

[入力例]
5
400 500 600 700 800

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

[入力例]
10
28 35 48 60 64 71 98 99 101 105

[出力例]
77

[入力例]
30
101 120 222 333 429 433 444 465 500 510 528 555 600 666 701 777 811 826 828 888 900 924 987 999 1010 1111 1155 1199 1200 1212

[出力例]
1111

[入力例]
50
2244 2823 2952 4405 4758 5000 11111 13509 14422 14746 20081 22222 30000 31135 31160 31171 31423 33333 41000 43000 44444 44633 55555 58825 60236 62022 65280 66392 66666 68304 69169 70842 72100 73600 77777 79455 81845 83000 84427 96524 97000 97967 98639 99227 99999 100000 105000 111111 115000 123456

[出力例]
121212

[入力例]

1 3 6

[出力例]

※AtCoderのテストケースより

[入力例]

400 500 600 700 800

[出力例]

400

※AtCoderのテストケースより

[入力例]

28 35 48 60 64 71 98 99 101 105

[出力例]

[入力例]

101 120 222 333 429 433 444 465 500 510 528 555 600 666 701 777 811 826 828 888 900 924 987 999 1010 1111 1155 1199 1200 1212

[出力例]

1111

[入力例]

2244 2823 2952 4405 4758 5000 11111 13509 14422 14746 20081 22222 30000 31135 31160 31171 31423 33333 41000 43000 44444 44633 55555 58825 60236 62022 65280 66392 66666 68304 69169 70842 72100 73600 77777 79455 81845 83000 84427 96524 97000 97967 98639 99227 99999 100000 105000 111111 115000 123456

[出力例]

121212

■参照サイト
AtCoder Regular Contest 152

2022年11月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 152 の問題A (Seat Occupation) ～問題B (Pass on Path) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc152/editorial/5100
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    
    // 2. 解説通り.
    int k = 0, a;
    rep(i, N){
        scanf("%d", &a);
        if(a == 2) k = i + 1;
    }
    
    // 3. 出力.
    printf("%s\n", (2 * k <= N + 1) ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc152/editorial/5100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N, L;

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

// 2. 解説通り.

int k = 0, a;

rep(i, N){

scanf("%d", &a);

if(a == 2) k = i + 1;

}

// 3. 出力.

printf("%s\n", (2 * k <= N + 1) ? "Yes" : "No");

return 0;

}

[入力例]
2 4
2 2

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

[入力例]
3 4
1 2 1

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

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

[出力例]
Yes

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

[出力例]
No

[入力例]
8 11
2 1 2 2 1 1 1 1

[出力例]
Yes

[入力例]
17 23
1 1 1 1 1 1 1 2 2 1 2 2 2 1 1 1 2

[出力例]
No

[入力例]
100 115
2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]
Yes

[入力例]

2 4

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

1 2 1

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 7

2 1 2 1 1

[出力例]

Yes

[入力例]

5 7

1 1 1 2 2

[出力例]

[入力例]

8 11

2 1 2 2 1 1 1 1

[出力例]

Yes

[入力例]

17 23

1 1 1 1 1 1 1 2 2 1 2 2 2 1 1 1 2

[出力例]

[入力例]

100 115

2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc152/editorial/5101
// 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[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL L;
    scanf("%d %lld", &N, &L);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 尺取り法(解説通り).
    LL ans = 202020202020202020;
    LL r = N - 1;
    rep(l, N){
        // l, r を 見つける.
        LL d = abs(a[l] - (L - a[r]));
        repr(i, r, l){
            if(d < abs(a[l] - (L - a[i]))) break;
            d = abs(a[l] - (L - a[i]));
            r = i;
        }
        
        // 最小値更新.
        ans = min(ans, 2 * L + 2 * d);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc152/editorial/5101

// 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[202020];

int main(){

// 1. 入力情報.

int N;

LL L;

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

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

// 2. 尺取り法(解説通り).

LL ans = 202020202020202020;

LL r = N - 1;

rep(l, N){

// l, r を見つける.

LL d = abs(a[l] - (L - a[r]));

repr(i, r, l){

if(d < abs(a[l] - (L - a[i]))) break;

d = abs(a[l] - (L - a[i]));

r = i;

}

// 最小値更新.

ans = min(ans, 2 * L + 2 * d);

}

// 3. 出力.

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

return 0;

}

[入力例]
2 6
2 5

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

[入力例]
2 3
1 2

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

[入力例]
6 16
2 7 8 11 15 16

[出力例]
32

[入力例]
10 55
12 13 17 21 23 31 33 35 39 50

[出力例]
112

[入力例]
20 125
21 33 40 51 57 60 61 66 71 76 87 88 91 93 97 101 102 109 111 115

[出力例]
252

[入力例]
50 2022
303 314 318 333 349 352 369 475 493 506 532 536 537 545 571 608 636 663 702 704 744 767 817 854 873 877 922 981 999 1053 1092 1093 1094 1151 1184 1196 1214 1238 1268 1273 1297 1301 1304 1326 1347 1389 1392 1404 1409 1410

[出力例]
4048

[入力例]
100 20221123
128835 562377 897048 1152450 1199393 1529218 1726509 1913983 2864404 2895053 2926150 3099197 3268192 3681471 3964738 4154313 4508141 4555753 4590559 4744276 4817919 4897461 5277397 5356400 5710006 5936848 6152387 6205833 6263672 6365982 6516841 6602161 6694602 6828548 6972057 7492155 7598137 7821736 7861994 8241001 8268328 8320758 8383872 9171490 9315253 9455053 9606984 9719161 9935027 10149081 10876706 10885955 10897725 10958945 11093741 11206593 11310413 11313808 11534793 11581603 11674632 11894174 11894642 12047576 12074845 12122608 12156598 12435718 12547534 12830845 12891461 13589452 14020667 14034695 14110691 14121735 14351669 14429505 14645628 15004934 15306849 15904377 16201626 16274361 16418629 16871621 16926232 16992253 17197178 18064919 18335010 18344733 18487232 18736047 18877809 19062531 19188601 19794983 19964528 20141094

[出力例]
40453000

[入力例]
250 314159265
9112972 9410829 9743615 11117859 11410003 11563552 12790573 12847345 13673853 13723022 18128097 21179986 21765253 25885744 26655258 29434614 30498934 30565072 31005545 32904736 33291363 33638067 36843825 37484998 39120342 39578010 41276473 42073898 42132396 42205626 42565822 43934228 45788734 45883163 47072579 47608190 48265188 49994174 61682393 62254104 64085415 64229602 64629536 64766735 66871613 68500814 72411276 72481705 72713086 73500005 73582728 74413292 74445316 79695650 82434775 86201587 87744748 88287560 89645968 89684376 90475385 92318594 93643604 95113684 95237729 96049566 96147279 98700156 99041712 99177717 99183984 100783911 101792441 104017323 104027336 104462341 105172235 105290064 108489733 108505278 109026346 109544104 109642592 110788725 110938708 112853720 115013139 117818948 117832475 119787009 120252090 120588494 123472619 123868296 124696017 125356818 125758804 128265366 128400070 130759244 130941323 133233782 135666494 136462099 136578583 137748879 139203836 139797385 141806181 142316105 144680092 145739024 146259225 146857258 148137376 150721159 150780241 150913094 153198200 154123816 154553304 155814954 156538992 156848921 160434739 160819712 162192909 162590128 163274291 163437259 165392437 165563440 165628358 165915439 166382456 167249880 171398471 171559795 171999154 172359846 173195723 175082168 175351537 175557970 176557034 176558208 177264997 177576723 180431386 180659553 182621904 182827207 183065558 183318911 183624887 183974582 184183073 186031061 186050200 191921747 194167703 195246383 195894239 200000536 200186882 200945686 205519593 210161050 211401051 213541610 220132394 227354612 227555002 228828979 229680455 230449950 231426845 237168219 237757594 237979552 238378360 238381351 238612590 238787941 239593125 241313174 243256000 245521314 247658929 248240712 249565805 252830182 253517441 255011300 256235525 258018692 260614119 262953868 263240697 263674422 264525063 264947133 268120373 268131263 268785676 268953364 270897923 271367636 271887314 273392330 274928749 275477763 275489407 276457472 277332334 281025034 281645511 281682352 283350413 283747258 283803716 284535582 285007014 285356826 285407404 285946677 287551595 287585907 288459663 288565068 290742246 290822735 291769684 293202209 293915634 294308274 295633185 296082485 296404123 296863402 300533964 302004624 302621960 302859845 304395456 305599692 305681614 306177876 308900855 310310310

[出力例]
628320224

[入力例]

2 6

2 5

[出力例]

※AtCoderのテストケースより

[入力例]

2 3

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

6 16

2 7 8 11 15 16

[出力例]

[入力例]

10 55

12 13 17 21 23 31 33 35 39 50

[出力例]

112

[入力例]

20 125

21 33 40 51 57 60 61 66 71 76 87 88 91 93 97 101 102 109 111 115

[出力例]

252

[入力例]

50 2022

303 314 318 333 349 352 369 475 493 506 532 536 537 545 571 608 636 663 702 704 744 767 817 854 873 877 922 981 999 1053 1092 1093 1094 1151 1184 1196 1214 1238 1268 1273 1297 1301 1304 1326 1347 1389 1392 1404 1409 1410

[出力例]

4048

[入力例]

100 20221123

128835 562377 897048 1152450 1199393 1529218 1726509 1913983 2864404 2895053 2926150 3099197 3268192 3681471 3964738 4154313 4508141 4555753 4590559 4744276 4817919 4897461 5277397 5356400 5710006 5936848 6152387 6205833 6263672 6365982 6516841 6602161 6694602 6828548 6972057 7492155 7598137 7821736 7861994 8241001 8268328 8320758 8383872 9171490 9315253 9455053 9606984 9719161 9935027 10149081 10876706 10885955 10897725 10958945 11093741 11206593 11310413 11313808 11534793 11581603 11674632 11894174 11894642 12047576 12074845 12122608 12156598 12435718 12547534 12830845 12891461 13589452 14020667 14034695 14110691 14121735 14351669 14429505 14645628 15004934 15306849 15904377 16201626 16274361 16418629 16871621 16926232 16992253 17197178 18064919 18335010 18344733 18487232 18736047 18877809 19062531 19188601 19794983 19964528 20141094

[出力例]

40453000

[入力例]

250 314159265

9112972 9410829 9743615 11117859 11410003 11563552 12790573 12847345 13673853 13723022 18128097 21179986 21765253 25885744 26655258 29434614 30498934 30565072 31005545 32904736 33291363 33638067 36843825 37484998 39120342 39578010 41276473 42073898 42132396 42205626 42565822 43934228 45788734 45883163 47072579 47608190 48265188 49994174 61682393 62254104 64085415 64229602 64629536 64766735 66871613 68500814 72411276 72481705 72713086 73500005 73582728 74413292 74445316 79695650 82434775 86201587 87744748 88287560 89645968 89684376 90475385 92318594 93643604 95113684 95237729 96049566 96147279 98700156 99041712 99177717 99183984 100783911 101792441 104017323 104027336 104462341 105172235 105290064 108489733 108505278 109026346 109544104 109642592 110788725 110938708 112853720 115013139 117818948 117832475 119787009 120252090 120588494 123472619 123868296 124696017 125356818 125758804 128265366 128400070 130759244 130941323 133233782 135666494 136462099 136578583 137748879 139203836 139797385 141806181 142316105 144680092 145739024 146259225 146857258 148137376 150721159 150780241 150913094 153198200 154123816 154553304 155814954 156538992 156848921 160434739 160819712 162192909 162590128 163274291 163437259 165392437 165563440 165628358 165915439 166382456 167249880 171398471 171559795 171999154 172359846 173195723 175082168 175351537 175557970 176557034 176558208 177264997 177576723 180431386 180659553 182621904 182827207 183065558 183318911 183624887 183974582 184183073 186031061 186050200 191921747 194167703 195246383 195894239 200000536 200186882 200945686 205519593 210161050 211401051 213541610 220132394 227354612 227555002 228828979 229680455 230449950 231426845 237168219 237757594 237979552 238378360 238381351 238612590 238787941 239593125 241313174 243256000 245521314 247658929 248240712 249565805 252830182 253517441 255011300 256235525 258018692 260614119 262953868 263240697 263674422 264525063 264947133 268120373 268131263 268785676 268953364 270897923 271367636 271887314 273392330 274928749 275477763 275489407 276457472 277332334 281025034 281645511 281682352 283350413 283747258 283803716 284535582 285007014 285356826 285407404 285946677 287551595 287585907 288459663 288565068 290742246 290822735 291769684 293202209 293915634 294308274 295633185 296082485 296404123 296863402 300533964 302004624 302621960 302859845 304395456 305599692 305681614 306177876 308900855 310310310

[出力例]

628320224

■参照サイト
AtCoder Regular Contest 152

2022年11月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題D (AND OR Equation) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc144/editorial/4307
// 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;
const int LIMIT = 303030;
LL kComb[LIMIT], nComb[LIMIT], mPow2[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

int main(){
    
    // 1. 入力情報.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    
    // 2. 2 の 冪乗 を 保存.
    mPow2[0] = 1;
    rep(i, (int)N + 1) mPow2[i + 1] = (mPow2[i] << 1) % MOD;
    
    // 3. 組み合わせ.
    kComb[0] = K + 1;
    nComb[0] = 1;
    repx(i, 1, (int)N + 1){
        kComb[i] = kComb[i - 1] % MOD * max(0LL, (K + 1 - i + MOD) % MOD) % MOD * mPow(i + 1, MOD - 2) % MOD;
        nComb[i] = nComb[i - 1] % MOD * max(0LL, (N + 1 - i + MOD) % MOD) % MOD * mPow(i, MOD - 2) % MOD;
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, (int)N + 1) ans = (ans + mPow2[i] * nComb[i] % MOD * kComb[i] % MOD) % MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc144/editorial/4307

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

const int LIMIT = 303030;

LL kComb[LIMIT], nComb[LIMIT], mPow2[LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

LL N, K;

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

// 2. 2 の冪乗を保存.

mPow2[0] = 1;

rep(i, (int)N + 1) mPow2[i + 1] = (mPow2[i] << 1) % MOD;

// 3. 組み合わせ.

kComb[0] = K + 1;

nComb[0] = 1;

repx(i, 1, (int)N + 1){

kComb[i] = kComb[i - 1] % MOD * max(0LL, (K + 1 - i + MOD) % MOD) % MOD * mPow(i + 1, MOD - 2) % MOD;

nComb[i] = nComb[i - 1] % MOD * max(0LL, (N + 1 - i + MOD) % MOD) % MOD * mPow(i, MOD - 2) % MOD;

}

// 4. 集計.

LL ans = 0;

rep(i, (int)N + 1) ans = (ans + mPow2[i] * nComb[i] % MOD * kComb[i] % MOD) % MOD;

// 5. 出力.

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

return 0;

}

[入力例]
2 1

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

[入力例]
2 2

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

[入力例]
100 123456789123456789

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

[入力例]
3 2

[出力例]
33

[入力例]
11 5

[出力例]
71000

[入力例]
2022 1123

[出力例]
560596535

[入力例]
77777 202207162100

[出力例]
836824508

[入力例]

2 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

100 123456789123456789

[出力例]

34663745

※AtCoderテストケースより

[入力例]

3 2

[出力例]

[入力例]

11 5

[出力例]

71000

[入力例]

2022 1123

[出力例]

560596535

[入力例]

77777 202207162100

[出力例]

836824508

■参照サイト
AtCoder Regular Contest 144

2022年11月21日

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

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題C (K Derangement) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 辞書順最小の順列を取得できることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc144/editorial/4440
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 例外.
    if(N < 2 * K){
        puts("-1");
        return 0;
    }
    
    // 3. 貪欲アルゴリズム(解説通り).
    vi ans;
    set<int> st;
    repx(i, 1, N + 1) st.insert(i);
    repx(i, 1, N + 1){
        // 操作 1.
        int j = i + K;
        if(st.count(j) && j > N - K){
            ans.pb(j);
            st.erase(j);
            continue;
        }
        
        // 操作 2.
        int x1 = N + 1, x2 = N + 1, x = N + 1;
        if(i + K <= N) x1 = *st.lower_bound(i + K);
        if(i - K >= 1) x2 = *st.lower_bound(1);
        if(abs(x1 - i) >= K) x = min(x, x1);
        if(abs(x2 - i) >= K) x = min(x, x2);
        ans.pb(x);
        st.erase(x);
    }
    
    // 4. 出力.
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc144/editorial/4440

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 例外.

if(N < 2 * K){

puts("-1");

return 0;

}

// 3. 貪欲アルゴリズム(解説通り).

vi ans;

set<int> st;

repx(i, 1, N + 1) st.insert(i);

repx(i, 1, N + 1){

// 操作 1.

int j = i + K;

if(st.count(j) && j > N - K){

ans.pb(j);

st.erase(j);

continue;

}

// 操作 2.

int x1 = N + 1, x2 = N + 1, x = N + 1;

if(i + K <= N) x1 = *st.lower_bound(i + K);

if(i - K >= 1) x2 = *st.lower_bound(1);

if(abs(x1 - i) >= K) x = min(x, x1);

if(abs(x2 - i) >= K) x = min(x, x2);

ans.pb(x);

st.erase(x);

}

// 4. 出力.

rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3 1

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

[入力例]
8 3

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

[入力例]
8 6

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

[入力例]
5 2

[出力例]
3 4 5 1 2

[入力例]
15 7

[出力例]
8 9 10 11 12 13 14 15 1 2 3 4 5 6 7

[入力例]
23 11

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

[入力例]
100 33

[出力例]
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 67

[入力例]
250 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 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

[入力例]
314 15

[出力例]
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285

[入力例]

3 1

[出力例]

2 3 1

※AtCoderのテストケースより

[入力例]

8 3

[出力例]

4 5 6 7 8 1 2 3

※AtCoderのテストケースより

[入力例]

8 6

[出力例]

-1

※AtCoderのテストケースより

[入力例]

5 2

[出力例]

3 4 5 1 2

[入力例]

15 7

[出力例]

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

[入力例]

23 11

[出力例]

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

[入力例]

100 33

[出力例]

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

[入力例]

250 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 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

[入力例]

314 15

[出力例]

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285

■参照サイト
AtCoder Regular Contest 144

2022年11月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題D (Add to Square) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 操作後のマス目の状態を抽出できる解説のロジックが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc135/editorial/3381
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL a[505][505], rSum[505], cSum[505], o1[505][505], o2[505][505], o3[505][505], o4[505][505], ans[505][505];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        rep(j, W){
            scanf("%lld", &a[i][j]);
            
            // (-1) の (i + j)乗 を 考慮.
            if((i + j) & 1) a[i][j] *= -1;
        }
    }
    
    // 2. 各行, 列の合計.
    rep(i, H) rep(j, W) rSum[i] += a[i][j];
    rep(j, W) rep(i, H) cSum[j] += a[i][j];
    
    // 3. 分類.
    // 3-1. 操作 1, 操作 2.
    rep(i, H){
        rep(j, W){
            if(rSum[i] < 0 && cSum[j] < 0) ++o1[i][j];
            if(rSum[i] > 0 && cSum[j] > 0) ++o2[i][j];
        }
    }
    
    // 3-2. 操作 3.
    rep(i, H) repx(j, i + 1, H) if((rSum[i] > 0 && rSum[j] < 0) || (rSum[i] < 0 && rSum[j] > 0)) ++o3[i][j];
    
    // 3-3. 操作 4.
    rep(i, W) repx(j, i + 1, W) if((cSum[i] > 0 && cSum[j] < 0) || (cSum[i] < 0 && cSum[j] > 0)) ++o4[i][j];
    
    // 4. 操作.
    // 4-1. 操作 1, 操作 2.
    rep(i, H){
        int wMax = 0;
        rep(j, W){
            if(rSum[i] != 0){
                if(o1[i][j] || o2[i][j]){
                    LL x = rSum[i];
                    LL y = cSum[j];
                    if(abs(x) <= abs(y)){
                        rSum[i] -= x;
                        cSum[j] -= x;
                        ans[i][j] -= x;
                    }
                    if(abs(x) > abs(y)){
                        rSum[i] -= y;
                        cSum[j] -= y;
                        ans[i][j] -= y;
                    }
                }
                
                // 更新最終列.
                wMax = j;
            }
        }
        
        // i行目の総和が, 0 か？
        if(rSum[i] != 0){
            LL res = rSum[i];
            rSum[i] -= res;
            cSum[wMax] -= res;
            ans[i][wMax] -= res;
        }
    }
    
    // 4-2. 操作 3.
    rep(i, H){
        repx(j, i + 1, H){
            if(o3[i][j]){
                LL x1 = rSum[i];
                LL x2 = rSum[j];
                if((x1 > 0 && x2 < 0) || (x2 > 0 && x1 < 0)){
                    if(abs(x1) <= abs(x2)){
                        rSum[i] -= x1;
                        rSum[j] += x1;
                        ans[i][0] -= x1;
                        ans[j][0] += x1;
                    }
                    if(abs(x1) > abs(x2)){
                        rSum[i] += x2;
                        rSum[j] -= x2;
                        ans[i][0] += x2;
                        ans[j][0] -= x2;
                    }
                }
            }
        }
    }
    
    // 4-3. 操作 4.
    rep(i, W){
        repx(j, i + 1, W){
            if(o4[i][j]){
                LL y1 = cSum[i];
                LL y2 = cSum[j];
                if((y1 > 0 && y2 < 0) || (y2 > 0 && y1 < 0)){
                    if(abs(y1) <= abs(y2)){
                        cSum[i] -= y1;
                        cSum[j] += y1;
                        ans[0][i] -= y1;
                        ans[0][j] += y1;
                    }
                    if(abs(y1) > abs(y2)){
                        cSum[i] += y2;
                        cSum[j] -= y2;
                        ans[0][i] += y2;
                        ans[0][j] -= y2;
                    }
                }
            }
        }
    }
    
    // 5. 符号の反映.
    LL t = 0;
    rep(i, H){
        rep(j, W){
            // (-1) の (i + j + 1)乗 を 考慮.
            if((i + j + 1) & 1) ans[i][j] *= -1;
            
            // 集計.
            t += abs(ans[i][j]);
        }
    }
    
    // 6. 出力.
    printf("%lld\n", t);
    rep(i, H) rep(j, W) printf("%lld%s", ans[i][j], (j < W - 1) ? " " : "\n");
    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

// 解き直し.

// https://atcoder.jp/contests/arc135/editorial/3381

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

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

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

LL a[505][505], rSum[505], cSum[505], o1[505][505], o2[505][505], o3[505][505], o4[505][505], ans[505][505];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

rep(j, W){

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

// (-1) の (i + j)乗を考慮.

if((i + j) & 1) a[i][j] *= -1;

}

// 2. 各行, 列の合計.

rep(i, H) rep(j, W) rSum[i] += a[i][j];

rep(j, W) rep(i, H) cSum[j] += a[i][j];

// 3. 分類.

// 3-1. 操作 1, 操作 2.

rep(i, H){

rep(j, W){

if(rSum[i] < 0 && cSum[j] < 0) ++o1[i][j];

if(rSum[i] > 0 && cSum[j] > 0) ++o2[i][j];

}

// 3-2. 操作 3.

rep(i, H) repx(j, i + 1, H) if((rSum[i] > 0 && rSum[j] < 0) || (rSum[i] < 0 && rSum[j] > 0)) ++o3[i][j];

// 3-3. 操作 4.

rep(i, W) repx(j, i + 1, W) if((cSum[i] > 0 && cSum[j] < 0) || (cSum[i] < 0 && cSum[j] > 0)) ++o4[i][j];

// 4. 操作.

// 4-1. 操作 1, 操作 2.

rep(i, H){

int wMax = 0;

rep(j, W){

if(rSum[i] != 0){

if(o1[i][j] || o2[i][j]){

LL x = rSum[i];

LL y = cSum[j];

if(abs(x) <= abs(y)){

rSum[i] -= x;

cSum[j] -= x;

ans[i][j] -= x;

}

if(abs(x) > abs(y)){

rSum[i] -= y;

cSum[j] -= y;

ans[i][j] -= y;

}

// 更新最終列.

wMax = j;

}

// i行目の総和が, 0 か？

if(rSum[i] != 0){

LL res = rSum[i];

rSum[i] -= res;

cSum[wMax] -= res;

ans[i][wMax] -= res;

}

// 4-2. 操作 3.

rep(i, H){

repx(j, i + 1, H){

if(o3[i][j]){

LL x1 = rSum[i];

LL x2 = rSum[j];

if((x1 > 0 && x2 < 0) || (x2 > 0 && x1 < 0)){

if(abs(x1) <= abs(x2)){

rSum[i] -= x1;

rSum[j] += x1;

ans[i][0] -= x1;

ans[j][0] += x1;

}

if(abs(x1) > abs(x2)){

rSum[i] += x2;

rSum[j] -= x2;

ans[i][0] += x2;

ans[j][0] -= x2;

}

// 4-3. 操作 4.

rep(i, W){

repx(j, i + 1, W){

if(o4[i][j]){

LL y1 = cSum[i];

LL y2 = cSum[j];

if((y1 > 0 && y2 < 0) || (y2 > 0 && y1 < 0)){

if(abs(y1) <= abs(y2)){

cSum[i] -= y1;

cSum[j] += y1;

ans[0][i] -= y1;

ans[0][j] += y1;

}

if(abs(y1) > abs(y2)){

cSum[i] += y2;

cSum[j] -= y2;

ans[0][i] += y2;

ans[0][j] -= y2;

}

// 5. 符号の反映.

LL t = 0;

rep(i, H){

rep(j, W){

// (-1) の (i + j + 1)乗を考慮.

if((i + j + 1) & 1) ans[i][j] *= -1;

// 集計.

t += abs(ans[i][j]);

}

// 6. 出力.

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

rep(i, H) rep(j, W) printf("%lld%s", ans[i][j], (j < W - 1) ? " " : "\n");

return 0;

}

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

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

[入力例]
2 2
1000000000 -1000000000
-1000000000 1000000000

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

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

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

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

[出力例]
18
0 1 0 4
-5 0 0 0
1 0 6 -1

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

[出力例]
66
-3 -1 8 0 -9
7 0 0 -8 11
0 -10 0 0 0
0 9 0 0 0

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

[出力例]
206
2 0 -34 0 -9 -47 -8 6 15 5
0 -13 11 0 0 0 0 0 0 0
0 0 -15 0 0 0 0 0 0 0
-11 0 0 0 0 0 0 0 0 0
3 0 0 -3 0 -18 0 0 0 0
0 0 5 0 0 0 0 0 0 0
0 0 -1 0 0 0 0 0 0 0

[入力例]
11 13
-81 15 71 2 -98 76 82 -40 -60 29 72 -88 90
36 66 28 -62 -54 64 -12 16 56 -63 -1 -50 -23
-81 -48 51 -37 77 -66 -33 -115 -78 8 36 28 -56
-105 -17 81 97 -70 88 17 51 50 -88 26 -69 26
66 -101 88 116 109 -62 15 -111 35 77 -20 -10 118
-103 -50 55 -10 61 81 -6 -64 -32 -121 -76 -12 67
96 -118 -29 -98 10 -97 -92 61 -9 3 -22 -107 -19
95 54 90 81 58 35 -45 113 -56 -22 -64 -122 98
84 69 -120 -11 123 69 -117 15 82 -63 99 37 71
110 15 -63 -123 97 113 21 -19 -115 -66 -72 -120 -39
39 38 -17 -23 -77 65 -103 59 9 -58 -34 61 22

[出力例]
2524
82 0 0 0 0 0 0 0 0 46 243 294 97
0 0 59 0 0 0 0 0 0 0 0 0 0
8 -138 0 0 0 0 0 0 0 0 0 0 0
0 37 0 0 0 0 0 0 0 0 0 0 0
0 -38 0 -34 52 -378 0 0 0 0 0 0 0
0 0 88 0 0 0 54 0 0 0 0 0 0
0 0 0 0 0 -18 0 -228 45 0 0 0 0
0 0 0 0 0 0 37 0 0 0 0 0 0
0 0 0 0 0 0 0 0 31 0 75 0 0
0 0 0 0 0 0 132 0 0 -7 0 0 0
0 0 0 0 0 0 0 0 0 303 0 0 0

[入力例]
20 22
-1901 -8626 -7663 -1030 1536 2767 1835 8925 709 1856 8515 -7283 -5161 9289 1256 1769 1582 -7961 -1765 5605 -5709 -1182
5956 -5305 -7753 -718 -8771 -9760 -9201 -1816 6573 2061 -1222 -7185 1126 -3599 212 -5582 -8987 -3713 -2281 9572 6851 -9210
6385 -1075 -3196 -2612 7087 1501 2806 -6331 3812 182 3918 -2102 980 -5110 -3217 -9100 8725 -8757 6277 -1237 -3818 1931
1918 6290 -5500 8719 -7779 -9918 -1061 -5121 2885 -9225 -1325 7992 -8115 -1851 -7827 -2091 -7820 -1951 8205 -1637 -999 -7792
-1691 7737 8620 128 2211 1089 -7957 -181 -9958 1912 2788 1882 7788 -1169 7126 -7122 -3631 -7231 6591 -676 3591 1120
3237 2995 3628 9657 -9556 6763 268 3567 -6026 1713 1710 -2272 -9331 5575 1020 -1121 -7925 -6802 8917 -130 2336 171
1273 -2202 8962 1251 9660 7721 -2531 -7978 -2893 1565 557 7188 -917 5131 -3132 -7210 2031 -9555 -9711 9215 -975 -238
5360 -6119 6151 3012 -2615 9951 1721 5510 -5212 6169 8380 5121 -9082 7116 -8261 1229 -8810 -9063 6689 9118 -8753 1991
159 -2763 -2170 3802 2996 2392 -312 -1636 7211 5756 -1661 -2337 1110 -3171 8689 -5966 -6810 -1917 3591 -3079 2255 6386
-3661 -8877 5780 -9561 812 -8151 -1725 1728 -5017 -1875 -7318 -8910 -1595 8187 -2367 -5873 -2855 1180 -8081 -1158 2922 7992
7106 -1022 7118 -2881 -2931 7878 2986 7187 73 -5637 -620 8128 1803 -9835 1529 -806 1111 -3963 108 -5059 -1759 -1183
1860 -1871 -1150 -3873 -18 -7002 1663 -775 -9318 -1690 2275 1626 -3805 -7996 -258 9266 6363 -6370 -7226 518 72 -193
-9275 2029 -7779 -7915 -3319 8902 -1276 3112 -2581 -2115 -7776 -2119 -587 -1151 7350 -9798 3599 9211 -1516 -2531 3011 -5266
6680 -921 1338 -5866 -9713 -621 3117 -160 351 6801 8177 6021 -372 -7172 -3822 756 3027 1003 7593 -9662 -8336 9695
-6316 -7796 -1725 9533 -3181 -698 6863 3033 -9761 -9972 -1931 -1515 3595 -952 9035 -2198 -8793 1711 -5736 3185 -8583 -3997
-3019 3301 -8613 9511 -711 -6038 -2736 8393 9711 1325 1180 1309 1259 9151 7263 1265 -1901 -739 -818 -9901 -3812 3918
-5887 7182 -8770 1517 6105 232 2118 5191 -1819 8521 -9512 -7599 -9961 -7185 126 -2650 -6921 1797 7135 5158 -7291 -2113
1685 1100 -2097 -9796 -7157 6196 7131 -7520 1679 3810 2015 -7926 8832 -1113 -6221 -5712 -1396 -3613 -1163 2928 1087 -1173
-7112 -9828 -1826 -2532 7235 -5829 6752 3306 -8525 317 9111 -9588 8618 2109 -6125 -9616 -7126 995 1056 7613 8353 5271
-2520 388 -3667 -8826 -3711 2712 3107 -1525 -5860 9990 -8036 -2278 -9559 -1690 5507 631 8273 8817 2116 6150 -3862 -6027

[出力例]
443074
-10895 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
17758 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 -7345 3454 0 51670 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 -10833 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 14115 0 3874 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 -5126 0 0 16694 0 8843 -1175 0 0 0 0 0 0 0 0 0
-2564 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -36735 11732 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 -6920 10671 0 0 0 0 0 0 0
2213 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 23717 0 0 0 0 0 0 0
1325 0 0 -7002 0 -491 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 12508 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 -8166 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 16867 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3003 20689 0 0 0 0 0 0
0 0 0 0 0 3791 0 12347 -13498 0 -2447 0 0 0 0 0 0 0 -7921 4724 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -7672 0 -19542
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -24776 3417 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2381 4419 0 0 -1569 18185

[入力例]
30 33
-88 -128 -368 -58 -315 168 -5 -837 -390 398 509 235 -202 825 -598 -755 306 357 -131 -778 905 -771 285 -587 -291 298 -162 852 361 -802 -561 -109 -512
100 752 -235 -583 -60 -852 591 -652 -367 205 65 -109 -733 -699 -820 876 -299 105 -582 285 -691 -659 -120 352 31 -33 -508 -59 -151 -772 -270 958 -797
-565 -650 -921 881 -970 162 328 936 602 555 -987 558 -637 -83 725 -687 859 581 -893 -682 857 799 722 -536 -233 933 537 587 -637 926 956 -982 -975
235 -229 -367 953 832 -373 266 123 -86 806 -868 57 -883 -190 -526 -1000 -52 551 611 -765 -162 -751 607 -657 351 -756 -826 -206 -226 -353 835 -158 -392
-512 -376 121 -873 -331 -321 -862 -252 776 595 756 -578 527 -655 953 -757 -386 782 -586 313 -993 -122 -758 558 -657 565 751 159 -896 388 103 -855 227
-515 -516 966 -277 -52 -825 855 90 123 159 759 -568 -871 -959 798 922 863 -715 500 296 -6 -503 -526 95 -753 -528 -235 -113 -236 -352 -682 -553 -399
-735 -126 73 -37 -63 -961 186 -551 -970 859 -300 577 -553 -151 937 -958 -620 -555 708 858 -863 801 670 795 -838 250 -659 -808 -252 358 972 523 715
979 278 682 255 -850 758 -505 558 65 -233 -258 -398 252 -659 -360 -52 553 -515 -577 -591 -259 -376 897 927 885 -831 -516 -300 316 -6 199 359 595
530 -155 378 -216 786 357 885 15 739 529 851 725 -277 665 -890 -528 802 835 552 -258 222 -237 987 -713 55 -918 708 890 -567 -89 -931 929 -322
-535 -528 -387 718 920 -555 77 28 820 -152 -396 985 -260 553 -153 -553 128 -662 839 570 715 262 -671 285 371 505 -153 -252 26 -319 -101 276 258
212 -382 -22 56 -100 -858 -782 553 156 582 967 575 23 -700 855 95 872 -816 533 -291 -615 -898 -259 973 -738 -866 -555 605 507 269 865 833 113
-556 691 -533 -205 -232 -661 75 508 538 -277 -156 513 -866 -125 -628 -522 -555 -615 -172 -319 170 -316 755 -252 825 -821 -676 225 109 535 595 78 29
-390 -896 -625 757 289 -599 572 -906 112 -775 -813 233 -708 -956 -575 591 655 -786 -898 -662 -779 -933 935 -801 361 553 297 -775 -657 385 988 665 362
-875 115 -637 -587 331 200 -983 -653 255 183 776 761 613 31 -8 -858 -502 531 127 -89 875 -319 -977 529 502 565 -329 -389 928 -650 370 369 956
-221 655 71 -308 368 527 377 -500 955 -188 923 -785 636 -150 11 65 359 767 -771 958 -228 90 -536 205 -650 319 -30 -596 228 -513 538 -5 523
958 890 -399 738 -61 -57 -225 -950 532 755 829 -283 693 -539 516 -157 -630 -685 -293 -596 277 -590 -770 -395 550 -892 189 -8 -153 -920 666 373 -593
-620 875 -350 75 -980 937 602 -537 -571 879 323 530 962 503 -627 -717 878 -136 -555 835 -763 -358 -511 -685 -578 -765 -280 95 -880 885 331 -56 -831
-272 -952 735 -505 -637 759 957 587 870 150 228 -889 828 559 -552 -515 -297 -156 261 -155 -178 695 521 138 -663 193 -76 -52 -338 -992 950 97 -201
-653 -658 -869 695 553 -596 -75 -825 855 107 -92 527 531 -903 -552 -370 -1000 -653 279 -835 560 -255 -651 525 653 67 556 201 -569 -538 -755 -85 -668
-576 -565 -551 -5 528 576 93 -275 -988 -665 -795 -711 285 -535 577 -988 -15 650 671 -327 -568 235 -568 -569 -850 -979 -502 88 659 836 -251 29 -698
-198 556 -197 93 -233 529 -823 57 529 795 230 265 337 695 265 51 190 835 -296 91 -655 -171 -619 -852 -966 650 -372 666 -36 698 -216 -518 777
36 -91 -335 51 -675 -595 -669 775 -785 -702 607 315 783 728 388 268 955 655 -273 505 -937 521 958 321 833 587 -537 -259 506 828 -777 157 916
975 -671 -755 193 -783 -365 -356 -16 -352 819 -865 583 323 -25 -230 -280 66 -11 -885 860 -876 -80 838 -868 -713 -623 -255 -671 713 753 225 -20 263
-788 686 -31 907 -598 -35 -209 -527 501 565 659 250 99 -263 587 173 -30 -365 156 251 707 295 -96 718 -736 -500 207 -870 -975 -259 913 903 -893
-63 -262 25 258 -663 -583 631 570 -268 -952 -599 117 502 738 -700 116 179 580 -518 508 -113 -759 713 765 851 218 -802 -502 -600 -873 -815 822 -596
-91 -712 800 137 -518 560 -286 -505 288 -971 776 -380 520 155 921 -196 593 606 957 912 26 -552 790 796 -123 -589 815 230 -915 -690 -705 -855 839
319 -222 53 336 -231 952 535 570 310 -311 -690 612 555 550 -550 865 605 -32 178 15 -835 -605 118 -357 -557 -583 -900 -569 -959 -592 -957 556 102
979 527 -75 -697 39 -675 961 -52 987 137 387 365 282 -905 -70 -868 -787 767 -39 582 289 -551 -289 930 -622 185 -171 710 -101 -595 587 -567 -920
173 -12 536 866 369 -767 985 -685 339 709 90 102 895 -373 -551 -588 -336 707 950 588 -951 269 -69 962 -517 825 588 68 585 355 -253 705 -179
19 -821 522 -86 882 -922 588 78 -512 -511 -617 -992 -277 621 782 -798 659 327 69 596 -579 -355 -737 -259 927 755 -595 -936 555 -91 525 -650 -391

[出力例]
90649
0 -435 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1542 0 0 0 0 -612 1541 -266 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-934 0 -3005 591 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 -1313 984 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 -338 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 831 -1279 0 0 0 -2826 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2326 -140 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1553 -1371 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 315 0 0 0 2362 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -337 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 87 0 0 0 2215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -285 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 630 0 0 0 0 -266 2091 -1044 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1683 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2012 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1684 0 -2207 1511 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1468 411 0 1976 -2955 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1633 -365 1176 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -519 0 0 1180 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -344 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3630 0 0 0 -3093 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1811 0 0 0 0 0 -1259
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2245 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2456
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1008 2589 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1473 0 -2393 2875 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -788 3301 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2109 35 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1077 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1252 -1587 3025

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

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

[入力例]

2 3

1 2 3

4 5 6

[出力例]

0 -3 -1

3 0 2

※AtCoderのテストケースより

[入力例]

2 2

1000000000 -1000000000

-1000000000 1000000000

[出力例]

4000000000

2000000000 0

0 2000000000

※AtCoderのテストケースより

[入力例]

3 4

0 2 0 -2

-3 -1 2 0

-3 -3 2 2

[出力例]

0 0 0 0

※AtCoderのテストケースより

[入力例]

3 4

1 3 2 5

2 5 1 3

7 3 5 1

[出力例]

0 1 0 4

-5 0 0 0

1 0 6 -1

[入力例]

4 5

1 -2 3 4 -5

6 7 8 -9 10

2 -3 4 5 6

7 8 -9 10 11

[出力例]

-3 -1 8 0 -9

7 0 0 -8 11

0 -10 0 0 0

0 9 0 0 0

[入力例]

7 10

7 10 -12 10 11 -18 11 9 2 6

13 7 13 3 3 18 13 -7 9 6

18 11 -8 12 11 -10 8 14 0 17

10 7 11 9 13 10 6 9 -6 10

22 -15 1 -5 -14 13 0 1 12 3

20 0 17 2 5 10 19 25 -12 7

12 21 -6 -6 4 -12 11 9 -8 2

[出力例]

206

2 0 -34 0 -9 -47 -8 6 15 5

0 -13 11 0 0 0 0 0 0 0

0 0 -15 0 0 0 0 0 0 0

-11 0 0 0 0 0 0 0 0 0

3 0 0 -3 0 -18 0 0 0 0

0 0 5 0 0 0 0 0 0 0

0 0 -1 0 0 0 0 0 0 0

[入力例]

11 13

-81 15 71 2 -98 76 82 -40 -60 29 72 -88 90

36 66 28 -62 -54 64 -12 16 56 -63 -1 -50 -23

-81 -48 51 -37 77 -66 -33 -115 -78 8 36 28 -56

-105 -17 81 97 -70 88 17 51 50 -88 26 -69 26

66 -101 88 116 109 -62 15 -111 35 77 -20 -10 118

-103 -50 55 -10 61 81 -6 -64 -32 -121 -76 -12 67

96 -118 -29 -98 10 -97 -92 61 -9 3 -22 -107 -19

95 54 90 81 58 35 -45 113 -56 -22 -64 -122 98

84 69 -120 -11 123 69 -117 15 82 -63 99 37 71

110 15 -63 -123 97 113 21 -19 -115 -66 -72 -120 -39

39 38 -17 -23 -77 65 -103 59 9 -58 -34 61 22

[出力例]

2524

82 0 0 0 0 0 0 0 0 46 243 294 97

0 0 59 0 0 0 0 0 0 0 0 0 0

8 -138 0 0 0 0 0 0 0 0 0 0 0

0 37 0 0 0 0 0 0 0 0 0 0 0

0 -38 0 -34 52 -378 0 0 0 0 0 0 0

0 0 88 0 0 0 54 0 0 0 0 0 0

0 0 0 0 0 -18 0 -228 45 0 0 0 0

0 0 0 0 0 0 37 0 0 0 0 0 0

0 0 0 0 0 0 0 0 31 0 75 0 0

0 0 0 0 0 0 132 0 0 -7 0 0 0

0 0 0 0 0 0 0 0 0 303 0 0 0

[入力例]

20 22

-1901 -8626 -7663 -1030 1536 2767 1835 8925 709 1856 8515 -7283 -5161 9289 1256 1769 1582 -7961 -1765 5605 -5709 -1182

5956 -5305 -7753 -718 -8771 -9760 -9201 -1816 6573 2061 -1222 -7185 1126 -3599 212 -5582 -8987 -3713 -2281 9572 6851 -9210

6385 -1075 -3196 -2612 7087 1501 2806 -6331 3812 182 3918 -2102 980 -5110 -3217 -9100 8725 -8757 6277 -1237 -3818 1931

1918 6290 -5500 8719 -7779 -9918 -1061 -5121 2885 -9225 -1325 7992 -8115 -1851 -7827 -2091 -7820 -1951 8205 -1637 -999 -7792

-1691 7737 8620 128 2211 1089 -7957 -181 -9958 1912 2788 1882 7788 -1169 7126 -7122 -3631 -7231 6591 -676 3591 1120

3237 2995 3628 9657 -9556 6763 268 3567 -6026 1713 1710 -2272 -9331 5575 1020 -1121 -7925 -6802 8917 -130 2336 171

1273 -2202 8962 1251 9660 7721 -2531 -7978 -2893 1565 557 7188 -917 5131 -3132 -7210 2031 -9555 -9711 9215 -975 -238

5360 -6119 6151 3012 -2615 9951 1721 5510 -5212 6169 8380 5121 -9082 7116 -8261 1229 -8810 -9063 6689 9118 -8753 1991

159 -2763 -2170 3802 2996 2392 -312 -1636 7211 5756 -1661 -2337 1110 -3171 8689 -5966 -6810 -1917 3591 -3079 2255 6386

-3661 -8877 5780 -9561 812 -8151 -1725 1728 -5017 -1875 -7318 -8910 -1595 8187 -2367 -5873 -2855 1180 -8081 -1158 2922 7992

7106 -1022 7118 -2881 -2931 7878 2986 7187 73 -5637 -620 8128 1803 -9835 1529 -806 1111 -3963 108 -5059 -1759 -1183

1860 -1871 -1150 -3873 -18 -7002 1663 -775 -9318 -1690 2275 1626 -3805 -7996 -258 9266 6363 -6370 -7226 518 72 -193

-9275 2029 -7779 -7915 -3319 8902 -1276 3112 -2581 -2115 -7776 -2119 -587 -1151 7350 -9798 3599 9211 -1516 -2531 3011 -5266

6680 -921 1338 -5866 -9713 -621 3117 -160 351 6801 8177 6021 -372 -7172 -3822 756 3027 1003 7593 -9662 -8336 9695

-6316 -7796 -1725 9533 -3181 -698 6863 3033 -9761 -9972 -1931 -1515 3595 -952 9035 -2198 -8793 1711 -5736 3185 -8583 -3997

-3019 3301 -8613 9511 -711 -6038 -2736 8393 9711 1325 1180 1309 1259 9151 7263 1265 -1901 -739 -818 -9901 -3812 3918

-5887 7182 -8770 1517 6105 232 2118 5191 -1819 8521 -9512 -7599 -9961 -7185 126 -2650 -6921 1797 7135 5158 -7291 -2113

1685 1100 -2097 -9796 -7157 6196 7131 -7520 1679 3810 2015 -7926 8832 -1113 -6221 -5712 -1396 -3613 -1163 2928 1087 -1173

-7112 -9828 -1826 -2532 7235 -5829 6752 3306 -8525 317 9111 -9588 8618 2109 -6125 -9616 -7126 995 1056 7613 8353 5271

-2520 388 -3667 -8826 -3711 2712 3107 -1525 -5860 9990 -8036 -2278 -9559 -1690 5507 631 8273 8817 2116 6150 -3862 -6027

[出力例]

443074

-10895 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

17758 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 -7345 3454 0 51670 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 -10833 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 14115 0 3874 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 -5126 0 0 16694 0 8843 -1175 0 0 0 0 0 0 0 0 0

-2564 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 -36735 11732 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 -6920 10671 0 0 0 0 0 0 0

2213 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 23717 0 0 0 0 0 0 0

1325 0 0 -7002 0 -491 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 12508 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 -8166 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 16867 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3003 20689 0 0 0 0 0 0

0 0 0 0 0 3791 0 12347 -13498 0 -2447 0 0 0 0 0 0 0 -7921 4724 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -7672 0 -19542

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -24776 3417 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2381 4419 0 0 -1569 18185

[入力例]

30 33

-88 -128 -368 -58 -315 168 -5 -837 -390 398 509 235 -202 825 -598 -755 306 357 -131 -778 905 -771 285 -587 -291 298 -162 852 361 -802 -561 -109 -512

100 752 -235 -583 -60 -852 591 -652 -367 205 65 -109 -733 -699 -820 876 -299 105 -582 285 -691 -659 -120 352 31 -33 -508 -59 -151 -772 -270 958 -797

-565 -650 -921 881 -970 162 328 936 602 555 -987 558 -637 -83 725 -687 859 581 -893 -682 857 799 722 -536 -233 933 537 587 -637 926 956 -982 -975

235 -229 -367 953 832 -373 266 123 -86 806 -868 57 -883 -190 -526 -1000 -52 551 611 -765 -162 -751 607 -657 351 -756 -826 -206 -226 -353 835 -158 -392

-512 -376 121 -873 -331 -321 -862 -252 776 595 756 -578 527 -655 953 -757 -386 782 -586 313 -993 -122 -758 558 -657 565 751 159 -896 388 103 -855 227

-515 -516 966 -277 -52 -825 855 90 123 159 759 -568 -871 -959 798 922 863 -715 500 296 -6 -503 -526 95 -753 -528 -235 -113 -236 -352 -682 -553 -399

-735 -126 73 -37 -63 -961 186 -551 -970 859 -300 577 -553 -151 937 -958 -620 -555 708 858 -863 801 670 795 -838 250 -659 -808 -252 358 972 523 715

979 278 682 255 -850 758 -505 558 65 -233 -258 -398 252 -659 -360 -52 553 -515 -577 -591 -259 -376 897 927 885 -831 -516 -300 316 -6 199 359 595

530 -155 378 -216 786 357 885 15 739 529 851 725 -277 665 -890 -528 802 835 552 -258 222 -237 987 -713 55 -918 708 890 -567 -89 -931 929 -322

-535 -528 -387 718 920 -555 77 28 820 -152 -396 985 -260 553 -153 -553 128 -662 839 570 715 262 -671 285 371 505 -153 -252 26 -319 -101 276 258

212 -382 -22 56 -100 -858 -782 553 156 582 967 575 23 -700 855 95 872 -816 533 -291 -615 -898 -259 973 -738 -866 -555 605 507 269 865 833 113

-556 691 -533 -205 -232 -661 75 508 538 -277 -156 513 -866 -125 -628 -522 -555 -615 -172 -319 170 -316 755 -252 825 -821 -676 225 109 535 595 78 29

-390 -896 -625 757 289 -599 572 -906 112 -775 -813 233 -708 -956 -575 591 655 -786 -898 -662 -779 -933 935 -801 361 553 297 -775 -657 385 988 665 362

-875 115 -637 -587 331 200 -983 -653 255 183 776 761 613 31 -8 -858 -502 531 127 -89 875 -319 -977 529 502 565 -329 -389 928 -650 370 369 956

-221 655 71 -308 368 527 377 -500 955 -188 923 -785 636 -150 11 65 359 767 -771 958 -228 90 -536 205 -650 319 -30 -596 228 -513 538 -5 523

958 890 -399 738 -61 -57 -225 -950 532 755 829 -283 693 -539 516 -157 -630 -685 -293 -596 277 -590 -770 -395 550 -892 189 -8 -153 -920 666 373 -593

-620 875 -350 75 -980 937 602 -537 -571 879 323 530 962 503 -627 -717 878 -136 -555 835 -763 -358 -511 -685 -578 -765 -280 95 -880 885 331 -56 -831

-272 -952 735 -505 -637 759 957 587 870 150 228 -889 828 559 -552 -515 -297 -156 261 -155 -178 695 521 138 -663 193 -76 -52 -338 -992 950 97 -201

-653 -658 -869 695 553 -596 -75 -825 855 107 -92 527 531 -903 -552 -370 -1000 -653 279 -835 560 -255 -651 525 653 67 556 201 -569 -538 -755 -85 -668

-576 -565 -551 -5 528 576 93 -275 -988 -665 -795 -711 285 -535 577 -988 -15 650 671 -327 -568 235 -568 -569 -850 -979 -502 88 659 836 -251 29 -698

-198 556 -197 93 -233 529 -823 57 529 795 230 265 337 695 265 51 190 835 -296 91 -655 -171 -619 -852 -966 650 -372 666 -36 698 -216 -518 777

36 -91 -335 51 -675 -595 -669 775 -785 -702 607 315 783 728 388 268 955 655 -273 505 -937 521 958 321 833 587 -537 -259 506 828 -777 157 916

975 -671 -755 193 -783 -365 -356 -16 -352 819 -865 583 323 -25 -230 -280 66 -11 -885 860 -876 -80 838 -868 -713 -623 -255 -671 713 753 225 -20 263

-788 686 -31 907 -598 -35 -209 -527 501 565 659 250 99 -263 587 173 -30 -365 156 251 707 295 -96 718 -736 -500 207 -870 -975 -259 913 903 -893

-63 -262 25 258 -663 -583 631 570 -268 -952 -599 117 502 738 -700 116 179 580 -518 508 -113 -759 713 765 851 218 -802 -502 -600 -873 -815 822 -596

-91 -712 800 137 -518 560 -286 -505 288 -971 776 -380 520 155 921 -196 593 606 957 912 26 -552 790 796 -123 -589 815 230 -915 -690 -705 -855 839

319 -222 53 336 -231 952 535 570 310 -311 -690 612 555 550 -550 865 605 -32 178 15 -835 -605 118 -357 -557 -583 -900 -569 -959 -592 -957 556 102

979 527 -75 -697 39 -675 961 -52 987 137 387 365 282 -905 -70 -868 -787 767 -39 582 289 -551 -289 930 -622 185 -171 710 -101 -595 587 -567 -920

173 -12 536 866 369 -767 985 -685 339 709 90 102 895 -373 -551 -588 -336 707 950 588 -951 269 -69 962 -517 825 588 68 585 355 -253 705 -179

19 -821 522 -86 882 -922 588 78 -512 -511 -617 -992 -277 621 782 -798 659 327 69 596 -579 -355 -737 -259 927 755 -595 -936 555 -91 525 -650 -391

[出力例]

90649

0 -435 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1542 0 0 0 0 -612 1541 -266 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-934 0 -3005 591 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 -1313 984 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 -338 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 831 -1279 0 0 0 -2826 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 2326 -140 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1553 -1371 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 315 0 0 0 2362 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 -337 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 87 0 0 0 2215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 -285 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 630 0 0 0 0 -266 2091 -1044 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 -1683 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2012 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 -1684 0 -2207 1511 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1468 411 0 1976 -2955 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1633 -365 1176 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -519 0 0 1180 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -344 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3630 0 0 0 -3093 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1811 0 0 0 0 0 -1259

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2245 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2456

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1008 2589 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1473 0 -2393 2875 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -788 3301 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -2109 35 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1077 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1252 -1587 3025

■参照サイト
AtCoder Regular Contest 135

2022年11月18日2022年11月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 214 の問題E (Packing Under Range Regulations) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労した(※)ものの, 個人的には, 実装を軽くする訓練を積めたので, 非常に良かったと思う.
※提出したところ, RE, WAとなったので, 集合要素を削除する処理の廃止, 入力情報(L, R) を配列に保存する処理の廃止, を含めたロジック修正を行って, 処理を軽くして再提出して, AC版となったもの.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc214/editorial/2431
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using PQ = priority_queue<int, vector<int>, greater<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        int N, L, R;
        scanf("%d", &N);
        set<int> st;
        map<int, vi> m;
        rep(j, N){
            scanf("%d %d", &L, &R);
            st.insert(L);
            m[L].pb(R);
        }
        st.insert(1000000001);
        
        // 3-2. シミュレーション.
        // -> WA, RE版 の 原因と見て, L[j] を 削除(st.erase(box);) は, 実装から外すようにロジックを修正.
        // 箱に入れてもいいボールのリスト(以下, リストと略記) へ 追加.
        bool ok = true;
        int box = *st.begin();
        PQ pq;
        while(box < 1000000001){
            // 箱番号と同じ L[j] が 見つかったか否かで, 分岐.
            if(st.count(box)){
                // L[j] = i の ボール j を, すべて, リスト に 追加.
                for(auto &q : m[box]) pq.push(q);
            }
            
            // ボール j を 箱 に 入れることができるか？
            if(!pq.empty()){
                // R[j] を 取り出す.
                int u = pq.top();
                pq.pop();
                
                // ボール j を 箱 に 入れることができなかった.
                if(u < box){
                    ok = false;
                    break;
                }
                
                // 次の箱へ.
                ++box;
            }
            
            // リスト が 空ならば, Skip.
            if(pq.empty() && !st.empty()) box = *st.lower_bound(box);
            
            // ボールを全て入れることはできない場合は, 終了.
            if(!ok) break;
        }
        
        // リスト へ 追加するボールが無くなった.
        while(ok && !pq.empty()){
            // R[j] を 取り出す.
            int u = pq.top();
            pq.pop();
            
            // ボール j を 箱 に 入れることができなかった.
            if(u < box){
                ok = false;
                break;
            }
            
            // 次の箱へ.
            ++box;
        }
        
        // 3-3. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc214/editorial/2431

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using PQ = priority_queue<int, vector<int>, greater<int>>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 各テストケース.

rep(i, T){

// 3-1. テストケース入力情報.

int N, L, R;

scanf("%d", &N);

set<int> st;

map<int, vi> m;

rep(j, N){

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

st.insert(L);

m[L].pb(R);

}

st.insert(1000000001);

// 3-2. シミュレーション.

// -> WA, RE版の原因と見て, L[j] を削除(st.erase(box);) は, 実装から外すようにロジックを修正.

// 箱に入れてもいいボールのリスト(以下, リストと略記) へ追加.

bool ok = true;

int box = *st.begin();

PQ pq;

while(box < 1000000001){

// 箱番号と同じ L[j] が見つかったか否かで, 分岐.

if(st.count(box)){

// L[j] = i のボール j を, すべて, リストに追加.

for(auto &q : m[box]) pq.push(q);

}

// ボール j を箱に入れることができるか？

if(!pq.empty()){

// R[j] を取り出す.

int u = pq.top();

pq.pop();

// ボール j を箱に入れることができなかった.

if(u < box){

ok = false;

break;

}

// 次の箱へ.

++box;

}

// リストが空ならば, Skip.

if(pq.empty() && !st.empty()) box = *st.lower_bound(box);

// ボールを全て入れることはできない場合は, 終了.

if(!ok) break;

}

// リストへ追加するボールが無くなった.

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

// R[j] を取り出す.

int u = pq.top();

pq.pop();

// ボール j を箱に入れることができなかった.

if(u < box){

ok = false;

break;

}

// 次の箱へ.

++box;

}

// 3-3. 出力.

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

}

return 0;

}

[入力例]
2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

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

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

[出力例]
No
Yes

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

[出力例]
Yes
Yes

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

[出力例]
Yes
No
Yes
No
Yes

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

[入力例]

1 2

2 3

3 3

1 2

2 3

3 3

1 3

999999999 1000000000

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 4

2 3

2 5

1 2

3 4

3 5

1 3

1 2

2 4

6 7

6 9

7 8

7 10

11 15

13 14

11 13

13 15

12 13

[出力例]

Yes

[入力例]

1 3

2 2

3 4

4 5

1 2

1 5

2 3

3 3

3 4

2 5

7 8

7 9

[出力例]

Yes

[入力例]

7 8

4 5

1 4

7 10

6 8

1 3

7 8

7 10

7 9

8 9

9 9

1 6

11 16

5 10

15 20

10 15

6 11

18 23

1 6

20 25

12 17

7 12

12 17

1 6

13 18

2 5

4 7

5 8

1 2

1 4

7 10

5 8

2 3

3 6

4 7

5 7

7 10

5 7

7 9

3 4

4 5

2 4

6 7

11 25

20 29

19 26

2 18

16 20

14 24

3 18

20 28

17 22

3 11

5 21

20 39

2 17

3 14

6 10

10 28

3 21

3 5

20 36

14 18

17 34

17 28

5 11

4 8

2 9

3 18

17 18

10 26

12 13

13 14

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 214

2022年11月16日

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

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

■感想.
1. 問題E は, 方針を絞り込んだものの WA版となったため, 解説を確認(※)し, 再提出したところ, AC版に到達できた.
※頂点(N) と仮想的な頂点(2 * N) の両方を確認してから, 出力する考慮が漏れていた.
2. 個人的には, 01-BFS を復習出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc277/editorial/5204
// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
const int INF = 2020202020;

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vvi G(2 * N);
    rep(i, M){
        int u, v, a;
        scanf("%d %d %d", &u, &v, &a);
        --u, --v;
        
        // 初回, 通行不可能な辺は, 仮想的な頂点(頂点番号が, N 大きい)から作成.
        u += !a * N;
        v += !a * N;
        G[u].pub(v);
        G[v].pub(u);
    }
    rep(i, K){
        // スイッチは, 頂点と仮想的な頂点を結ぶ辺とみなす.
        int s;
        scanf("%d", &s);
        --s;
        G[s + 0].pub(s + N);
        G[s + N].pub(s + 0);
    }
    
    // 2. 01-BFS.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // https://betrue12.hateblo.jp/entry/2018/12/08/000020
    auto bfs01 = [&](int s, int* d){
        // 2-1. 空のキュー.
        deque<int> dq;
        
        // 2-2. 探索開始地点 s の コスト設定.
        d[s] = 0;
        
        // 2-3. 探索開始地点 s をキュー に追加.
        dq.pub(s);
        while(!dq.empty()){
            // 2-4. キュー の 先頭要素を取り出す.
            int u = dq.front();
            dq.pof();
            
            // 2-5. 隣接頂点を確認.
            for(auto &v : G[u]){
                // コスト 0.
                if(abs(u - v) == N && d[v] > d[u] + 0) d[v] = d[u] + 0, dq.puf(v);
                
                // コスト 1.
                if(abs(u - v) != N && d[v] > d[u] + 1) d[v] = d[u] + 1, dq.pub(v);
            }
        }
    };
    int d[2 * N];
    rep(i, 2 * N) d[i] = INF;
    bfs01(0, d);
    
    // 3. 出力.
    int ans = min(d[N - 1], d[2 * N - 1]);
    printf("%d\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc277/editorial/5204

// 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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

const int INF = 2020202020;

int main(){

// 1. 入力情報.

int N, M, K;

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

vvi G(2 * N);

rep(i, M){

int u, v, a;

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

--u, --v;

// 初回, 通行不可能な辺は, 仮想的な頂点(頂点番号が, N 大きい)から作成.

u += !a * N;

v += !a * N;

G[u].pub(v);

G[v].pub(u);

}

rep(i, K){

// スイッチは, 頂点と仮想的な頂点を結ぶ辺とみなす.

int s;

scanf("%d", &s);

--s;

G[s + 0].pub(s + N);

G[s + N].pub(s + 0);

}

// 2. 01-BFS.

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

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

auto bfs01 = [&](int s, int* d){

// 2-1. 空のキュー.

deque<int> dq;

// 2-2. 探索開始地点 s のコスト設定.

d[s] = 0;

// 2-3. 探索開始地点 s をキューに追加.

dq.pub(s);

while(!dq.empty()){

// 2-4. キューの先頭要素を取り出す.

int u = dq.front();

dq.pof();

// 2-5. 隣接頂点を確認.

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

// コスト 0.

if(abs(u - v) == N && d[v] > d[u] + 0) d[v] = d[u] + 0, dq.puf(v);

// コスト 1.

if(abs(u - v) != N && d[v] > d[u] + 1) d[v] = d[u] + 1, dq.pub(v);

}

};

int d[2 * N];

rep(i, 2 * N) d[i] = INF;

bfs01(0, d);

// 3. 出力.

int ans = min(d[N - 1], d[2 * N - 1]);

printf("%d\n", (ans == INF) ? -1 : ans);

return 0;

}

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

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

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

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

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

[出力例]
5

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

[出力例]
7

[入力例]
18 23 15
1 2 1
1 3 1
3 2 0
3 5 0
4 5 1
4 6 1
6 5 0
5 8 1
8 7 1
8 9 1
7 9 0
11 9 0
11 10 1
11 12 1
12 10 0
12 14 1
14 13 0
13 15 1
14 15 0
15 16 1
16 17 0
17 18 0
16 18 1
2 3 5 6 7 9 10 11 12 13 14 15 16 17 18

[出力例]
10

[入力例]

5 5 2

1 3 0

2 3 1

5 4 1

2 1 1

1 4 0

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

4 4 2

4 3 0

1 2 1

1 2 0

2 1 1

2 4

[出力例]

-1

※AtCoderのテストケースより

[入力例]

7 8 6

1 2 1

3 4 1

5 6 1

7 6 1

4 2 0

3 5 0

5 7 0

6 7 0

2 3 4 5 6 7

[出力例]

[入力例]

10 10 8

1 2 1

3 2 0

3 4 1

5 6 1

5 3 0

6 7 0

7 8 1

7 9 0

8 10 0

9 10 1

2 3 5 6 7 8 9 10

[出力例]

[入力例]

18 23 15

1 2 1

1 3 1

3 2 0

3 5 0

4 5 1

4 6 1

6 5 0

5 8 1

8 7 1

8 9 1

7 9 0

11 9 0

11 10 1

11 12 1

12 10 0

12 14 1

14 13 0

13 15 1

14 15 0

15 16 1

16 17 0

17 18 0

16 18 1

2 3 5 6 7 9 10 11 12 13 14 15 16 17 18

[出力例]

■参照サイト
大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)
01-BFSのちょっと丁寧な解説

2022年11月15日2022年11月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 277 の問題C (Ladder Takahashi) ～問題D (Takahashi’s Solitaire) を解いてみた.

■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 個人的には, 問題C, D で, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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 a first
#define b second
int a[202020], b[202020], o[404040];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    m[1] = 0;
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        m[a[i]] = 0;
        m[b[i]] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    for(auto &p : m) o[p.b] = p.a;
    
    // 3. グラフ作成.
    vvi G(idx + 1);
    rep(i, N){
        G[m[a[i]]].pb(m[b[i]]);
        G[m[b[i]]].pb(m[a[i]]);
    }
    
    // 4. 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 &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d[idx + 1];
    rep(i, idx + 1) d[i] = 0;
    bfs(G, 0, d);
    
    // 5. 最高で何階へ上れるか？
    int ans = 1;
    rep(i, idx + 1) if(d[i]) ans = max(ans, o[i]);
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 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 a first

#define b second

int a[202020], b[202020], o[404040];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

m[1] = 0;

rep(i, N){

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

m[a[i]] = 0;

m[b[i]] = 0;

}

// 2. 座標圧縮.

int idx = -1;

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

for(auto &p : m) o[p.b] = p.a;

// 3. グラフ作成.

vvi G(idx + 1);

rep(i, N){

G[m[a[i]]].pb(m[b[i]]);

G[m[b[i]]].pb(m[a[i]]);

}

// 4. 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 &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);

}

};

int d[idx + 1];

rep(i, idx + 1) d[i] = 0;

bfs(G, 0, d);

// 5. 最高で何階へ上れるか？

int ans = 1;

rep(i, idx + 1) if(d[i]) ans = max(ans, o[i]);

// 6. 出力.

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

return 0;

}

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

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

[入力例]
6
1 3
1 5
1 12
3 5
3 12
5 12

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

[入力例]
3
500000000 600000000
600000000 700000000
700000000 800000000

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

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

[出力例]
7

[入力例]
20
187 89
159 225
26 1
27 177
124 151
206 333
29 26
89 29
191 74
156 42
62 45
1 27
53 30
42 4
1 10
175 111
10 22
113 174
206 22
20 171

[出力例]
333

[入力例]

1 4

4 3

4 10

8 3

[出力例]

※AtCoderテストケースより

[入力例]

1 3

1 5

1 12

3 5

3 12

5 12

[出力例]

※AtCoderテストケースより

[入力例]

500000000 600000000

600000000 700000000

700000000 800000000

[出力例]

※AtCoderテストケースより

[入力例]

1 3

1 5

2 3

4 5

2 7

[出力例]

[入力例]

187 89

159 225

26 1

27 177

124 151

206 333

29 26

89 29

191 74

156 42

62 45

1 27

53 30

42 4

1 10

175 111

10 22

113 174

206 22

20 171

[出力例]

333

■C++版プログラム(問題D／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
#define a first
#define b second
int a[202020];
LL t[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL ans = 0;
    map<int, int> m;
    rep(i, N){
        scanf("%d", &a[i]);
        ans += (LL)a[i];
        m[a[i]] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    vi v;
    for(auto &p : m) v.pb(p.a);
    v.pb(v.front());
    
    // 3. 各整数の合計.
    for(auto &p : m) t[p.b] += (LL)p.a;
    
    // 4. グラフ作成.
    vvi G(idx + 1);
    rep(i, v.size() - 1){
        if((v[i] + 1) % M == v[i + 1]){
            G[m[v[i + 0]]].pb(m[v[i + 1]]);
            G[m[v[i + 1]]].pb(m[v[i + 0]]);
        }
    }
    
    // 5. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[idx + 1], n = 0;
    rep(i, idx + 1) c[i] = 0;
    rep(i, idx + 1) if(!c[i]) bfs(G, i, c, ++n);
    
    // 6. 連結成分ごとに集計.
    LL g[n + 1];
    rep(i, n + 1) g[i] = 0;
    rep(i, N) g[c[m[a[i]]]] += t[m[a[i]]];
    
    // 7. 最大値は？
    LL gMax = 0;
    rep(i, n + 1) gMax = max(gMax , g[i]);
    
    // 8. 出力.
    printf("%lld\n", ans - gMax);
    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

#define a first

#define b second

int a[202020];

LL t[202020];

int main(){

// 1. 入力情報.

int N, M;

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

LL ans = 0;

map<int, int> m;

rep(i, N){

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

ans += (LL)a[i];

m[a[i]] = 0;

}

// 2. 座標圧縮.

int idx = -1;

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

vi v;

for(auto &p : m) v.pb(p.a);

v.pb(v.front());

// 3. 各整数の合計.

for(auto &p : m) t[p.b] += (LL)p.a;

// 4. グラフ作成.

vvi G(idx + 1);

rep(i, v.size() - 1){

if((v[i] + 1) % M == v[i + 1]){

G[m[v[i + 0]]].pb(m[v[i + 1]]);

G[m[v[i + 1]]].pb(m[v[i + 0]]);

}

// 5. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 取り出した要素を処理.

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[idx + 1], n = 0;

rep(i, idx + 1) c[i] = 0;

rep(i, idx + 1) if(!c[i]) bfs(G, i, c, ++n);

// 6. 連結成分ごとに集計.

LL g[n + 1];

rep(i, n + 1) g[i] = 0;

rep(i, N) g[c[m[a[i]]]] += t[m[a[i]]];

// 7. 最大値は？

LL gMax = 0;

rep(i, n + 1) gMax = max(gMax , g[i]);

// 8. 出力.

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

return 0;

}

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

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

[入力例]
1 10
4

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

[入力例]
20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

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

[入力例]
50 123
80 110 3 22 46 88 40 64 40 91 32 60 109 73 43 68 23 118 55 59 67 83 83 37 5 89 24 45 34 21 37 61 72 7 119 36 105 26 114 3 49 37 86 113 115 79 122 25 5 76

[出力例]
2657

[入力例]
100 1234
215 1020 246 682 852 664 1057 811 639 129 40 929 845 948 485 1174 47 1048 1150 827 929 1204 704 959 1101 169 430 1073 96 621 519 1173 1107 654 320 1105 292 684 854 386 866 189 460 994 504 748 1162 461 778 496 271 1179 1190 612 423 791 310 614 307 849 160 433 506 449 326 399 247 581 1195 1108 1013 664 1187 36 1211 334 633 97 1188 1009 1018 770 638 351 1090 1165 1050 614 1119 788 187 1187 246 1022 64 1224 957 17 406 1111

[出力例]
65630

[入力例]
200 123
12 18 6 72 23 90 66 25 12 34 43 104 114 56 89 116 21 38 30 50 24 46 80 94 88 87 35 50 84 31 100 20 3 29 87 23 79 94 3 30 37 42 21 30 33 88 114 69 84 18 17 100 22 69 70 18 109 115 86 30 64 7 97 111 85 81 3 29 14 117 103 55 75 30 118 104 57 35 108 20 87 50 104 28 24 39 18 68 26 97 69 100 19 94 6 37 111 9 46 60 2 72 56 6 13 58 109 63 28 47 62 81 90 90 82 48 92 118 116 81 82 45 100 65 8 122 22 53 23 119 6 86 33 96 35 93 119 0 63 50 10 8 109 104 84 16 73 115 29 19 3 86 99 106 1 86 60 100 57 5 28 64 27 111 6 67 91 77 71 14 118 21 84 39 91 10 94 113 22 5 12 51 55 16 1 102 24 18 104 122 103 79 65 77 61 13 91 90 0 50

[出力例]
9189

[入力例]

9 7

3 0 2 5 5 3 0 6 3

[出力例]

※AtCoderテストケースより

[入力例]

1 10

[出力例]

※AtCoderテストケースより

[入力例]

20 20

18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

[出力例]

※AtCoderテストケースより

[入力例]

50 123

80 110 3 22 46 88 40 64 40 91 32 60 109 73 43 68 23 118 55 59 67 83 83 37 5 89 24 45 34 21 37 61 72 7 119 36 105 26 114 3 49 37 86 113 115 79 122 25 5 76

[出力例]

2657

[入力例]

100 1234

215 1020 246 682 852 664 1057 811 639 129 40 929 845 948 485 1174 47 1048 1150 827 929 1204 704 959 1101 169 430 1073 96 621 519 1173 1107 654 320 1105 292 684 854 386 866 189 460 994 504 748 1162 461 778 496 271 1179 1190 612 423 791 310 614 307 849 160 433 506 449 326 399 247 581 1195 1108 1013 664 1187 36 1211 334 633 97 1188 1009 1018 770 638 351 1090 1165 1050 614 1119 788 187 1187 246 1022 64 1224 957 17 406 1111

[出力例]

65630

[入力例]

200 123

12 18 6 72 23 90 66 25 12 34 43 104 114 56 89 116 21 38 30 50 24 46 80 94 88 87 35 50 84 31 100 20 3 29 87 23 79 94 3 30 37 42 21 30 33 88 114 69 84 18 17 100 22 69 70 18 109 115 86 30 64 7 97 111 85 81 3 29 14 117 103 55 75 30 118 104 57 35 108 20 87 50 104 28 24 39 18 68 26 97 69 100 19 94 6 37 111 9 46 60 2 72 56 6 13 58 109 63 28 47 62 81 90 90 82 48 92 118 116 81 82 45 100 65 8 122 22 53 23 119 6 86 33 96 35 93 119 0 63 50 10 8 109 104 84 16 73 115 29 19 3 86 99 106 1 86 60 100 57 5 28 64 27 111 6 67 91 77 71 14 118 21 84 39 91 10 94 113 22 5 12 51 55 16 1 102 24 18 104 122 103 79 65 77 61 13 91 90 0 50

[出力例]

9189

■参照サイト
大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

2022年11月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題A (Digit Sum of 2x) ～問題B (Gift Tax) を解いてみた.

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

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

■C++版プログラム(問題A／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--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. M.
    int M = 2 * N;
    
    // 3. x.
    int q = N / 4;
    int r = N % 4;
    string x;
    if(r) x.pb(r + '0');
    rep(i, q) x.pb('4');
    
    // 4. 出力.
    printf("%d\n%s\n", M, x.c_str());
    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--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. M.

int M = 2 * N;

// 3. x.

int q = N / 4;

int r = N % 4;

string x;

if(r) x.pb(r + '0');

rep(i, q) x.pb('4');

// 4. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
6

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

[入力例]
100

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

[入力例]
7

[出力例]
14
34

[入力例]
21

[出力例]
42
144444

[入力例]
55

[出力例]
110
34444444444444

[入力例]
2022

[出力例]
4044
24444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

100

[出力例]

200

4444444444444444444444444

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

144444

[入力例]

[出力例]

110

34444444444444

[入力例]

2022

[出力例]

4044

24444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444

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

// 解き直し.
// https://atcoder.jp/contests/arc144/editorial/4438
// 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];

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d %d %d", &N, &a, &b);
    LL aMax = 0;
    rep(i, N){
        scanf("%lld", &A[i]);
        aMax = max(aMax, A[i]);
    }
    
    // 2. 評価関数.
    auto f = [&](LL C) -> bool {
        // 2-1. 任意 の i で, A[i] >= C を 達成できるか？
        LL x = 0, y = 0;
        rep(i, N){
            // 差分.
            LL d = abs(C - A[i]);
            
            // +a 操作.
            if(A[i] < C){
                x += d / a;
                x += (d % a) > 0;
            }
            
            // -b 操作.
            if(A[i] >= C) y += d / b;
        }
        
        // 2-2. 判定結果.
        return (x <= y);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = -1, h = aMax * 2 + 1;
    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", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc144/editorial/4438

// 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];

int main(){

// 1. 入力情報.

int N, a, b;

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

LL aMax = 0;

rep(i, N){

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

aMax = max(aMax, A[i]);

}

// 2. 評価関数.

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

// 2-1. 任意の i で, A[i] >= C を達成できるか？

LL x = 0, y = 0;

rep(i, N){

// 差分.

LL d = abs(C - A[i]);

// +a 操作.

if(A[i] < C){

x += d / a;

x += (d % a) > 0;

}

// -b 操作.

if(A[i] >= C) y += d / b;

}

// 2-2. 判定結果.

return (x <= y);

};

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

LL l = -1, h = aMax * 2 + 1;

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", l);

return 0;

}

[入力例]
3 2 2
1 5 9

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

[入力例]
3 2 3
11 1 2

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

[入力例]
3 1 100
8 5 6

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

[入力例]
6 123 321
10 100 1000 10000 100000 1000000

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

[入力例]
10 20 22
314 159 265 358 979 323 846 264 338 327

[出力例]
399

[入力例]
12 2022 2023
48777 62245 64053 48929 50177 34066 62213 19468 65086 76308 36458 60626

[出力例]
51820

[入力例]
33 123456789 234567890
119462232 441702612 741000538 75937058 249169418 88678388 322309006 934544728 382109572 200174813 579938761 629008023 922337708 321026352 72252172 312780367 202788116 381989156 254895422 726096598 313540074 392866546 879268330 653653149 384616870 261814030 36273445 535329540 106843016 868666234 758681421 156962817 133682619

[出力例]
256960818

[入力例]
50 11 15
2244 9171 5910 9145 7923 1959 4653 7101 7913 9403 9144 3185 5328 9177 2117 134 6376 6425 8190 9558 7087 9909 4856 4663 9774 9330 3626 8179 3955 5244 1060 9881 6784 7292 543 6069 7909 2869 232 7170 2628 4975 622 2394 1279 4281 6452 2930 8750 264

[出力例]
5102

[入力例]

3 2 2

1 5 9

[出力例]

※AtCoderのテストケースより

[入力例]

3 2 3

11 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 100

8 5 6

[出力例]

※AtCoderのテストケースより

[入力例]

6 123 321

10 100 1000 10000 100000 1000000

[出力例]

90688

※AtCoderのテストケースより

[入力例]

10 20 22

314 159 265 358 979 323 846 264 338 327

[出力例]

399

[入力例]

12 2022 2023

48777 62245 64053 48929 50177 34066 62213 19468 65086 76308 36458 60626

[出力例]

51820

[入力例]

33 123456789 234567890

119462232 441702612 741000538 75937058 249169418 88678388 322309006 934544728 382109572 200174813 579938761 629008023 922337708 321026352 72252172 312780367 202788116 381989156 254895422 726096598 313540074 392866546 879268330 653653149 384616870 261814030 36273445 535329540 106843016 868666234 758681421 156962817 133682619

[出力例]

256960818

[入力例]

50 11 15

2244 9171 5910 9145 7923 1959 4653 7101 7913 9403 9144 3185 5328 9177 2117 134 6376 6425 8190 9558 7087 9909 4856 4663 9774 9330 3626 8179 3955 5244 1060 9881 6784 7292 543 6069 7909 2869 232 7170 2628 4975 622 2394 1279 4281 6452 2930 8750 264

[出力例]

5102

■参照サイト
AtCoder Regular Contest 144

2022年11月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題C (Bracket and Permutation) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 実装に苦労したものの, 括弧列の性質に触れることが出来たので, 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc141/editorial/4024
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi P(2 * N), Q(2 * N);
    rep(i, 2 * N){
        scanf("%d", &P[i]);
        --P[i];
    }
    rep(i, 2 * N){
        scanf("%d", &Q[i]);
        --Q[i];
    }
    
    // 2. S の 候補.
    string S(2 * N, '.');
    rep(i, N){
        int l = 2 * i + 0;
        int r = 2 * i + 1;
        
        // P[l] > P[r] の ケース.
        // -> P[l] < P[r] の ケースは, 不問とする.
        if(P[l] > P[r]){
            S[P[l]] = '(';
            S[P[r]] = ')';
        }
        
        // Q[l] < Q[r] の ケース.
        // -> Q[l] > Q[r] の ケースは, 不問とする.
        if(Q[l] < Q[r]){
            S[Q[l]] = '(';
            S[Q[r]] = ')';
        }
    }
    
    // 3. S の 候補 が 定まらない.
    rep(i, 2 * N){
        if(S[i] == '.'){
            puts("-1");
            return 0;
        }
    }
    
    // 4. 貪欲法.
    // 4-1. 順列 P に あたるものは？
    // -> 正しい括弧列(pUpDown >= 0) or 正しい括弧列 の 逆(pUpDown <= 0) を 区別.
    vi p, pL, pR;
    int pUpDown = 0;
    int pCur = 0;
    rep(i, 2 * N){
        // 左括弧数 - 右括弧数.
        pCur += (S[i] == '(') ? +1 : -1;
        
        // スタート.
        if(pUpDown == 0) pUpDown = pCur;
        
        // 左括弧 or 右括弧 の インデックス保存.
        if(S[i] == '(') pL.pb(i);
        else            pR.pb(i);
        
        // 次へ.
        if(pCur != 0) continue;
        
        // ゴール(正しい括弧列).
        // -> sort したものを追加.
        if(pUpDown > 0){
            vi v;
            rep(j, pL.size()) v.pb(pL[j]);
            rep(j, pR.size()) v.pb(pR[j]);
            sort(all(v));
            for(auto &x : v) p.pb(x);
        }
        
        // ゴール(正しい括弧列 の 逆).
        if(pUpDown < 0){
            rep(j, pL.size()){
                p.pb(pL[j]);
                p.pb(pR[j]);
            }
        }
        
        // 初期化し, 次へ.
        pUpDown = 0;
        pL.clear();
        pR.clear();
    }
    
    // 4-2. 順列 Q に あたるものは？
    // -> 正しい括弧列(qUpDown >= 0) or 正しい括弧列 の 逆(qUpDown <= 0) を 区別.
    vi q, qL, qR;
    int qUpDown = 0;
    int qCur = 0;
    repr(i, 2 * N - 1, 0){
        // 右括弧数 - 左括弧数.
        qCur += (S[i] == ')') ? +1 : -1;
        
        // スタート.
        if(qUpDown == 0) qUpDown = qCur;
        
        // 左括弧 or 右括弧 の インデックス保存.
        if(S[i] == '(') qL.pb(i);
        else            qR.pb(i);
        
        // 次へ.
        if(qCur != 0) continue;
        
        // ゴール(正しい括弧列).
        if(qUpDown > 0){
            rep(j, qL.size()){
                q.pb(qL[j]);
                q.pb(qR[j]);
            }
        }
        
        // ゴール(正しい括弧列 の 逆).
        // -> sort したものを追加.
        if(qUpDown < 0){
            vi v;
            rep(j, qL.size()) v.pb(qL[j]);
            rep(j, qR.size()) v.pb(qR[j]);
            sort(all(v));
            reverse(all(v));
            for(auto &x : v) q.pb(x);
        }
        
        // 初期化し, 次へ.
        qUpDown = 0;
        qL.clear();
        qR.clear();
    }
    
    // 5. 出力.
    printf("%s\n", (P == p && Q == q) ? S.c_str() : "-1");
    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/arc141/editorial/4024

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi P(2 * N), Q(2 * N);

rep(i, 2 * N){

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

--P[i];

}

rep(i, 2 * N){

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

--Q[i];

}

// 2. S の候補.

string S(2 * N, '.');

rep(i, N){

int l = 2 * i + 0;

int r = 2 * i + 1;

// P[l] > P[r] のケース.

// -> P[l] < P[r] のケースは, 不問とする.

if(P[l] > P[r]){

S[P[l]] = '(';

S[P[r]] = ')';

}

// Q[l] < Q[r] のケース.

// -> Q[l] > Q[r] のケースは, 不問とする.

if(Q[l] < Q[r]){

S[Q[l]] = '(';

S[Q[r]] = ')';

}

// 3. S の候補が定まらない.

rep(i, 2 * N){

if(S[i] == '.'){

puts("-1");

return 0;

}

// 4. 貪欲法.

// 4-1. 順列 P にあたるものは？

// -> 正しい括弧列(pUpDown >= 0) or 正しい括弧列の逆(pUpDown <= 0) を区別.

vi p, pL, pR;

int pUpDown = 0;

int pCur = 0;

rep(i, 2 * N){

// 左括弧数 - 右括弧数.

pCur += (S[i] == '(') ? +1 : -1;

// スタート.

if(pUpDown == 0) pUpDown = pCur;

// 左括弧 or 右括弧のインデックス保存.

if(S[i] == '(') pL.pb(i);

else pR.pb(i);

// 次へ.

if(pCur != 0) continue;

// ゴール(正しい括弧列).

// -> sort したものを追加.

if(pUpDown > 0){

vi v;

rep(j, pL.size()) v.pb(pL[j]);

rep(j, pR.size()) v.pb(pR[j]);

sort(all(v));

for(auto &x : v) p.pb(x);

}

// ゴール(正しい括弧列の逆).

if(pUpDown < 0){

rep(j, pL.size()){

p.pb(pL[j]);

p.pb(pR[j]);

}

// 初期化し, 次へ.

pUpDown = 0;

pL.clear();

pR.clear();

}

// 4-2. 順列 Q にあたるものは？

// -> 正しい括弧列(qUpDown >= 0) or 正しい括弧列の逆(qUpDown <= 0) を区別.

vi q, qL, qR;

int qUpDown = 0;

int qCur = 0;

repr(i, 2 * N - 1, 0){

// 右括弧数 - 左括弧数.

qCur += (S[i] == ')') ? +1 : -1;

// スタート.

if(qUpDown == 0) qUpDown = qCur;

// 左括弧 or 右括弧のインデックス保存.

if(S[i] == '(') qL.pb(i);

else qR.pb(i);

// 次へ.

if(qCur != 0) continue;

// ゴール(正しい括弧列).

if(qUpDown > 0){

rep(j, qL.size()){

q.pb(qL[j]);

q.pb(qR[j]);

}

// ゴール(正しい括弧列の逆).

// -> sort したものを追加.

if(qUpDown < 0){

vi v;

rep(j, qL.size()) v.pb(qL[j]);

rep(j, qR.size()) v.pb(qR[j]);

sort(all(v));

reverse(all(v));

for(auto &x : v) q.pb(x);

}

// 初期化し, 次へ.

qUpDown = 0;

qL.clear();

qR.clear();

}

// 5. 出力.

printf("%s\n", (P == p && Q == q) ? S.c_str() : "-1");

return 0;

}

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

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

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

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

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

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

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

[出力例]
()())(

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

[出力例]
((()))

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

[出力例]
-1

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

[出力例]
(()))(

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

[出力例]
-1

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

[出力例]
))((())(

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

[出力例]
)(((())))(

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

[出力例]
()((()))()((()())())

[入力例]

1 2 4 3

4 3 1 2

[出力例]

())(

※AtCoderのテストケースより

[入力例]

1 3 2 4

4 3 2 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

2 1 5 3 4 6

6 5 3 4 2 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

1 2 3 4 6 5

6 5 3 4 1 2

[出力例]

()())(

[入力例]

1 2 3 4 5 6

3 6 2 5 1 4

[出力例]

((()))

[入力例]

1 3 2 4 5 6

5 6 2 4 1 3

[出力例]

-1

[入力例]

1 2 3 4 6 5

6 5 2 4 1 3

[出力例]

(()))(

[入力例]

1 2 3 5 4 6 7 8

7 8 4 6 3 5 1 2

[出力例]

-1

[入力例]

3 1 4 2 5 6 8 7

8 7 5 6 4 3 2 1

[出力例]

))((())(

[入力例]

2 1 3 4 5 6 7 8 10 9

10 9 5 8 4 7 3 6 2 1

[出力例]

)(((())))(

[入力例]

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

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

[出力例]

()((()))()((()())())

■参照サイト
AtCoder Regular Contest 141

C++の練習を兼ねて, AtCoder Regular Contest 152 の 問題C (Pivot) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 152 の 問題A (Seat Occupation) ～ 問題B (Pass on Path) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の 問題D (AND OR Equation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の 問題C (K Derangement) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 135 の 問題D (Add to Square) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 214 の 問題E (Packing Under Range Regulations) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 277 の 問題C (Ladder Takahashi) ～ 問題D (Takahashi’s Solitaire) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の 問題A (Digit Sum of 2x) ～ 問題B (Gift Tax) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 141 の 問題C (Bracket and Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 152 の問題C (Pivot) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 152 の問題A (Seat Occupation) ～問題B (Pass on Path) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題D (AND OR Equation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題C (K Derangement) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題D (Add to Square) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 214 の問題E (Packing Under Range Regulations) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 277 の問題C (Ladder Takahashi) ～問題D (Takahashi’s Solitaire) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 144 の問題A (Digit Sum of 2x) ～問題B (Gift Tax) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 141 の問題C (Bracket and Permutation) を解いてみた.