4月, 2020 | 個人用メモ帳

2020年4月30日2020年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題A (A – ダイナミックなポーズ) ～問題B (B – 完全数) を解いてみた.

■感想.
1. 問題B で, 約数の計算方法を復習できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 026 解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    
    // 2. 出力.
    printf("%d\n", A * max(N - 5, 0) + B * min(N, 5));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, A, B;

scanf("%d %d %d", &N, &A, &B);

// 2. 出力.

printf("%d\n", A * max(N - 5, 0) + B * min(N, 5));

return 0;

}

[入力例]
10 5 1

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

[入力例]
4 60 7

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

[入力例]

10 5 1

[出力例]

※AtCoderのテストケースより

[入力例]

4 60 7

[出力例]

※AtCoderのテストケースより

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define pb push_back

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数.
vector<LL> div(LL X){
    vector<LL> ret;
    ret.pb(1);
    for(LL d = 2; d * d <= X; d++){
        if(X % d == 0){
            ret.pb(d);
            if(d * d != X) ret.pb(X / d);
        }
    }
    // subtask1_24.txt で WA版.
    // ret.pb(X);
    if(X > 1) ret.pb(X);
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 約数を計算.
    vector<LL> v = div(N);
    
    // 3. 約数の和を計算.
    LL sum = -N;
    for(auto &p : v) sum += p;
    
    // 4. 完全数か？
    string ans = "Perfect";
    if(sum > N) ans = "Abundant";
    if(sum < N) ans = "Deficient";
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define pb push_back

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数.

vector<LL> div(LL X){

vector<LL> ret;

ret.pb(1);

for(LL d = 2; d * d <= X; d++){

if(X % d == 0){

ret.pb(d);

if(d * d != X) ret.pb(X / d);

}

// subtask1_24.txt で WA版.

// ret.pb(X);

if(X > 1) ret.pb(X);

return ret;

}

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 約数を計算.

vector<LL> v = div(N);

// 3. 約数の和を計算.

LL sum = -N;

for(auto &p : v) sum += p;

// 4. 完全数か？

string ans = "Perfect";

if(sum > N) ans = "Abundant";

if(sum < N) ans = "Deficient";

// 5. 出力.

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

return 0;

}

[入力例]
6

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

[入力例]
24

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

[入力例]
27

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

[入力例]
945

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

[入力例]
1

[出力例]
Deficient

[入力例]
8128

[出力例]
Perfect

[入力例]
33550336

[出力例]
Perfect

[入力例]
8589869056

[出力例]
Perfect

[入力例]
10000000000

[出力例]
Abundant

[入力例]

[出力例]

Perfect

※AtCoderのテストケースより

[入力例]

[出力例]

Abundant

※AtCoderのテストケースより

[入力例]

[出力例]

Deficient

※AtCoderのテストケースより

[入力例]

945

[出力例]

Abundant

※AtCoderのテストケースより

[入力例]

[出力例]

Deficient

[入力例]

8128

[出力例]

Perfect

[入力例]

33550336

[出力例]

Perfect

[入力例]

8589869056

[出力例]

Perfect

[入力例]

10000000000

[出力例]

Abundant

■参照サイト
AtCoder Regular Contest 026
完全数

2020年4月28日2020年4月28日

C++ の動作確認をしてみた（２１０）

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題A (A – ゴールドラッシュ) ～問題B (B – チョコレート) を解いてみた.

■感想.
1. 問題A は, 苦手なdpの訓練を積めたので, 非常に良かったと思う.
2. 問題B は, 二次元累積和の復習が出来たので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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 D[10], J[10], dp[10][2];

int main(){
    
    // 1. 入力情報.
    rep(i, 7) scanf("%d", &D[i]);
    rep(i, 7) scanf("%d", &J[i]);
    
    // 2. 最適に鉱山を選んだ場合に得られる金の量は？
    dp[0][0] = D[0];
    dp[0][1] = J[0];
    rep(i, 7){
        dp[i + 1][0] = max(dp[i][0], dp[i][1]) + D[i + 1];
        dp[i + 1][1] = max(dp[i][0], dp[i][1]) + J[i + 1];
    }
    
    // 3. 出力.
    printf("%d\n", max(dp[7][0], dp[7][1]));
    return 0;
    
}

#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 D[10], J[10], dp[10][2];

int main(){

// 1. 入力情報.

rep(i, 7) scanf("%d", &D[i]);

rep(i, 7) scanf("%d", &J[i]);

// 2. 最適に鉱山を選んだ場合に得られる金の量は？

dp[0][0] = D[0];

dp[0][1] = J[0];

rep(i, 7){

dp[i + 1][0] = max(dp[i][0], dp[i][1]) + D[i + 1];

dp[i + 1][1] = max(dp[i][0], dp[i][1]) + J[i + 1];

}

// 3. 出力.

printf("%d\n", max(dp[7][0], dp[7][1]));

return 0;

}

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

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

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

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

[入力例]
0 0 0 0 0 0 0
0 0 0 0 0 0 0

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

[入力例]
8 3 0 2 5 25 252
252 252 2 5 2 5 2

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

[入力例]
224 1964 1954 1506 547 894 1437
812 1474 1392 783 1375 1115 509

[出力例]
10163

[入力例]
1353 553 146 452 660 733 1384
1627 1450 324 1152 848 823 227

[出力例]
7608

[入力例]

4 2 0 5 6 2 5

6 1 4 3 6 4 6

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 4 5 6 7

2 3 4 5 6 7 8

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 0 0 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

8 3 0 2 5 25 252

252 252 2 5 2 5 2

[出力例]

793

※AtCoderのテストケースより

[入力例]

224 1964 1954 1506 547 894 1437

812 1474 1392 783 1375 1115 509

[出力例]

10163

[入力例]

1353 553 146 452 660 733 1384

1627 1450 324 1152 848 823 227

[出力例]

7608

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

#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 wC[111][111], bC[111][111];     // white, black.
int wCum[111][111], bCum[111][111]; // white, black.

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        rep(j, W){
            if((i + j) & 1) scanf("%d", &wC[i][j]);
            else            scanf("%d", &bC[i][j]);
        }
    }
    
    // 2. ブラック, ホワイトチョコレートについて, 二次元累積和を保存.
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            bCum[i][j] = bC[i - 1][j - 1] + bCum[i - 1][j] + bCum[i][j - 1] - bCum[i - 1][j - 1];
            wCum[i][j] = wC[i - 1][j - 1] + wCum[i - 1][j] + wCum[i][j - 1] - wCum[i - 1][j - 1];
        }
    }
        
    // 3. 条件を満たす切り出し方を調査.
    int ans = 0;
    repx(h, 1, H + 1){
        repx(w, 1, W + 1){
            // 3-1. マスの数が小さい場合は, Skip.
            if(h * w <= ans) continue;
            
            // 3-2. 縦h, 横w の 切り出し方 を 調査.
            // 左上隅 を (sx, sy) と 置く.
            rep(sx, H - h + 1){
                rep(sy, W - w + 1){
                    // 右下隅 は, (sx + h - 1, sy + w - 1)
                    int gx = sx + h - 1;
                    int gy = sy + w - 1;
                    
                    // ブラック, ホワイトチョコレートの濃度合計.
                    int bSum = bCum[gx + 1][gy + 1] - bCum[sx][gy + 1] - bCum[gx + 1][sy] + bCum[sx][sy];
                    int wSum = wCum[gx + 1][gy + 1] - wCum[sx][gy + 1] - wCum[gx + 1][sy] + wCum[sx][sy];
                    
                    // 等しければ, 次の処理へ.
                    if(bSum == wSum){
                        ans = h * w; // 最大値更新.
                        break;
                    }
                }
            }
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 wC[111][111], bC[111][111]; // white, black.

int wCum[111][111], bCum[111][111]; // white, black.

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

rep(j, W){

if((i + j) & 1) scanf("%d", &wC[i][j]);

else scanf("%d", &bC[i][j]);

}

// 2. ブラック, ホワイトチョコレートについて, 二次元累積和を保存.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

bCum[i][j] = bC[i - 1][j - 1] + bCum[i - 1][j] + bCum[i][j - 1] - bCum[i - 1][j - 1];

wCum[i][j] = wC[i - 1][j - 1] + wCum[i - 1][j] + wCum[i][j - 1] - wCum[i - 1][j - 1];

}

// 3. 条件を満たす切り出し方を調査.

int ans = 0;

repx(h, 1, H + 1){

repx(w, 1, W + 1){

// 3-1. マスの数が小さい場合は, Skip.

if(h * w <= ans) continue;

// 3-2. 縦h, 横w の切り出し方を調査.

// 左上隅を (sx, sy) と置く.

rep(sx, H - h + 1){

rep(sy, W - w + 1){

// 右下隅は, (sx + h - 1, sy + w - 1)

int gx = sx + h - 1;

int gy = sy + w - 1;

// ブラック, ホワイトチョコレートの濃度合計.

int bSum = bCum[gx + 1][gy + 1] - bCum[sx][gy + 1] - bCum[gx + 1][sy] + bCum[sx][sy];

int wSum = wCum[gx + 1][gy + 1] - wCum[sx][gy + 1] - wCum[gx + 1][sy] + wCum[sx][sy];

// 等しければ, 次の処理へ.

if(bSum == wSum){

ans = h * w; // 最大値更新.

break;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
4 0
7 3

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

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

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

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

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

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

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

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

[出力例]
266

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

[出力例]
1960

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

[入力例]

3 4

4 6 2 5

3 5 6 7

2 5 5 6

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

4 0

7 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 3

0 0 0

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 3

1 2 3

6 5 4

7 8 9

[出力例]

※AtCoderのテストケースより

[入力例]

1 5

0 1 2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

20 30

79 26 49 19 88 87 44 69 61 31 17 25 28 32 34 34 30 74 19 97 66 35 32 54 75 97 48 64 51 40

91 82 28 6 54 56 1 88 4 11 68 32 89 51 61 77 22 84 91 91 38 79 86 83 92 27 76 80 63 52

25 66 85 50 55 56 58 96 71 2 65 67 58 57 81 18 56 99 44 73 42 66 91 36 77 43 47 95 26 68

94 13 0 85 14 37 36 34 58 86 1 44 49 28 15 26 24 44 39 98 78 27 30 93 68 78 49 95 26 26

21 31 92 95 23 21 8 55 41 86 25 62 26 27 25 85 1 11 4 73 42 26 56 32 32 66 99 60 68 8

54 51 1 6 86 24 20 1 0 0 97 72 46 67 98 56 61 94 45 67 6 60 1 48 97 38 87 69 90 99

55 37 44 84 33 26 70 86 63 78 20 42 87 6 69 35 20 34 77 12 32 24 28 74 29 42 98 88 30 90

70 57 29 52 58 20 9 51 14 45 27 35 51 91 98 90 69 10 35 45 99 0 38 25 89 2 32 29 72 79

30 40 7 96 97 86 61 48 37 69 24 24 71 42 47 60 28 89 77 26 88 35 47 49 84 20 62 98 65 17

58 93 63 54 57 96 75 46 3 8 94 20 96 78 98 56 3 73 27 91 48 55 44 71 10 53 95 83 49 28

36 67 56 11 30 94 15 14 36 6 63 39 47 2 93 48 27 28 82 83 98 5 29 79 8 42 51 76 95 97

89 75 9 23 37 25 35 33 50 85 41 53 28 95 36 16 99 12 98 58 21 62 71 66 93 7 55 85 50 45

6 9 40 8 7 19 32 56 78 79 26 79 75 88 33 35 55 70 13 59 15 98 96 25 44 46 15 91 25 40

8 75 80 4 1 33 83 76 48 13 24 7 92 29 19 99 62 2 68 83 27 25 93 79 47 13 9 19 73 81

49 46 7 39 77 13 9 8 39 41 69 30 96 76 36 86 3 94 39 76 87 34 46 5 54 43 50 74 89 87

36 76 48 54 18 43 89 79 59 2 91 79 1 57 21 35 65 54 96 9 72 75 39 19 93 23 55 79 20 22

55 37 5 73 87 1 36 85 91 47 4 86 74 56 62 90 40 97 43 93 10 70 55 72 19 26 46 72 59 31

0 82 39 78 91 99 67 47 23 92 70 74 45 48 92 24 41 98 28 67 30 2 43 49 88 66 88 18 13 29

44 44 16 48 93 84 40 26 32 82 19 92 39 46 93 28 11 88 18 78 97 38 18 98 24 46 58 94 70 92

60 4 73 79 33 43 14 99 65 7 41 48 53 86 72 91 95 83 1 58 45 15 33 92 25 67 77 24 32 92

[出力例]

266

[入力例]

50 75

81 23 73 83 35 30 8 53 0 84 1 5 48 52 26 12 78 87 79 35 84 29 82 80 23 68 6 61 13 79 66 44 6 25 80 44 54 36 55 81 84 64 78 64 91 85 19 75 87 3 93 93 91 41 86 84 39 34 27 77 39 61 79 80 43 34 84 14 22 30 68 47 22 84 0

93 92 11 88 80 98 31 49 10 87 41 25 80 60 97 1 18 65 9 2 52 45 26 9 54 14 16 84 73 12 66 61 30 9 94 40 87 39 95 59 12 24 34 59 36 64 21 27 33 35 2 35 84 22 31 80 88 61 66 40 40 50 54 4 82 18 77 88 68 73 96 54 21 73 47

54 24 5 42 98 34 25 20 85 21 2 86 91 87 70 24 21 9 55 80 74 63 65 89 78 44 75 41 18 6 49 89 0 64 25 9 62 71 79 14 67 87 40 47 6 16 99 32 20 23 46 19 26 7 1 40 26 66 31 79 70 64 36 52 56 90 28 44 94 5 84 15 10 16 34

31 43 96 15 90 5 76 25 38 76 90 47 20 31 52 45 31 64 60 38 41 79 0 96 99 7 17 97 40 46 73 92 72 85 52 28 63 14 66 24 12 35 96 14 68 20 29 2 61 98 68 31 2 1 99 89 88 9 8 39 68 15 40 12 20 58 45 48 8 55 50 22 2 15 22

23 9 44 79 27 54 37 62 47 77 52 49 92 20 51 55 69 54 12 91 1 54 98 98 88 61 16 88 38 60 92 28 96 67 15 67 26 64 48 20 72 32 18 66 34 68 90 80 28 64 50 76 36 72 85 47 39 50 36 27 66 77 28 67 94 55 20 4 36 85 60 69 38 50 82

68 48 44 72 39 81 27 88 29 71 47 29 89 21 84 44 37 53 16 68 5 83 13 22 25 82 32 73 52 67 55 50 57 91 40 27 18 45 75 50 96 26 78 69 96 2 64 44 43 56 76 13 73 76 21 61 72 88 31 84 90 55 53 57 30 42 56 90 73 21 88 47 64 53 52

47 21 3 75 52 72 7 65 63 94 80 40 63 53 4 9 67 76 45 68 44 10 38 79 31 0 81 89 30 19 27 14 46 53 40 68 10 34 83 29 22 50 53 50 0 95 90 50 25 77 33 79 66 77 60 40 82 97 86 70 65 88 60 36 10 5 49 85 87 14 20 87 23 36 64

98 1 96 11 32 25 71 22 76 86 74 66 10 29 49 49 9 52 28 42 12 66 28 45 24 1 61 40 37 98 20 41 42 97 86 17 61 57 69 54 59 73 54 0 80 45 20 32 16 71 43 19 31 8 41 14 75 16 94 21 95 54 18 20 76 65 47 10 29 17 47 18 53 57 62

59 24 42 54 46 65 68 83 36 64 38 68 57 7 18 23 81 2 64 11 85 8 86 25 18 85 91 44 24 70 99 62 70 59 34 88 61 95 90 79 26 7 41 31 55 57 21 9 45 57 5 68 75 10 23 19 46 21 96 34 22 11 48 63 81 16 26 27 14 62 94 8 35 38 13

97 23 37 24 83 79 24 15 32 7 17 92 91 37 39 27 73 94 50 21 86 60 55 16 0 52 41 36 25 83 47 51 10 32 23 7 74 29 42 15 2 46 45 8 60 40 19 79 90 26 12 24 58 2 23 29 54 3 43 29 29 25 68 4 67 29 21 0 28 77 93 47 2 49 6

48 51 87 83 3 58 25 79 31 28 91 11 39 37 75 4 58 53 62 32 37 30 80 35 57 48 84 94 26 32 94 3 95 7 77 79 19 80 47 94 76 65 60 71 46 68 43 51 91 83 45 70 80 23 24 32 33 2 5 73 61 20 44 38 81 20 8 38 77 37 86 42 68 53 32

82 25 27 63 35 21 46 44 64 40 95 64 2 11 10 70 28 84 13 63 43 47 29 26 52 94 93 38 30 93 59 31 2 47 6 30 71 62 12 61 4 97 41 33 3 88 81 71 31 50 99 46 6 19 32 14 95 59 62 17 82 52 48 42 67 99 65 53 65 54 22 8 72 97 35

74 49 2 80 47 85 64 21 57 78 30 61 16 74 76 18 24 34 99 70 73 77 22 68 14 61 29 76 3 83 74 62 10 65 39 50 62 7 94 93 43 30 23 96 21 52 99 98 74 39 99 89 91 51 8 87 31 12 37 12 54 63 75 68 72 47 2 75 8 64 19 45 95 7 26

10 41 41 73 29 48 67 6 10 59 88 69 57 67 43 6 54 29 20 22 23 3 42 25 3 33 46 38 99 7 22 27 94 74 45 5 27 2 75 19 32 98 48 8 49 19 71 88 63 54 6 44 67 3 16 35 73 31 23 5 74 1 59 70 83 26 69 82 65 59 33 92 26 47 79

79 1 83 28 48 22 29 80 14 94 92 79 18 82 54 41 7 40 17 81 61 56 77 1 62 47 80 77 60 64 68 0 14 7 3 45 41 70 56 64 87 40 48 46 0 95 42 77 20 96 75 45 63 14 91 86 44 67 97 29 56 35 82 51 18 88 38 79 12 12 47 98 66 93 23

72 33 90 56 30 39 42 9 44 80 9 60 67 48 70 53 19 48 86 10 60 52 66 75 68 34 76 33 82 29 17 35 14 14 10 76 85 43 13 74 11 69 85 44 45 4 28 42 27 3 8 13 60 20 82 55 21 37 26 93 47 40 66 66 0 91 33 17 20 44 59 88 62 37 46

92 46 0 28 15 53 65 51 19 90 5 40 39 71 79 51 31 46 67 86 15 16 90 41 88 7 45 71 27 45 38 50 12 12 82 48 82 75 56 99 99 78 51 79 72 27 67 2 82 70 0 84 36 84 16 40 6 36 16 7 32 23 37 96 95 15 87 70 19 62 30 40 92 97 84

52 13 82 14 15 47 33 23 67 12 39 38 65 33 22 55 2 7 51 1 77 28 2 56 66 18 42 41 67 73 29 12 70 28 15 33 16 73 82 45 64 8 28 65 57 82 6 57 44 97 28 94 44 28 56 19 50 94 13 55 15 44 42 92 12 26 94 80 58 90 50 27 78 65 35

19 74 60 20 15 75 0 11 91 89 8 52 43 89 40 72 55 29 92 79 72 41 85 94 13 37 22 49 51 85 69 56 13 55 28 78 86 70 63 38 95 68 23 26 39 66 9 49 41 38 34 51 19 39 10 46 45 62 10 93 44 6 58 10 62 33 58 53 85 7 44 46 82 36 47

85 51 11 37 91 62 32 93 13 25 17 46 32 5 81 74 91 32 45 33 6 11 39 51 17 68 3 12 48 9 97 27 98 18 98 86 56 75 4 16 95 16 99 0 69 87 31 2 27 66 87 60 77 13 5 4 85 4 21 4 90 25 2 27 19 35 54 51 24 88 61 1 6 27 54

17 45 81 21 71 78 76 38 59 43 31 50 79 94 86 82 24 88 95 56 40 35 0 3 24 61 75 48 46 14 31 76 25 64 62 56 55 33 34 56 83 57 46 58 40 58 17 53 91 64 89 50 25 93 60 17 38 39 20 97 5 24 48 6 60 85 53 13 16 71 21 39 11 50 87

56 19 6 60 66 71 80 16 84 1 48 1 78 2 38 85 52 43 36 95 69 42 28 6 59 49 15 6 80 89 27 49 94 86 45 52 95 6 98 73 70 53 59 48 0 93 29 73 36 22 53 96 4 76 45 47 96 11 48 46 54 29 55 43 44 26 19 93 38 91 67 78 88 22 88

64 74 53 13 20 18 65 62 81 92 7 28 59 4 96 27 6 41 57 85 52 76 53 11 23 75 29 70 33 30 26 34 79 43 67 15 43 54 47 68 25 28 26 8 26 24 53 19 85 68 42 73 24 30 89 88 35 61 81 22 93 25 3 36 72 31 47 15 74 83 10 62 52 15 57

85 33 58 67 42 14 98 1 23 78 92 98 54 53 90 97 78 15 32 26 92 54 67 2 19 94 51 0 6 81 18 30 31 96 38 50 34 51 16 86 99 39 9 94 49 11 41 87 67 90 48 5 61 85 29 98 0 76 64 55 14 89 75 2 32 98 28 46 27 27 40 75 78 20 81

90 30 3 77 22 3 87 49 63 27 16 89 40 14 53 93 62 19 8 58 37 21 74 28 75 33 98 56 46 77 29 39 37 15 48 15 91 82 89 21 99 65 54 22 57 3 92 34 78 38 44 82 52 77 64 58 84 86 54 88 92 40 86 96 13 81 61 54 17 13 23 51 31 26 12

53 72 97 25 68 58 93 67 63 88 72 10 74 13 38 0 56 30 7 65 82 57 32 60 23 24 43 49 45 99 73 3 55 13 35 15 44 51 4 8 28 57 33 98 16 64 96 69 84 86 85 76 54 9 8 31 7 91 80 84 60 26 41 38 82 36 52 74 66 37 55 48 59 6 10

76 60 42 92 29 48 21 25 9 93 37 27 26 69 31 28 22 45 76 87 70 78 21 34 7 86 84 97 51 68 0 70 70 22 54 51 88 84 32 38 91 82 51 22 44 97 56 6 83 11 12 19 28 91 1 7 8 76 57 11 90 78 42 31 44 81 70 50 59 58 93 50 86 89 38

90 69 9 66 78 95 99 43 68 3 51 44 59 31 86 45 91 73 13 1 93 18 47 97 11 58 81 90 20 81 23 20 62 70 24 30 49 47 34 44 29 78 32 40 75 32 76 64 35 13 32 58 75 34 60 81 21 86 64 12 95 26 67 70 73 8 16 74 38 21 42 68 55 59 91

52 87 44 24 62 81 15 29 87 99 49 7 81 30 4 64 6 61 25 92 20 33 48 50 22 33 83 18 50 94 48 38 69 50 82 24 43 32 45 11 61 93 63 50 90 61 9 77 57 4 22 75 4 14 91 94 80 14 98 72 53 65 63 26 34 73 35 70 1 69 8 85 15 16 17

17 61 49 51 85 77 9 71 66 70 70 75 26 20 16 16 35 68 12 35 63 43 33 22 40 19 67 92 74 47 7 77 9 24 36 9 63 28 46 2 75 25 20 26 97 66 64 4 65 82 94 14 25 17 38 31 50 27 92 14 77 66 3 59 85 39 45 99 54 13 56 95 46 55 60

87 42 92 3 44 27 49 91 86 16 10 67 46 29 23 20 50 85 37 16 32 27 87 83 33 53 32 44 69 87 87 62 0 96 23 28 93 51 10 39 6 96 73 26 97 5 75 31 35 27 25 93 21 71 76 68 36 71 48 29 57 11 86 43 0 82 17 86 22 52 20 57 30 39 51

14 62 53 40 60 16 21 7 35 16 8 1 37 99 37 59 54 86 23 5 87 26 83 47 77 0 45 73 87 65 27 52 7 4 67 5 25 86 61 59 22 31 57 46 0 61 8 11 76 27 80 25 15 64 92 59 90 63 61 70 61 29 41 42 81 39 68 42 31 21 32 63 8 38 51

71 62 76 49 10 48 11 17 86 14 12 21 50 8 90 3 16 3 60 61 59 96 52 81 85 42 55 65 60 94 85 97 66 80 15 22 87 1 68 63 32 82 49 69 44 31 50 13 59 4 37 2 41 51 58 40 13 7 26 6 36 47 74 35 22 80 42 63 55 35 99 77 11 39 29

6 64 99 56 91 78 66 92 61 35 16 91 47 42 91 45 82 12 18 15 42 18 60 14 19 95 41 5 92 63 53 74 76 0 48 41 74 67 47 64 17 29 52 49 14 65 73 13 56 46 23 90 15 9 40 6 86 72 2 14 46 42 19 17 40 66 63 75 2 24 22 8 36 22 89

0 39 48 87 79 1 26 61 88 49 70 98 19 44 17 49 71 24 79 64 4 88 76 54 55 47 68 25 58 52 81 46 3 68 87 76 46 16 49 18 2 99 73 19 30 30 75 90 82 55 71 18 13 70 26 54 12 60 82 28 21 42 52 76 76 74 73 58 59 89 52 97 53 60 42

17 10 76 49 40 50 89 85 77 80 87 12 57 66 5 58 66 39 13 99 71 81 24 74 57 39 8 35 75 64 24 88 30 83 38 48 17 5 1 70 3 73 35 80 18 51 8 92 6 3 82 50 45 8 24 84 18 9 33 61 38 92 9 85 56 40 75 23 38 21 28 74 7 21 91

23 17 31 6 51 21 27 28 26 52 38 63 83 55 46 47 5 68 59 57 15 46 84 93 40 50 33 27 49 31 80 89 76 72 80 77 26 11 88 2 96 70 33 58 5 57 0 46 37 85 87 62 95 77 87 7 40 54 31 44 73 57 77 97 45 94 36 19 65 42 16 17 8 24 9

56 72 72 10 18 58 89 35 17 19 99 57 42 55 33 96 53 22 55 85 9 64 43 21 72 76 33 35 52 88 44 78 78 50 40 58 72 0 80 34 45 55 66 64 45 39 64 68 98 29 78 31 31 74 9 69 4 2 65 83 62 55 54 51 97 5 63 73 75 1 66 40 34 51 39

40 28 40 57 72 88 65 88 87 11 2 92 23 57 46 26 39 81 61 26 77 70 3 75 31 29 52 44 63 75 32 92 91 25 11 33 90 57 11 2 81 46 76 21 53 52 83 6 2 65 94 7 7 90 78 47 61 92 0 8 56 7 4 97 62 68 73 44 84 71 24 75 39 79 99

75 69 74 10 86 78 49 25 39 56 58 84 61 62 53 96 85 12 37 17 21 66 43 6 19 59 57 16 80 77 74 39 74 54 75 44 29 25 52 8 95 71 18 7 44 34 36 53 33 22 18 66 13 29 32 10 38 33 24 78 30 59 74 74 53 78 45 60 83 81 46 0 53 17 44

41 59 90 93 59 89 54 89 40 18 90 22 2 61 63 25 78 52 27 95 32 20 64 16 4 89 23 95 57 23 11 2 34 56 61 27 37 65 99 58 41 75 5 56 85 85 74 73 50 53 34 3 67 51 5 66 38 31 57 14 60 89 81 12 20 63 56 69 14 14 90 1 52 61 67

9 10 71 29 40 59 95 43 28 71 28 85 21 30 12 15 40 79 76 53 65 35 29 5 56 3 19 50 27 96 48 14 31 79 46 76 91 85 54 84 25 1 78 54 33 57 40 2 14 93 4 7 38 29 4 50 95 97 70 7 33 52 77 17 13 4 41 29 64 94 44 39 89 44 18

12 28 46 63 56 93 80 87 79 57 95 53 31 86 96 93 86 83 8 43 54 57 2 13 20 72 1 8 84 37 3 59 19 38 98 16 74 16 61 95 18 15 18 96 99 39 64 48 27 66 16 8 16 31 71 41 89 79 6 62 9 86 58 22 63 45 88 66 27 51 47 46 83 14 92

33 4 2 59 60 54 9 21 62 50 87 65 70 83 70 28 63 25 89 43 72 5 21 15 89 84 73 85 25 97 22 87 28 1 98 42 18 38 38 23 51 81 99 90 74 23 76 24 80 65 21 93 82 71 96 89 36 53 34 88 98 55 68 4 88 69 47 64 16 86 60 73 18 40 11

18 23 50 25 2 38 82 27 3 47 17 89 71 59 16 54 9 18 3 52 0 36 47 8 93 63 67 58 26 1 91 41 58 37 11 5 96 8 97 24 26 74 28 90 82 95 51 52 11 70 26 40 54 12 36 2 31 60 75 46 1 37 53 55 88 16 61 61 65 46 96 35 90 83 72

22 46 3 57 43 30 8 53 13 57 21 66 27 53 22 80 8 22 91 99 67 67 87 95 39 80 51 18 31 47 36 65 3 94 58 18 34 29 24 91 49 90 54 49 65 16 55 11 14 46 10 56 24 24 59 95 22 42 65 77 0 1 90 73 67 36 57 12 0 36 11 22 69 94 31

88 73 44 15 8 80 93 33 52 18 64 79 66 89 83 17 77 92 21 56 62 21 76 28 26 85 68 63 34 38 22 39 94 92 82 22 39 91 16 36 31 52 13 25 24 26 59 65 92 16 4 35 50 39 1 18 37 62 97 14 49 57 65 12 78 14 19 28 46 51 18 70 2 0 11

23 20 28 58 30 55 75 17 68 55 16 40 76 70 7 78 77 26 95 14 39 10 51 16 55 5 47 46 66 37 99 18 90 6 28 36 60 98 11 59 92 62 90 91 54 43 27 63 8 5 1 55 54 58 68 89 61 41 97 28 26 69 9 59 10 7 34 15 31 93 1 13 73 18 98

98 57 77 6 25 4 11 39 59 45 97 88 63 61 12 59 73 48 47 39 81 86 88 70 84 93 82 36 25 54 80 58 8 43 37 81 11 26 59 32 11 68 56 68 45 31 86 29 26 29 12 96 38 65 94 17 59 92 98 79 46 93 63 65 85 94 57 62 97 77 15 52 60 3 65

57 21 11 63 25 46 75 29 31 62 58 26 40 28 33 75 82 6 80 41 51 84 87 2 55 44 81 9 11 69 7 79 65 33 30 50 83 56 58 49 3 48 62 12 87 91 91 38 17 75 7 32 28 77 24 65 77 72 81 29 12 83 93 92 91 67 60 40 93 35 23 96 65 47 79

[出力例]

1960

■参照サイト
AtCoder Regular Contest 025

2020年4月27日2020年4月28日

C++ の動作確認をしてみた（２０９）

C++の練習を兼ねて, AtCoder Beginner Contest 164 の問題D (D – Multiple of 2019) を解いてみた.

■感想.
1. 方針を決めるのに時間かかったものの, AC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 164 解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int r[202020], t[202020];
LL m[2020];

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    int l = strlen(c);
    
    // 2. 10 の 冪乗 について, 2019 で 割った余りを保存.
    t[0] = 1;
    repx(i, 1, 202020) t[i] = 10 * t[i - 1] % 2019;
    // rep(i, 10) printf("t[%d]=%d\n", i, t[i]);
    
    // 3. 2019 で 割った余りを 保存.
    // i文字目までで, 2019で割った余りを保存.
    repr(i, l - 1, 0){
        r[i] = r[i + 1] + (c[i] - '0') * t[l - 1 - i];
        r[i] %= 2019;
    }
    // rep(i, l + 1) printf("r[%d]=%d\n", i, r[i]);
    
    // 4. 余りの個数を集計.
    rep(i, l + 1) m[r[i]]++;
    
    // 5. 条件を満たす整数の組は？
    LL ans = 0;
    rep(i, 2020) ans += m[i] * (m[i] - 1LL) / 2LL;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int r[202020], t[202020];

LL m[2020];

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

int l = strlen(c);

// 2. 10 の冪乗について, 2019 で割った余りを保存.

t[0] = 1;

repx(i, 1, 202020) t[i] = 10 * t[i - 1] % 2019;

// rep(i, 10) printf("t[%d]=%d\n", i, t[i]);

// 3. 2019 で割った余りを保存.

// i文字目までで, 2019で割った余りを保存.

repr(i, l - 1, 0){

r[i] = r[i + 1] + (c[i] - '0') * t[l - 1 - i];

r[i] %= 2019;

}

// rep(i, l + 1) printf("r[%d]=%d\n", i, r[i]);

// 4. 余りの個数を集計.

rep(i, l + 1) m[r[i]]++;

// 5. 条件を満たす整数の組は？

LL ans = 0;

rep(i, 2020) ans += m[i] * (m[i] - 1LL) / 2LL;

// 6. 出力.

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

return 0;

}

[入力例]
1817181712114

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

[入力例]
14282668646

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

[入力例]
2119

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

[入力例]
5927561483499133816681483285962193978296762292135521819997344122591819263711514166282293149468917732931372373582374231754637521338415522734986783746251827878858734285992236975761669764917192519634598499956141881618566486524156655583242728247725527832955998571927419919664517757174362165539848928432818819783288418317797891449995554482781481393773592238658854731667832175299162387233899479317587693629389288842517584816558249714533418663147625787276558616452141341356183268829976755771374161469264246991695389539282469276854743339244587176376811562583349151716683359386276825445915243943354271813118549572889596242256983768973299179492513813963166548373125884168652873488175139512567463419394877115371555596287468718681524769631398116896779714269685182377121875661883216277146935177167586657246684288426748585746111476633777625397857847791227846447781527652718365152611432287777972799773917717781292899491177181763659662268342866844661496823674993676359949711779674315715974281427356378439739315378244

[出力例]
211

[入力例]
97228238287242445316297743562293571698136258547357947664137676744787922269777911237528513861156186597324215846711127225828383558398319668244438459791753997581456126356261444731242776625764281311725613586397355614863752185811558675894635782967131872611431961158726691611425372722522665562681397975849497213965444742673553893915738645335128683673445578328225595493367171282659242892738752912911295787728215545426317145765628211362272374621969166257832285662363327561255897553853755271682266589525832262998889511715134226227154168212957786988328833191116875523548248455337535768365192923268929249874252126353512169866142966837557181422476466664955338134995881877252549618484182117218174122345398527169659642974627611471686184974374711987267623722773168192325477251751112133853763142417349415588322718385649659277221955384597588288176942628819731316544956935313883188633594571632613627766446643344927916349262771849311952587942677424288597585719968582134592698486959177783652764624175377469794827765346732911681649683413359145657988387492643414545325548837665575782416266892673692242364852675888531883526188461253945634113343286132513753585429947347372182593937985691453898465646446328747476274628154626297728935929953963898585918952811194147453916579168677672849821641933797722838938131542725837493913632992868367511339571668683828757739439956776122533293988889366784276374449214611872968942766922197779245996138537356134544698285131447816325558292577977548997853545522541448564824254479552321573399161123858827775385673488888495171737135739813928898754687367471134342693644164131174171545574941826528427248586426552437675241235972977272345518584125696796554613138697921324262591952918769893453287613249588119729333127965727212523556327126578141191375412541173713993162573285279976924655946263372519781349757669742328633567424128564312983372961442361631729926886814765664416273472295425554788847482942948379576435668296624794167157396645865427116931783746691476553952571459849762988567564214879132449873556937523212355725797428589474797685711535266513659394965935668687213882692816114744615356364781193973474619154221235759458314558489459818965936398842619375793188515872183129862358876577169777912757425334157419846998291713446764485567616995892432831774597473521269819277463276769345974943498375191863972984823235142339889637588736784269885985178552494447613562928448216147945673917615598679589629253937317614917195696198885316852914554918923238714647639513723477973155731356137112939947447454199248156415441747484149628483197329943878929171175788144434732954751896639559581292591957192638738932366443292999897583481226822891974225397453736381741998794469259947943421485918733756913221337924182313664899545531347374627619465397854734563419612962411255119972155175329931192982535934679935817947879265869983716856415652318195538225753828974793188889555569586176645879365184938433548174975733475178135257787886319618655824223462264769987925648418787766388455684643635816723297682311411587958118557972187116388476365933846454153362762238752759236612132584938618487639823343284949381224833396899911947775327981843262267362719922371877171585449155587545165176552397735931948777996667366677518287742189283451238862721982492612381753749972918459915757555275584426511598563278658311551589383488445451524985579351172293185142483352644298691416337389149215939353432317873623126293968676899498552693579268721435763459196423676442256957975362317726757864711193656262441342285212133985684361254816834143942551699442713829821876946336457868557937447545824455676834126317469182728672178557721544161737438235514642948656468391636319523116282696412734467791264413588474768494392835243221588166749523645165749472568641872764471849417478877454129149549518369989338692421774463976846343183935668135331961583712358461389781711724313474268117692477213625547261341363439281529343523788281942466236422758367325758213943348125311549725776431347671831847574929543284595844629115775117425823339744265127713698168615416336529916877581271688657217772772435329644139157618137634485387723415565646432779293522887785156918468698516218614156274927973235896957571974791524816269874973671959444618289434314627755921979641898942733647766815622882772532495253578612768527242213782636572443917973346391873358554189786439549173297542257457134627899514861847733767584125193843272652244466828835422452486492353835634625832342443536365222222288973721854255556685515895826221239521875471163879644365468485892466864739371584695792168599647968337932994954135341266123577555648515777656789918858723999514782758128383895895882648244295599999331123488235421364424247863674626585546875693179888692886778561772126339861922952724187529467443533224559739134238214389158953211824727428645523684638663959614215634286796921985531546371114983389237869757514117439656498279733918869886253524876447165831113865315312634612817552774589541182855661786459353989634922818962858643144565765531828745374841759773978732631399712455296473473552914328121479323762592182

[出力例]
6199

[入力例]
7659183897322581891441989417986522374719288564486137788587674721377878883159646365746363295255165129311581347555687884227489157749189591898738479514317888816248967165179829283276392434515956864326728221229728881257776356664878151211974914556868799938983352133475239727528421484656773281212727248642975331924732498222379128527119286615753355876978129291294846951793899362666563268474157666719546578474784124934184364866482226411334895149385186482573319694335391552913622269474868443726149576378754894269828835275524388692222346735534682281374644484574418711874514877756255212275792495739718226521827867537426952561597794785168763896168361352586881641572159283855129653847599888739264822278846934248972139944957676353334227121173448665127884696983933297885632168751861931155176281879546699648134131362739137317563564868435252661715479846149666181226718955959184398458596836155838232871169673863145224918563958187747631635155127437847679765347137373613385993619299314428364783212512678498836453297143981184695499798225152175649338675359279762274321564465678287316537447492174867579714232538435151468162472762564798948341138783847132856655672288638789918218672423359565556926812879113627929597664521446687895722863346417892781952917446229641769457337257952191472355468332969175769283815595636755423127835879669651575774415771954536781788862525939683915965495515994651825178797161978793589713917852215953263174812399976861948192875565146794919757651235237941319161711515966124265817755129852746179111712775762121952541557986275243758243696141818686275549522675973938133534244676293177165927825736182674177736526811242477111885163337212821696438241498992189559169598399149776884174121662446468818868465817322497833191567181764783215143315598873958481824725493435566592825841657234696365485222648892166481952517229591639529423588217345951872984864351734186334327735814288334563757759556411276219337386575153444739728375537487937693539223598146494698938113179331921239349493956472668989143812365898711398724693572739485475432259573622128597565438285271443215233216116634588855911514324495767311988688797877653539598383513826754632137458764233637852659848382751522189497287911598128491556467671944167396435591256746466685298727167414385649981543941632293441135938747687883175579177625367916944212353193383282699829214313573518355923575692126394947311582697946423543156566649766411861615895513972937467375734156199354532141982184164418259585184715924488388593893644292825257425673999732121341963671336995852288421545224663395854991889513488519712245932548118714291893685249331286356265485392659357695294417958549197441934521535866479761228292527845912991132768679437843847833591628661373269961622857945624553212744855818932341821631997186932896462661247523174154525586811625569731452977713883435833833769271458299657452826774267839887366337527279529566789794861799248241851521366467684926532819286458492812367714869251417654712139654251542628418491754794196457632171149687232834863416276667918726759743899478235853216545334373297655583472861964662258885589437363335877823743243189748711785468518223351943135516444361684123985611474787168356819531541671615541898814141984491843827163841885864875333472559226176927866296383258957732185484586862627287331274121648812366776824128494656761431678163181378356233991261943836757645747376122374846631245472966579218459377149617714334118452615777375765774158833335619853412316646696136838376317314214752711698946893965422252652961253615617566475933758368796587757726878118539882414652713296541451311584116363188723365262477631238378833384894456127275457498781546336764472563125541488862836713368531976241562636299927592272186783219374764137455774341916957622224457543523916578831134443275173552655558617789968262515739796869854863666133536698211981692336914755656771981132582631252499648898827938848734887948879678126676449936832957342661137625496372992171969281916713445999413935742213242327438511557443183872287655737768515839247873731759186359987424876834142423517944568986996448125425427257996412385337613285898736295817358494797772845711446783446728155768799658443363952285437724678126947168316924149858624237646695154112619957654213434323162128571989844146262959625549949368144862595742467191245232876661128826848371521393518343529755573596743813196123624159223817645558137571547614828451916365542515478488891444366719983288294947476976764174662293119552922632993749439862263198567758533521933794312113465254261131416187675851513336696958284738244411836274552228654749411469332797189891526542869957454776778334693133694597752823582988383821151279356291459653445982511732296335392136377265887912734332545153971526451528111326675533744577593944395571724375543761638269832394883553187676987343497657837759454379794771323621985491498677256322793168178487471353217742272279567142764931236819773792235221351714365256436788674531828537132981799158511184952458334366314476628726775871162698169597661342276529294185932212977855992614552357377296656182822915166432962273445211758182981924982284762143973853766482688712661919669641283885769981893284287622565557994571729299629645758964653876147248746672879834948928668768954783754353864676236331496613788153533636368588143847877171598649493762621256654677897234967435513698755465783485749439337734833725316453326673439826259284741753142371887437333524486385456438624758245672858111144628183529385554228576217994922215465491561577838883987928276899971495998261584325634392914722794811269449271272426481933554215625238941982536524896535498293827484442827343192712687835918666663532856658256312967673256753468829718816599655813277233424659818456265181966286672169633266848588364136572978161846945519551821431826174772451553777756165338713841355365746326334267937632789735548194471733938323842392792872572334114322578868396497657174458448222117597975398774729157618612869994331848822155474186433426839456574529823361495559573842748993736574463127179367665535361685645541993893975951533185821897171769459562882299814477366394744935187967923612468552295928821881289948588725256775969242512682274484129654979268841482718421355445728657299745417366771884141114558764931729334967196513514636983653739881385536447975921553219216473258286635448244515638937529923922637669396123761712741797622438835777131746317546665421671394734173152328313813421787512593655336478931415871697138898361212813764836327217569847519267917321794211671329996538778241967786869652733366576979616293357672831848872838157899571618444395437968133229317145871983584328712463322512328114224832783254333749918515738775396571461646413338712417461327645799463444584852928414328267466454446783395857176455333635223824488399717162215349229984686699181655788999647994515866293879677361839682576982914484612424255623672813914273881856322864129337358591635479167989341264452746428786117313748162598556619964778946963873388332939797291487851869444976231781623364519878961179952165441352748346375774924552896991959287619748112973226576839669568337565916339681211258218959418845332393132977869121732467692645531389382511548736145338717111342917194878784351754629674177315983713159687787736552712771794836684213953922152182286877768371124526452339989915299624739425557922669828318369452982423695734393795644524462716421963573245873295133882643166911131561213281568525996387573376688398346238184841444558259977452163641473589869325772641334222414552498868664381853164287895359412817116579863352615629738467792425267865535937724959687858379632376937611499643124713647859697296134512755281573585921831672263229314574232648412294211277827446588679662665443167183456921642221948766553773457615785377387559245456468775628988278814793621887499434934762884949791552373313715622184748764732544818627471726926755892776696275771875196587145934591844771494411293528331393186253171441687793695393414892312548287949749167861519582458657957462973418288145632411916812417582145252114624689379511976444526467391167631957592389334276872719475463497913458672388634234461265852816461755259634559642689854685496515229776944921928743548699654943622111815266367374293423473514964418527443966179964416957281361263549494287752433281185651594893852231441455267363954987753239631343662986323512259749294141157829741792554788472755325233965396449185788425295756577783623552311573882428338591817771571653933954954856777613212122753641145376495747442979941127986386813636554816772856948337953952639242971354636379172812323284251292794351522136179139464943968598293553913864746716128624258598683213311575967591454113517299765546414543919816683711355967877787549884262242627732597195824288756241994278166691596374926953186789863534178969543421764488834181751813237158179838779278328591817372634663338186545346537294356551546279911577475348774972596446845458513962996572425411122691922689821964655667294544563133286758744829441957432194484851926374687167979339443678127361284393444628319452828717648527661338939651158546337271584737637163297366442799276227657654354696889832559678569496263663752862364526636155781626529447526162253975689848799348857767272814319653727859334573347541868529734989421416966642597662355941875741951873693495183552779593959545672517146231884794936873173427415235157291188396298421629538513694137549647752489588258285992715558879972928538496999721968494581931169329665633948676714627449869697546112338386626418982691247944746865374454949189999853261618995752299936544357648339789743916597361265128257281892539633169868162447952176384978166217224558632269493356686838675821431377233494887234861697632711816999326825929497238268797213335259481495157282142276475679374946855216244599667889642648328969747438664447813177633816781548786528851411761594648132219239624752953714811517766329344683983389498969972365766331787183378416719493562311664687865737499895162562282281177971924526331454921959775425157841428358832774235251643216391735182581825466334153948483536744626512265326573979365879285918657274514881685787185144177443985438743376373446634498619192128868891588498365323742249583

[出力例]
24593

[入力例]

1817181712114

[出力例]

※AtCoderテストケースより

[入力例]

14282668646

[出力例]

※AtCoderテストケースより

[入力例]

2119

[出力例]

※AtCoderテストケースより

[入力例]

5927561483499133816681483285962193978296762292135521819997344122591819263711514166282293149468917732931372373582374231754637521338415522734986783746251827878858734285992236975761669764917192519634598499956141881618566486524156655583242728247725527832955998571927419919664517757174362165539848928432818819783288418317797891449995554482781481393773592238658854731667832175299162387233899479317587693629389288842517584816558249714533418663147625787276558616452141341356183268829976755771374161469264246991695389539282469276854743339244587176376811562583349151716683359386276825445915243943354271813118549572889596242256983768973299179492513813963166548373125884168652873488175139512567463419394877115371555596287468718681524769631398116896779714269685182377121875661883216277146935177167586657246684288426748585746111476633777625397857847791227846447781527652718365152611432287777972799773917717781292899491177181763659662268342866844661496823674993676359949711779674315715974281427356378439739315378244

[出力例]

211

[入力例]

97228238287242445316297743562293571698136258547357947664137676744787922269777911237528513861156186597324215846711127225828383558398319668244438459791753997581456126356261444731242776625764281311725613586397355614863752185811558675894635782967131872611431961158726691611425372722522665562681397975849497213965444742673553893915738645335128683673445578328225595493367171282659242892738752912911295787728215545426317145765628211362272374621969166257832285662363327561255897553853755271682266589525832262998889511715134226227154168212957786988328833191116875523548248455337535768365192923268929249874252126353512169866142966837557181422476466664955338134995881877252549618484182117218174122345398527169659642974627611471686184974374711987267623722773168192325477251751112133853763142417349415588322718385649659277221955384597588288176942628819731316544956935313883188633594571632613627766446643344927916349262771849311952587942677424288597585719968582134592698486959177783652764624175377469794827765346732911681649683413359145657988387492643414545325548837665575782416266892673692242364852675888531883526188461253945634113343286132513753585429947347372182593937985691453898465646446328747476274628154626297728935929953963898585918952811194147453916579168677672849821641933797722838938131542725837493913632992868367511339571668683828757739439956776122533293988889366784276374449214611872968942766922197779245996138537356134544698285131447816325558292577977548997853545522541448564824254479552321573399161123858827775385673488888495171737135739813928898754687367471134342693644164131174171545574941826528427248586426552437675241235972977272345518584125696796554613138697921324262591952918769893453287613249588119729333127965727212523556327126578141191375412541173713993162573285279976924655946263372519781349757669742328633567424128564312983372961442361631729926886814765664416273472295425554788847482942948379576435668296624794167157396645865427116931783746691476553952571459849762988567564214879132449873556937523212355725797428589474797685711535266513659394965935668687213882692816114744615356364781193973474619154221235759458314558489459818965936398842619375793188515872183129862358876577169777912757425334157419846998291713446764485567616995892432831774597473521269819277463276769345974943498375191863972984823235142339889637588736784269885985178552494447613562928448216147945673917615598679589629253937317614917195696198885316852914554918923238714647639513723477973155731356137112939947447454199248156415441747484149628483197329943878929171175788144434732954751896639559581292591957192638738932366443292999897583481226822891974225397453736381741998794469259947943421485918733756913221337924182313664899545531347374627619465397854734563419612962411255119972155175329931192982535934679935817947879265869983716856415652318195538225753828974793188889555569586176645879365184938433548174975733475178135257787886319618655824223462264769987925648418787766388455684643635816723297682311411587958118557972187116388476365933846454153362762238752759236612132584938618487639823343284949381224833396899911947775327981843262267362719922371877171585449155587545165176552397735931948777996667366677518287742189283451238862721982492612381753749972918459915757555275584426511598563278658311551589383488445451524985579351172293185142483352644298691416337389149215939353432317873623126293968676899498552693579268721435763459196423676442256957975362317726757864711193656262441342285212133985684361254816834143942551699442713829821876946336457868557937447545824455676834126317469182728672178557721544161737438235514642948656468391636319523116282696412734467791264413588474768494392835243221588166749523645165749472568641872764471849417478877454129149549518369989338692421774463976846343183935668135331961583712358461389781711724313474268117692477213625547261341363439281529343523788281942466236422758367325758213943348125311549725776431347671831847574929543284595844629115775117425823339744265127713698168615416336529916877581271688657217772772435329644139157618137634485387723415565646432779293522887785156918468698516218614156274927973235896957571974791524816269874973671959444618289434314627755921979641898942733647766815622882772532495253578612768527242213782636572443917973346391873358554189786439549173297542257457134627899514861847733767584125193843272652244466828835422452486492353835634625832342443536365222222288973721854255556685515895826221239521875471163879644365468485892466864739371584695792168599647968337932994954135341266123577555648515777656789918858723999514782758128383895895882648244295599999331123488235421364424247863674626585546875693179888692886778561772126339861922952724187529467443533224559739134238214389158953211824727428645523684638663959614215634286796921985531546371114983389237869757514117439656498279733918869886253524876447165831113865315312634612817552774589541182855661786459353989634922818962858643144565765531828745374841759773978732631399712455296473473552914328121479323762592182

[出力例]

6199

[入力例]

7659183897322581891441989417986522374719288564486137788587674721377878883159646365746363295255165129311581347555687884227489157749189591898738479514317888816248967165179829283276392434515956864326728221229728881257776356664878151211974914556868799938983352133475239727528421484656773281212727248642975331924732498222379128527119286615753355876978129291294846951793899362666563268474157666719546578474784124934184364866482226411334895149385186482573319694335391552913622269474868443726149576378754894269828835275524388692222346735534682281374644484574418711874514877756255212275792495739718226521827867537426952561597794785168763896168361352586881641572159283855129653847599888739264822278846934248972139944957676353334227121173448665127884696983933297885632168751861931155176281879546699648134131362739137317563564868435252661715479846149666181226718955959184398458596836155838232871169673863145224918563958187747631635155127437847679765347137373613385993619299314428364783212512678498836453297143981184695499798225152175649338675359279762274321564465678287316537447492174867579714232538435151468162472762564798948341138783847132856655672288638789918218672423359565556926812879113627929597664521446687895722863346417892781952917446229641769457337257952191472355468332969175769283815595636755423127835879669651575774415771954536781788862525939683915965495515994651825178797161978793589713917852215953263174812399976861948192875565146794919757651235237941319161711515966124265817755129852746179111712775762121952541557986275243758243696141818686275549522675973938133534244676293177165927825736182674177736526811242477111885163337212821696438241498992189559169598399149776884174121662446468818868465817322497833191567181764783215143315598873958481824725493435566592825841657234696365485222648892166481952517229591639529423588217345951872984864351734186334327735814288334563757759556411276219337386575153444739728375537487937693539223598146494698938113179331921239349493956472668989143812365898711398724693572739485475432259573622128597565438285271443215233216116634588855911514324495767311988688797877653539598383513826754632137458764233637852659848382751522189497287911598128491556467671944167396435591256746466685298727167414385649981543941632293441135938747687883175579177625367916944212353193383282699829214313573518355923575692126394947311582697946423543156566649766411861615895513972937467375734156199354532141982184164418259585184715924488388593893644292825257425673999732121341963671336995852288421545224663395854991889513488519712245932548118714291893685249331286356265485392659357695294417958549197441934521535866479761228292527845912991132768679437843847833591628661373269961622857945624553212744855818932341821631997186932896462661247523174154525586811625569731452977713883435833833769271458299657452826774267839887366337527279529566789794861799248241851521366467684926532819286458492812367714869251417654712139654251542628418491754794196457632171149687232834863416276667918726759743899478235853216545334373297655583472861964662258885589437363335877823743243189748711785468518223351943135516444361684123985611474787168356819531541671615541898814141984491843827163841885864875333472559226176927866296383258957732185484586862627287331274121648812366776824128494656761431678163181378356233991261943836757645747376122374846631245472966579218459377149617714334118452615777375765774158833335619853412316646696136838376317314214752711698946893965422252652961253615617566475933758368796587757726878118539882414652713296541451311584116363188723365262477631238378833384894456127275457498781546336764472563125541488862836713368531976241562636299927592272186783219374764137455774341916957622224457543523916578831134443275173552655558617789968262515739796869854863666133536698211981692336914755656771981132582631252499648898827938848734887948879678126676449936832957342661137625496372992171969281916713445999413935742213242327438511557443183872287655737768515839247873731759186359987424876834142423517944568986996448125425427257996412385337613285898736295817358494797772845711446783446728155768799658443363952285437724678126947168316924149858624237646695154112619957654213434323162128571989844146262959625549949368144862595742467191245232876661128826848371521393518343529755573596743813196123624159223817645558137571547614828451916365542515478488891444366719983288294947476976764174662293119552922632993749439862263198567758533521933794312113465254261131416187675851513336696958284738244411836274552228654749411469332797189891526542869957454776778334693133694597752823582988383821151279356291459653445982511732296335392136377265887912734332545153971526451528111326675533744577593944395571724375543761638269832394883553187676987343497657837759454379794771323621985491498677256322793168178487471353217742272279567142764931236819773792235221351714365256436788674531828537132981799158511184952458334366314476628726775871162698169597661342276529294185932212977855992614552357377296656182822915166432962273445211758182981924982284762143973853766482688712661919669641283885769981893284287622565557994571729299629645758964653876147248746672879834948928668768954783754353864676236331496613788153533636368588143847877171598649493762621256654677897234967435513698755465783485749439337734833725316453326673439826259284741753142371887437333524486385456438624758245672858111144628183529385554228576217994922215465491561577838883987928276899971495998261584325634392914722794811269449271272426481933554215625238941982536524896535498293827484442827343192712687835918666663532856658256312967673256753468829718816599655813277233424659818456265181966286672169633266848588364136572978161846945519551821431826174772451553777756165338713841355365746326334267937632789735548194471733938323842392792872572334114322578868396497657174458448222117597975398774729157618612869994331848822155474186433426839456574529823361495559573842748993736574463127179367665535361685645541993893975951533185821897171769459562882299814477366394744935187967923612468552295928821881289948588725256775969242512682274484129654979268841482718421355445728657299745417366771884141114558764931729334967196513514636983653739881385536447975921553219216473258286635448244515638937529923922637669396123761712741797622438835777131746317546665421671394734173152328313813421787512593655336478931415871697138898361212813764836327217569847519267917321794211671329996538778241967786869652733366576979616293357672831848872838157899571618444395437968133229317145871983584328712463322512328114224832783254333749918515738775396571461646413338712417461327645799463444584852928414328267466454446783395857176455333635223824488399717162215349229984686699181655788999647994515866293879677361839682576982914484612424255623672813914273881856322864129337358591635479167989341264452746428786117313748162598556619964778946963873388332939797291487851869444976231781623364519878961179952165441352748346375774924552896991959287619748112973226576839669568337565916339681211258218959418845332393132977869121732467692645531389382511548736145338717111342917194878784351754629674177315983713159687787736552712771794836684213953922152182286877768371124526452339989915299624739425557922669828318369452982423695734393795644524462716421963573245873295133882643166911131561213281568525996387573376688398346238184841444558259977452163641473589869325772641334222414552498868664381853164287895359412817116579863352615629738467792425267865535937724959687858379632376937611499643124713647859697296134512755281573585921831672263229314574232648412294211277827446588679662665443167183456921642221948766553773457615785377387559245456468775628988278814793621887499434934762884949791552373313715622184748764732544818627471726926755892776696275771875196587145934591844771494411293528331393186253171441687793695393414892312548287949749167861519582458657957462973418288145632411916812417582145252114624689379511976444526467391167631957592389334276872719475463497913458672388634234461265852816461755259634559642689854685496515229776944921928743548699654943622111815266367374293423473514964418527443966179964416957281361263549494287752433281185651594893852231441455267363954987753239631343662986323512259749294141157829741792554788472755325233965396449185788425295756577783623552311573882428338591817771571653933954954856777613212122753641145376495747442979941127986386813636554816772856948337953952639242971354636379172812323284251292794351522136179139464943968598293553913864746716128624258598683213311575967591454113517299765546414543919816683711355967877787549884262242627732597195824288756241994278166691596374926953186789863534178969543421764488834181751813237158179838779278328591817372634663338186545346537294356551546279911577475348774972596446845458513962996572425411122691922689821964655667294544563133286758744829441957432194484851926374687167979339443678127361284393444628319452828717648527661338939651158546337271584737637163297366442799276227657654354696889832559678569496263663752862364526636155781626529447526162253975689848799348857767272814319653727859334573347541868529734989421416966642597662355941875741951873693495183552779593959545672517146231884794936873173427415235157291188396298421629538513694137549647752489588258285992715558879972928538496999721968494581931169329665633948676714627449869697546112338386626418982691247944746865374454949189999853261618995752299936544357648339789743916597361265128257281892539633169868162447952176384978166217224558632269493356686838675821431377233494887234861697632711816999326825929497238268797213335259481495157282142276475679374946855216244599667889642648328969747438664447813177633816781548786528851411761594648132219239624752953714811517766329344683983389498969972365766331787183378416719493562311664687865737499895162562282281177971924526331454921959775425157841428358832774235251643216391735182581825466334153948483536744626512265326573979365879285918657274514881685787185144177443985438743376373446634498619192128868891588498365323742249583

[出力例]

24593

■参照サイト
AtCoder Beginner Contest 164

2020年4月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 004 の問題A (A – 2点間距離の最大値 ( The longest distance )) ～問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

■感想.
1. 問題B は, 方針決まるまで時間かかったものの, 一番長い辺を固定すれば解けることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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 a first
#define b second
pair<double, double> p[111];

int main(){
    
    // 1. 入力情報.
    int N;
    double x, y;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lf %lf", &x, &y);
        p[i] = {x, y};
    }
    
    // 2. 最も長くなる線分の長さは？
    double ans = 0.0;
    rep(i, N - 1) repx(j, i + 1, N) ans = max(ans, hypot(p[i].a - p[j].a, p[i].b - p[j].b));
    
    // 3. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

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

#define b second

pair<double, double> p[111];

int main(){

// 1. 入力情報.

int N;

double x, y;

scanf("%d", &N);

rep(i, N){

scanf("%lf %lf", &x, &y);

p[i] = {x, y};

}

// 2. 最も長くなる線分の長さは？

double ans = 0.0;

rep(i, N - 1) repx(j, i + 1, N) ans = max(ans, hypot(p[i].a - p[j].a, p[i].b - p[j].b));

// 3. 出力.

printf("%.12lf\n", ans);

return 0;

}

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

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

※上記のプログラムだと以下のように出力される.
3.605551275464

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

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

※上記のプログラムだと以下のように出力される.
10.630145812735

[入力例]
4
0 0
0 100
100 0
100 100

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

※上記のプログラムだと以下のように出力される.
141.421356237310

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

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

※上記のプログラムだと以下のように出力される.
4.000000000000

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

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

※上記のプログラムだと以下のように出力される.
4.242640687119

[入力例]

1 1

2 4

4 3

[出力例]

3.605551

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

3.605551275464

[入力例]

1 8

4 0

3 7

2 4

5 9

9 1

6 2

0 2

8 6

7 8

[出力例]

10.630146

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

10.630145812735

[入力例]

0 0

0 100

100 0

100 100

[出力例]

141.421356

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

141.421356237310

[入力例]

3 0

1 0

0 0

4 0

2 0

[出力例]

4.000000

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

4.000000000000

[入力例]

2 2

0 0

1 1

3 3

[出力例]

4.242641

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

4.242640687119

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

#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 d[555];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &d[i]);
    
    // 2. sort.
    sort(d, d + N);
    
    // 3. 0番目, N番目の距離 で 取り得る値の最大, 最小は？
    // 3-1. 最大.
    int aMax = 0;
    rep(i, N) aMax += d[i];
    
    // 3-2. 最小.
    // ※ 一番長い辺を固定して考える.
    int aMin = d[N - 1] - (aMax - d[N - 1]);
    if(aMin < 0) aMin = 0;
    
    // 4. 出力.
    printf("%d\n%d\n", aMax, aMin);
    return 0;
    
}

#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 d[555];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(d, d + N);

// 3. 0番目, N番目の距離で取り得る値の最大, 最小は？

// 3-1. 最大.

int aMax = 0;

rep(i, N) aMax += d[i];

// 3-2. 最小.

// ※ 一番長い辺を固定して考える.

int aMin = d[N - 1] - (aMax - d[N - 1]);

if(aMin < 0) aMin = 0;

// 4. 出力.

printf("%d\n%d\n", aMax, aMin);

return 0;

}

[入力例]
1
1024

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

[入力例]
3
3
4
5

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

[入力例]
2
512
512

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

[入力例]
3
4
8
1

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

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

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

[入力例]
5
10
12
30
32
100

[出力例]
184
16

[入力例]
10
6
7
8
8
7
9
10
10
12
111

[出力例]
188
34

[入力例]

1024

[出力例]

1024

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

512

[出力例]

1024

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

100

[出力例]

184

[入力例]

111

[出力例]

188

■参照サイト
AtCoder Regular Contest 004

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題C (C – 魂の還る場所) を解いてみた.

■感想.
1. 各色のボールが, 偶数個か奇数個かで, 最後に円筒に残るボールの数が決まることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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;
    char c[101010];
    scanf("%d %s", &N, c);
    
    // 2. 各ボール(R, G, B)の個数は？
    int r = 0, g = 0, b = 0;
    rep(i, N){
        if(c[i] == 'R') r++;
        if(c[i] == 'G') g++;
        if(c[i] == 'B') b++;
    }
    
    // 3. 出力.
    printf("%d\n", (r % 2) + (g % 2) + (b % 2));
    return 0;
    
}

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

char c[101010];

scanf("%d %s", &N, c);

// 2. 各ボール(R, G, B)の個数は？

int r = 0, g = 0, b = 0;

rep(i, N){

if(c[i] == 'R') r++;

if(c[i] == 'G') g++;

if(c[i] == 'B') b++;

}

// 3. 出力.

printf("%d\n", (r % 2) + (g % 2) + (b % 2));

return 0;

}

[入力例]
9
RGBGGBGBR

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

[入力例]
6
RGBRGB

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

[入力例]
30
BBBBRGGRRBRBBGGGBGGGRBRBRBGBGR

[出力例]
0

[入力例]
100
GBRRRGGRRGGBGRGGBRRGBRRBGBBGBGBGGRGBBRBBGBGGGRGGRBBRBBRGGRGRGBRRRGRRRBRRGGGRRRBGGGBRBGBBBBBRGGRBBRRB

[出力例]
2

[入力例]
500
GBGBGGRBRGGGGBGGRGBBRGGBGGBGGGGGGGBBGBGGRBGRBRGGRGBBRBRRGRBBBGGGBRGRBRRRRBGBRBBRRBRBBBRGBBGRBGRRRRGRGRBBBGRGBGGRGBBBBGRRRBBGGRBRBBRBBGRBGBBGGGRRBBBRGRBRBRGGBGRBRGBRBGRGGRRGRRGGRBGBGBGRGBBBGBRRRBBRBRBBBBRBGGRRRGRRBBRGGGGGGBBRBGGRBRGBGBBRGRBGRGRRRGRGRGGGRBGBRRGBGGGGRGRRBRRGBBGGRBRGRRBRRRGRRGBRBRRBRGRBBBGRRRBGGRBGBBBBBRBRRGBRGRRBBRGRRRGBBGGGGBGBBRBBBGBRGGRRGBRRGGGGGGBBBRBGGBRRRGGBBRBRRRRBRRRGRGBBBBRBBGRGGGBRRBBRRRGRRGRGGRGRRGGGRRGRRRGRGRBGGGBRBRGBGGBGRGGRGGGRGRRBRRBRRBGRRRBBRBBRRGRRGRRGBGGRGBBBGBRB

[出力例]
2

[入力例]

RGBGGBGBR

[出力例]

※AtCoderのテストケースより

[入力例]

RGBRGB

[出力例]

※AtCoderのテストケースより

[入力例]

BBBBRGGRRBRBBGGGBGGGRBRBRBGBGR

[出力例]

[入力例]

100

GBRRRGGRRGGBGRGGBRRGBRRBGBBGBGBGGRGBBRBBGBGGGRGGRBBRBBRGGRGRGBRRRGRRRBRRGGGRRRBGGGBRBGBBBBBRGGRBBRRB

[出力例]

[入力例]

500

GBGBGGRBRGGGGBGGRGBBRGGBGGBGGGGGGGBBGBGGRBGRBRGGRGBBRBRRGRBBBGGGBRGRBRRRRBGBRBBRRBRBBBRGBBGRBGRRRRGRGRBBBGRGBGGRGBBBBGRRRBBGGRBRBBRBBGRBGBBGGGRRBBBRGRBRBRGGBGRBRGBRBGRGGRRGRRGGRBGBGBGRGBBBGBRRRBBRBRBBBBRBGGRRRGRRBBRGGGGGGBBRBGGRBRGBGBBRGRBGRGRRRGRGRGGGRBGBRRGBGGGGRGRRBRRGBBGGRBRGRRBRRRGRRGBRBRRBRGRBBBGRRRBGGRBGBBBBBRBRRGBRGRRBBRGRRRGBBGGGGBGBBRBBBGBRGGRRGBRRGGGGGGBBBRBGGBRRRGGBBRBRRRRBRRRGRGBBBBRBBGRGGGBRRBBRRRGRRGRGGRGRRGGGRRGRRRGRGRBGGGBRBRGBGGBGRGGRGGGRGRRBRRBRRBGRRRBBRBBRRGRRGRRGBGGRGBBBGBRB

[出力例]

■参照サイト
AtCoder Regular Contest 014

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

■感想.
1. 問題A は、与えられた数字の偶奇で, 分岐する方針で, AC版となった.
2. 問題Bは, 実装に, やや苦戦したものの, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 出力.
    printf("%s\n", (N & 1) ? "Red" : "Blue");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 出力.

printf("%s\n", (N & 1) ? "Red" : "Blue");

return 0;

}

[入力例]
4

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

[入力例]
9

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

[入力例]
13

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

[入力例]

[出力例]

Blue

※AtCoderのテストケースより

[入力例]

[出力例]

Red

※AtCoderのテストケースより

[入力例]

[出力例]

Red

※AtCoderのテストケースより

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

#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;
    scanf("%d", &N);
    
    // 2. しりとりを行う.
    map<string, int> m;
    int index = -1;
    string bef = "#";
    rep(i, N){
        // 今回分保存.
        char c[33];
        scanf("%s", c);
        string cur(c);
        
        // 前回以前に, すでに出現しているか確認.
        if(m.count(cur)){
            index = i + 1;
            break;
        }else{
            m[cur]++;
        }
        
        // 前回の単語の末尾と, 今回の単語の先頭を比較.
        if(bef != "#" && bef.back() != cur.front()){
            index = i + 1;
            break;
        }
        
        // 前回分保存.
        bef = cur;
    }
    
    // 3. 勝敗判定.
    string ans = "DRAW";
    if(index > 0) ans = (index & 1) ? "LOSE" : "WIN";
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

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

scanf("%d", &N);

// 2. しりとりを行う.

map<string, int> m;

int index = -1;

string bef = "#";

rep(i, N){

// 今回分保存.

char c[33];

scanf("%s", c);

string cur(c);

// 前回以前に, すでに出現しているか確認.

if(m.count(cur)){

index = i + 1;

break;

}else{

m[cur]++;

}

// 前回の単語の末尾と, 今回の単語の先頭を比較.

if(bef != "#" && bef.back() != cur.front()){

index = i + 1;

break;

}

// 前回分保存.

bef = cur;

}

// 3. 勝敗判定.

string ans = "DRAW";

if(index > 0) ans = (index & 1) ? "LOSE" : "WIN";

// 4. 出力.

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

return 0;

}

[入力例]
4
ab
ba
ab
cb

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

[入力例]
3
atcoder
redcoder
recorder

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

[入力例]
5
test
tree
examination
pass
stack

[出力例]
WIN

[入力例]
5
sine
logarithm
cosine
hyperbolic
cotangent

[出力例]
WIN

[入力例]
28
stack
kind
direction
negative
edge
efficient
third
dynamic
cosine
end
decode
extra
algebra
algorithm
map
pop
programming
graph
hash
head
deque
enqueue
euler
route
erase
equation
not
tuple

[出力例]
DRAW

[入力例]

[出力例]

LOSE

※AtCoderのテストケースより

[入力例]

atcoder

redcoder

recorder

[出力例]

DRAW

※AtCoderのテストケースより

[入力例]

test

tree

examination

pass

stack

[出力例]

WIN

[入力例]

sine

logarithm

cosine

hyperbolic

cotangent

[出力例]

WIN

[入力例]

stack

kind

direction

negative

edge

efficient

third

dynamic

cosine

end

decode

extra

algebra

algorithm

map

pop

programming

graph

hash

head

deque

enqueue

euler

route

erase

equation

not

tuple

[出力例]

DRAW

■参照サイト
AtCoder Regular Contest 014

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 013 の問題A (A – 梱包できるかな？) ～問題B (B – 引越しできるかな？) を解いてみた.

■感想.
1. 問題A は、6通りのパターンを見る方針で, AC版となった.
2. 問題Bは, 縦, 横, 高さを入れ替えて, 小さい方から並び替えた後に, 縦, 横, 高さのそれぞれの最大値から, 計算できることに気付いたので, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int N, M, L, P, Q, R;
    scanf("%d %d %d %d %d %d", &N, &M, &L, &P, &Q, &R);
    
    // 2. ダンボールに詰め込むことができる荷物の数の最大値は？
    //                 (縦) (横) (高)
    // 段ボール          N    M    L
    // 荷物(パターン1)   P    Q    R
    // 荷物(パターン2)   P    R    Q
    // 荷物(パターン3)   Q    P    R
    // 荷物(パターン4)   Q    R    P
    // 荷物(パターン5)   R    P    Q
    // 荷物(パターン6)   R    Q    P
    int ans = 0;
    ans = max(ans, (N / P) * (M / Q) * (L / R));
    ans = max(ans, (N / P) * (M / R) * (L / Q));
    ans = max(ans, (N / Q) * (M / P) * (L / R));
    ans = max(ans, (N / Q) * (M / R) * (L / P));
    ans = max(ans, (N / R) * (M / P) * (L / Q));
    ans = max(ans, (N / R) * (M / Q) * (L / P));
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, M, L, P, Q, R;

scanf("%d %d %d %d %d %d", &N, &M, &L, &P, &Q, &R);

// 2. ダンボールに詰め込むことができる荷物の数の最大値は？

// (縦) (横) (高)

// 段ボール N M L

// 荷物(パターン1) P Q R

// 荷物(パターン2) P R Q

// 荷物(パターン3) Q P R

// 荷物(パターン4) Q R P

// 荷物(パターン5) R P Q

// 荷物(パターン6) R Q P

int ans = 0;

ans = max(ans, (N / P) * (M / Q) * (L / R));

ans = max(ans, (N / P) * (M / R) * (L / Q));

ans = max(ans, (N / Q) * (M / P) * (L / R));

ans = max(ans, (N / Q) * (M / R) * (L / P));

ans = max(ans, (N / R) * (M / P) * (L / Q));

ans = max(ans, (N / R) * (M / Q) * (L / P));

// 3. 出力.

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

return 0;

}

[入力例]
10 10 10
1 1 1

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

[入力例]
10 3 1
2 1 1

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

[入力例]
5 10 3
2 5 3

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

[入力例]
8 8 8
1 1 9

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

[入力例]
100 97 89
2 3 5

[出力例]
28160

[入力例]
314 159 265
3 5 9

[出力例]
95506

[入力例]

10 10 10

1 1 1

[出力例]

1000

※AtCoderのテストケースより

[入力例]

10 3 1

2 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

5 10 3

2 5 3

[出力例]

※AtCoderのテストケースより

[入力例]

8 8 8

1 1 9

[出力例]

※AtCoderのテストケースより

[入力例]

100 97 89

2 3 5

[出力例]

28160

[入力例]

314 159 265

3 5 9

[出力例]

95506

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

#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 C, b[3], v[3];
    scanf("%d", &C);
    memset(v, 0, sizeof(v));
    rep(i, C){
        rep(j, 3) scanf("%d", &b[j]);
        sort(b, b + 3);
        rep(j, 3) v[j] = max(v[j], b[j]);
    }
    
    // 2. 出力.
    printf("%d\n", v[0] * v[1] * v[2]);
    return 0;
    
}

#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 C, b[3], v[3];

scanf("%d", &C);

memset(v, 0, sizeof(v));

rep(i, C){

rep(j, 3) scanf("%d", &b[j]);

sort(b, b + 3);

rep(j, 3) v[j] = max(v[j], b[j]);

}

// 2. 出力.

printf("%d\n", v[0] * v[1] * v[2]);

return 0;

}

[入力例]
2
10 20 30
20 20 20

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

[入力例]
3
10 20 30
20 20 20
30 20 10

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

[入力例]
4
10 20 30
20 20 20
30 20 10
10 40 10

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

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

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

[入力例]
100
57 31 72
58 70 68
62 33 39
57 7 26
56 55 47
58 13 48
47 40 27
29 32 12
25 45 18
37 21 17
40 38 25
43 27 67
59 48 78
9 30 4
54 30 77
24 38 48
1 33 16
52 63 32
32 51 77
44 49 22
74 3 7
49 44 23
22 20 27
39 80 26
40 45 65
45 68 22
62 14 46
51 49 41
55 25 13
77 53 50
12 34 50
6 64 63
6 68 47
4 19 66
25 68 29
3 28 71
30 23 70
7 59 31
8 53 54
58 29 8
41 52 3
76 69 20
45 69 67
71 62 59
63 26 22
3 19 29
6 13 74
77 24 36
79 56 47
67 9 17
55 23 14
15 46 31
20 12 49
77 4 21
60 22 63
31 37 77
71 59 16
33 50 64
19 10 34
73 4 1
35 42 33
38 67 17
32 27 12
7 3 30
64 28 10
75 73 62
8 66 39
75 47 53
70 74 31
14 18 1
12 9 57
68 59 8
39 50 17
63 56 60
56 20 55
76 63 39
69 77 52
23 1 15
21 48 17
47 1 68
4 79 31
52 7 51
55 72 58
3 23 80
20 11 4
10 71 12
18 11 31
72 63 26
31 51 15
68 55 16
43 20 4
74 59 20
50 17 22
22 52 18
19 75 77
30 16 67
30 72 71
49 7 11
52 15 56
41 66 41

[出力例]
372000

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

[入力例]

10 20 30

20 20 20

[出力例]

12000

※AtCoderのテストケースより

[入力例]

10 20 30

20 20 20

30 20 10

[出力例]

12000

※AtCoderのテストケースより

[入力例]

10 20 30

20 20 20

30 20 10

10 40 10

[出力例]

16000

※AtCoderのテストケースより

[入力例]

10 10 10

11 1 1

[出力例]

1100

※AtCoderのテストケースより

[入力例]

100

57 31 72

58 70 68

62 33 39

57 7 26

56 55 47

58 13 48

47 40 27

29 32 12

25 45 18

37 21 17

40 38 25

43 27 67

59 48 78

9 30 4

54 30 77

24 38 48

1 33 16

52 63 32

32 51 77

44 49 22

74 3 7

49 44 23

22 20 27

39 80 26

40 45 65

45 68 22

62 14 46

51 49 41

55 25 13

77 53 50

12 34 50

6 64 63

6 68 47

4 19 66

25 68 29

3 28 71

30 23 70

7 59 31

8 53 54

58 29 8

41 52 3

76 69 20

45 69 67

71 62 59

63 26 22

3 19 29

6 13 74

77 24 36

79 56 47

67 9 17

55 23 14

15 46 31

20 12 49

77 4 21

60 22 63

31 37 77

71 59 16

33 50 64

19 10 34

73 4 1

35 42 33

38 67 17

32 27 12

7 3 30

64 28 10

75 73 62

8 66 39

75 47 53

70 74 31

14 18 1

12 9 57

68 59 8

39 50 17

63 56 60

56 20 55

76 63 39

69 77 52

23 1 15

21 48 17

47 1 68

4 79 31

52 7 51

55 72 58

3 23 80

20 11 4

10 71 12

18 11 31

72 63 26

31 51 15

68 55 16

43 20 4

74 59 20

50 17 22

22 52 18

19 75 77

30 16 67

30 72 71

49 7 11

52 15 56

41 66 41

[出力例]

372000

■参照サイト
AtCoder Regular Contest 013

2020年4月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題C (C – Back and Forth) を解いてみた.

■感想.
1. 個人的には, 非常に面白い問題と感じた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 051 解説をご覧下さい.

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

#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 sx, sy, tx, ty;
    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
    
    // 2. イルカの最短経路を一つ求める.
    // 2-1. 右方向: (tx - sx)回
    string ans = "";
    rep(i, tx - sx) ans.pb('R');
    
    // 2-2. 上方向: (ty - sy)回
    rep(i, ty - sy) ans.pb('U');
    
    // 2-3. 左方向: (tx - sx)回
    rep(i, tx - sx) ans.pb('L');
    
    // 2-4. 下方向: (ty - sy)回
    rep(i, ty - sy) ans.pb('D');
    
    // 2-5. 下方向: 1回
    ans.pb('D');
    
    // 2-6. 右方向: (tx - sx + 1)回
    rep(i, tx - sx + 1) ans.pb('R');
    
    // 2-7. 上方向: (ty - sy + 1)回
    rep(i, ty - sy + 1) ans.pb('U');
    
    // 2-8. 左方向: 1回
    ans.pb('L');
    
    // 2-8. 上方向: 1回
    ans.pb('U');
    
    // 2-9. 左方向: (tx - sx + 1)回
    rep(i, tx - sx + 1) ans.pb('L');
    
    // 2-10.下方向: (ty - sy + 1)回
    rep(i, ty - sy + 1) ans.pb('D');
    
    // 2-11.右方向: 1回
    ans.pb('R');
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

#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 sx, sy, tx, ty;

scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

// 2. イルカの最短経路を一つ求める.

// 2-1. 右方向: (tx - sx)回

string ans = "";

rep(i, tx - sx) ans.pb('R');

// 2-2. 上方向: (ty - sy)回

rep(i, ty - sy) ans.pb('U');

// 2-3. 左方向: (tx - sx)回

rep(i, tx - sx) ans.pb('L');

// 2-4. 下方向: (ty - sy)回

rep(i, ty - sy) ans.pb('D');

// 2-5. 下方向: 1回

ans.pb('D');

// 2-6. 右方向: (tx - sx + 1)回

rep(i, tx - sx + 1) ans.pb('R');

// 2-7. 上方向: (ty - sy + 1)回

rep(i, ty - sy + 1) ans.pb('U');

// 2-8. 左方向: 1回

ans.pb('L');

// 2-8. 上方向: 1回

ans.pb('U');

// 2-9. 左方向: (tx - sx + 1)回

rep(i, tx - sx + 1) ans.pb('L');

// 2-10.下方向: (ty - sy + 1)回

rep(i, ty - sy + 1) ans.pb('D');

// 2-11.右方向: 1回

ans.pb('R');

// 3. 出力.

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

return 0;

}

[入力例]
0 0 1 2

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

※上記のプログラムだと以下のように出力される.
RUULDDDRRUUULULLDDDR

[入力例]
-2 -2 1 1

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

※上記のプログラムだと以下のように出力される.
RRRUUULLLDDDDRRRRUUUULULLLLDDDDR

[入力例]
0 0 1 1

[出力例]
RULDDRRUULULLDDR

[入力例]
11 19 31 47

[出力例]
RRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]
3 14 15 92

[出力例]
RRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]

0 0 1 2

[出力例]

UURDDLLUUURRDRDDDLLU

※AtCoderテストケースより

※上記のプログラムだと以下のように出力される.

RUULDDDRRUUULULLDDDR

[入力例]

-2 -2 1 1

[出力例]

UURRURRDDDLLDLLULUUURRURRDDDLLDL

※AtCoderテストケースより

※上記のプログラムだと以下のように出力される.

RRRUUULLLDDDDRRRRUUUULULLLLDDDDR

[入力例]

0 0 1 1

[出力例]

RULDDRRUULULLDDR

[入力例]

11 19 31 47

[出力例]

RRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]

3 14 15 92

[出力例]

RRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

■参照サイト
AtCoder Beginner Contest 051

2020年4月23日

C++ の動作確認をしてみた（２０３）

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題A (A – くつがくっつく) ～問題B (B – 赤と黒の木) を解いてみた.

■感想.
1. 問題Bは, もっとも長く連続する 0 もしくは 1 のパターンに対して, 計算で求まることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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 l[111], r[111]; // 左足, 右足の靴のサイズ.

int main(){
    
    // 1. 入力情報.
    int L, R, x;
    scanf("%d %d", &L, &R);
    rep(i, L){
        scanf("%d", &x);
        l[x]++;
    }
    rep(i, R){
        scanf("%d", &x);
        r[x]++;
    }
    
    // 2. 作成可能な靴のペア数の最大値を集計.
    int ans = 0;
    rep(i, 111) ans += min(l[i], r[i]);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 l[111], r[111]; // 左足, 右足の靴のサイズ.

int main(){

// 1. 入力情報.

int L, R, x;

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

rep(i, L){

scanf("%d", &x);

l[x]++;

}

rep(i, R){

scanf("%d", &x);

r[x]++;

}

// 2. 作成可能な靴のペア数の最大値を集計.

int ans = 0;

rep(i, 111) ans += min(l[i], r[i]);

// 3. 出力.

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

return 0;

}

[入力例]
3 3
20 21 22
30 22 15

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

[入力例]
3 4
10 11 10
12 10 11 25

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

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

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

[入力例]
5 5
10 11 12 13 14
30 31 32 33 34

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

[入力例]
45 75
33 22 12 34 13 36 36 18 14 10 17 10 38 13 27 21 14 11 18 29 31 28 30 33 19 29 12 24 35 17 37 30 29 31 17 27 29 10 26 11 37 36 19 18 36
14 25 18 33 31 28 13 31 25 35 30 37 18 10 22 12 37 36 35 27 21 15 17 35 35 20 18 37 37 27 15 21 33 31 35 18 23 36 38 36 25 19 19 19 14 30 27 11 28 11 32 22 10 12 14 19 17 36 10 12 11 14 36 35 12 36 14 37 38 35 31 14 12 23 12

[出力例]
36

[入力例]

3 3

20 21 22

30 22 15

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

10 11 10

12 10 11 25

[出力例]

※AtCoderのテストケースより

[入力例]

5 5

10 10 10 10 10

[出力例]

※AtCoderのテストケースより

[入力例]

5 5

10 11 12 13 14

30 31 32 33 34

[出力例]

※AtCoderのテストケースより

[入力例]

45 75

33 22 12 34 13 36 36 18 14 10 17 10 38 13 27 21 14 11 18 29 31 28 30 33 19 29 12 24 35 17 37 30 29 31 17 27 29 10 26 11 37 36 19 18 36

14 25 18 33 31 28 13 31 25 35 30 37 18 10 22 12 37 36 35 27 21 15 17 35 35 20 18 37 37 27 15 21 33 31 35 18 23 36 38 36 25 19 19 19 14 30 27 11 28 11 32 22 10 12 14 19 17 36 10 12 11 14 36 35 12 36 14 37 38 35 31 14 12 23 12

[出力例]

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

#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 a first
#define b second
int br[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &br[i]);
    
    // 2. 0, 1 の 切り替わり箇所は？
    int cur = -1, bef = br[0], s = -1;
    repx(i, 1, N){
        // 今回分更新.
        cur = br[i];
        
        // 前回と異なる場合は, 出現位置を保存して終了.
        if(bef != cur){
            s = i;
            break;
        }
        
        // 前回分更新.
        bef = cur;
    }
    
    // 3. 全部同じ色の場合は, -1 を 出力.
    if(s == -1){
        puts("-1");
        return 0;
    }
    
    // 4. 0 ～ (s - 1)番目 までを, br の 後ろにくっつける.
    // ex.
    // 110111 -> 11011111
    rep(i, s) br[i + N] = br[i];
    
    // 5. 0, 1 の 連続する長さを測定.
    map<int, int> mb, mr;
    bef = br[s];
    int c = 0, maxC = 0;
    repx(i, s, N + s){
        // 今回分更新.
        cur = br[i];
        // 前回と同じ場合は, カウンターを増やす.
        if(bef == cur){
            c++;
        }else{
            // 黒色.
            if(bef == 0) mb[c]++;
            // 赤色.
            if(bef == 1) mr[c]++;
            // 最大値更新.
            maxC = max(maxC, c);
            // カウンターを初期化.
            c = 1;
        }
        // 前回分更新.
        bef = cur;
    }
    // 黒色.
    if(bef == 0) mb[c]++;
    // 赤色.
    if(bef == 1) mr[c]++;
    // 最大値更新.
    maxC = max(maxC, c);
    // puts("--- black ---");
    // for(auto i = mb.begin(); i != mb.end(); ++i) printf("key=%d value=%d\n", i->a, i->b);
    // puts("--- red ---");
    // for(auto i = mr.begin(); i != mr.end(); ++i) printf("key=%d value=%d\n", i->a, i->b);
    
    // 6. すべての木の色が変わらなくなる日が何日目か？
    int ans = (maxC + 1) / 2;
    
    // 7. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

#define b second

int br[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 0, 1 の切り替わり箇所は？

int cur = -1, bef = br[0], s = -1;

repx(i, 1, N){

// 今回分更新.

cur = br[i];

// 前回と異なる場合は, 出現位置を保存して終了.

if(bef != cur){

s = i;

break;

}

// 前回分更新.

bef = cur;

}

// 3. 全部同じ色の場合は, -1 を出力.

if(s == -1){

puts("-1");

return 0;

}

// 4. 0 ～ (s - 1)番目までを, br の後ろにくっつける.

// ex.

// 110111 -> 11011111

rep(i, s) br[i + N] = br[i];

// 5. 0, 1 の連続する長さを測定.

map<int, int> mb, mr;

bef = br[s];

int c = 0, maxC = 0;

repx(i, s, N + s){

// 今回分更新.

cur = br[i];

// 前回と同じ場合は, カウンターを増やす.

if(bef == cur){

c++;

}else{

// 黒色.

if(bef == 0) mb[c]++;

// 赤色.

if(bef == 1) mr[c]++;

// 最大値更新.

maxC = max(maxC, c);

// カウンターを初期化.

c = 1;

}

// 前回分更新.

bef = cur;

}

// 黒色.

if(bef == 0) mb[c]++;

// 赤色.

if(bef == 1) mr[c]++;

// 最大値更新.

maxC = max(maxC, c);

// puts("--- black ---");

// for(auto i = mb.begin(); i != mb.end(); ++i) printf("key=%d value=%d\n", i->a, i->b);

// puts("--- red ---");

// for(auto i = mr.begin(); i != mr.end(); ++i) printf("key=%d value=%d\n", i->a, i->b);

// 6. すべての木の色が変わらなくなる日が何日目か？

int ans = (maxC + 1) / 2;

// 7. 出力.

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

return 0;

}

[入力例]
5
0
1
1
1
0

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

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

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

[入力例]
3
1
1
1

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

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

[出力例]
5

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

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

-1

※AtCoderのテストケースより

[入力例]

100

[出力例]

■参照サイト
AtCoder Regular Contest 024

2020年4月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 163 の問題E (E – Active Infants) を解いてみた.

■感想.
1. 方針が全く見えなかった(※priority_queueを使う方針では, 駄目だった)ので, 解説を見てから, 実装して, AC版となった.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 163 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc163/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
LL dp[2020][2020];
vector<P> v; // joy, index.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        v.pb({a, i + 1});
    }
    
    // 2. sort.
    sort(all(v), greater<P>());
    
    // 3. 解説通り.
    // (x + y)人 を 昇順にチェックしていくとのこと.
    repx(xy, 1, N + 1){
        // A[i] * (i - p[i]) を 選択: x人
        // A[i] * (p[i] - i) を 選択: y人
        rep(x, xy + 1){
            // 3-1. x人, y人 を 設定.
            int y = xy - x;
            LL hx = 0, hy = 0;
            
            // 3-2. (x - 1)人 と y人 から (x + y)人 になる場合.
            if(x > 0) hx = dp[x - 1][y] + v[xy - 1].a * (LL)(v[xy - 1].b - x);
            
            // 3-3. x人 と (y - 1)人 から (x + y)人 になる場合.
            if(y > 0) hy = dp[x][y - 1] + v[xy - 1].a * (LL)(N + 1 - y - v[xy - 1].b);
            
            // 3-4. dp更新.
            dp[x][y] = max(hx, hy);
        }
    }
    
    // 4. 最大値.
    LL ans = 0;
    rep(i, N + 1) ans = max(ans, dp[i][N - i]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

LL dp[2020][2020];

vector<P> v; // joy, index.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

LL a;

scanf("%lld", &a);

v.pb({a, i + 1});

}

// 2. sort.

sort(all(v), greater<P>());

// 3. 解説通り.

// (x + y)人を昇順にチェックしていくとのこと.

repx(xy, 1, N + 1){

// A[i] * (i - p[i]) を選択: x人

// A[i] * (p[i] - i) を選択: y人

rep(x, xy + 1){

// 3-1. x人, y人を設定.

int y = xy - x;

LL hx = 0, hy = 0;

// 3-2. (x - 1)人と y人から (x + y)人になる場合.

if(x > 0) hx = dp[x - 1][y] + v[xy - 1].a * (LL)(v[xy - 1].b - x);

// 3-3. x人と (y - 1)人から (x + y)人になる場合.

if(y > 0) hy = dp[x][y - 1] + v[xy - 1].a * (LL)(N + 1 - y - v[xy - 1].b);

// 3-4. dp更新.

dp[x][y] = max(hx, hy);

}

// 4. 最大値.

LL ans = 0;

rep(i, N + 1) ans = max(ans, dp[i][N - i]);

// 5. 出力.

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

return 0;

}

[入力例]
4
1 3 4 2

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

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

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

[入力例]
6
8 6 9 1 2 1

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

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

[出力例]
36116215

[入力例]
100
62348265 95118635 88054189 121268617 106864743 43443412 39089716 90005653 90407480 61727531 10640257 77739370 34308834 41637572 26904411 115837893 76505695 72814009 54022243 47711319 61268030 81181912 68700366 51202991 58630161 39475078 65163030 36017359 68297710 24484888 80071596 20937946 108066614 119344302 74603735 84460903 62061764 5510962 69425324 112771391 119382808 58473923 24060311 46840374 67943003 16480754 93527856 113070388 29569607 40157553 71094181 88543249 59269990 35626451 98694582 38008567 120847955 120411925 121330414 64063181 122991777 32151428 85712702 21751581 31449111 94566545 54499823 68414787 54995847 98738012 77292808 42234394 38135507 69679926 21624428 41860842 21819789 63474564 81735114 110205665 83768177 21756959 1582887 14429454 117149701 80571598 87476072 83505763 112108880 89461233 80063731 76208411 34661572 87190410 39834167 24542553 63945913 71905551 46749037 78809363

[出力例]
374598037940

[入力例]
500
415740821 221850321 41384601 922455619 733988292 10737122 910402593 307466244 744732428 676153329 726496724 324458831 970969966 416407799 583701681 770688808 96899422 964051260 591579151 373255767 932902324 406763003 480043799 471759715 860368894 154854101 291388993 385686584 71324017 69963893 957610363 611713330 291608589 775913934 462565042 145998157 611652762 448539078 762566168 73073636 991501640 257947005 593042486 29618614 77777672 959256024 314773796 630574591 959748996 482888957 788543663 356305640 484108406 263833633 992135754 709563527 274270660 253334073 741376525 164316465 460345409 189434727 871334757 395487842 516502296 533411025 854863158 240098682 947186795 949657526 561904748 608447749 213599658 484030161 386616406 588322273 938333769 951577977 259013040 376472673 77100454 613545045 706541617 605221486 91738873 796660365 881000645 454934725 3781977 511400378 529590051 142020774 780025282 155253712 148092830 853026140 307797097 504713952 323607903 887588976 39535556 771636311 124842284 267528984 879690220 442469323 819298694 196528588 784263881 732671334 399158020 930618068 717205326 108858692 890495554 57655898 470923246 467089973 784879927 816020297 145868362 259749495 533581067 30178956 174799899 576494830 203015853 197017329 613951517 759062291 938895552 401790875 243623371 252867092 118576699 838157568 176932195 480747739 429560255 889153631 761873611 258101971 54983086 623911621 634804533 685642486 754295610 109076553 311418860 344583006 635818079 774357468 91627532 184161489 722900742 743701625 872251338 335280940 897245765 797057216 47032590 836102050 814290555 955450036 908783654 481413968 35594032 651647466 602463602 1483924 554751391 573164310 412941957 991689630 347258135 188392871 626473360 249639482 255155258 27982014 605892203 136179085 517158296 246666573 304210124 806548146 821321826 189019185 602419091 102154730 882383285 733314244 350502525 699353815 657528516 456821438 397620410 102518484 230733386 872764142 134876380 397223490 585829826 729525467 398379349 224372383 257805001 235439937 649151352 125213301 294059302 991320778 99452893 991043349 496064341 401694975 466840048 72669307 954429429 529234342 605148165 118923434 416951209 53775332 158933204 754847171 435600614 63425711 766511783 804649992 689617506 852110064 381314214 691159579 481575026 44298821 874885138 840392862 876798386 836652200 908125443 747221316 896232059 254419136 852980046 382936378 924758300 2317320 82152492 92506390 301097174 837485564 753053927 668126566 687927306 80374655 318228911 926290907 179606807 894725341 574389347 80556524 733598359 775678478 498185043 571636142 621090739 632952737 473659336 547742269 336022000 942710571 859488373 666971270 351520919 222575238 991967494 951779918 904250162 305530293 320898233 312913409 218061846 737017877 227477347 720927596 344101378 532738853 411906764 533454717 425269617 393914681 848112060 489871374 861782610 964184599 201435582 841574587 279337685 396594122 199918093 283979878 928582142 780992132 751487978 455800238 662061870 233254972 565494260 30746813 537423635 725312594 22550639 41457734 519441630 789710141 473423252 52308852 584690557 327121247 535004743 4521896 862343475 687258737 381865349 285728806 216216180 528530882 511656249 32187951 480925897 813995229 970461797 487166876 110231122 359272428 693667848 431823688 988925953 344916935 31548136 888055127 378262109 506990101 403876056 110211587 123241593 287332152 405398141 932416088 2831084 679307570 494279793 601519508 985045492 850057592 164121859 771348766 221122514 221252440 89487737 872701416 38962747 682837375 700224277 565816651 350343660 668562332 51169872 557317108 787788957 855058406 68662346 962946226 401223596 387749420 593318697 703905727 386756033 169222307 494062948 6739882 533350369 821311769 227242678 828832150 843957695 826520930 765482387 619940308 794607917 429420661 135527293 489713085 387670092 498313800 447435567 991809892 560793490 682223712 599172061 212701192 835266036 951933349 612423230 178796464 105178524 216096737 896620293 234909684 588148930 505449834 622924093 34638859 805835550 561111579 891210362 887814214 473370936 867883624 186853678 526536583 154315691 141303237 108819632 614958922 286222095 275940649 708541641 812666215 20964433 940468616 439494728 856710354 667166833 712334578 602273817 262726780 819893357 24282481 681042753 795416296 235732460 597730460 503597086 591043811 796248177 525726279 138283859 170920872 679191898 151147957 37912717 544745211 211759678 872377798 945710921 535663942 805023755 497241687 170000344 779215798 941409425 255415772 8056573 559707960 271360756 723121594 190493492 366979382 421868113 547589193 922098969 754538608 799396239 442087028 984944550 167507030 520931853 141871083 4647323 864879888 116344376 558790763 423779029 823477547 652618924 109363757 533945834 839428202 811261480 636652354 132852593 999823304 145009894 74501249 821760045 195288852 940570539 858110272

[出力例]
73710316323217

[入力例]

1 3 4 2

[出力例]

※AtCoderテストケースより

[入力例]

5 5 6 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

8 6 9 1 2 1

[出力例]

※AtCoderテストケースより

[入力例]

1000

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

[出力例]

36116215

[入力例]

100

62348265 95118635 88054189 121268617 106864743 43443412 39089716 90005653 90407480 61727531 10640257 77739370 34308834 41637572 26904411 115837893 76505695 72814009 54022243 47711319 61268030 81181912 68700366 51202991 58630161 39475078 65163030 36017359 68297710 24484888 80071596 20937946 108066614 119344302 74603735 84460903 62061764 5510962 69425324 112771391 119382808 58473923 24060311 46840374 67943003 16480754 93527856 113070388 29569607 40157553 71094181 88543249 59269990 35626451 98694582 38008567 120847955 120411925 121330414 64063181 122991777 32151428 85712702 21751581 31449111 94566545 54499823 68414787 54995847 98738012 77292808 42234394 38135507 69679926 21624428 41860842 21819789 63474564 81735114 110205665 83768177 21756959 1582887 14429454 117149701 80571598 87476072 83505763 112108880 89461233 80063731 76208411 34661572 87190410 39834167 24542553 63945913 71905551 46749037 78809363

[出力例]

374598037940

[入力例]

500

415740821 221850321 41384601 922455619 733988292 10737122 910402593 307466244 744732428 676153329 726496724 324458831 970969966 416407799 583701681 770688808 96899422 964051260 591579151 373255767 932902324 406763003 480043799 471759715 860368894 154854101 291388993 385686584 71324017 69963893 957610363 611713330 291608589 775913934 462565042 145998157 611652762 448539078 762566168 73073636 991501640 257947005 593042486 29618614 77777672 959256024 314773796 630574591 959748996 482888957 788543663 356305640 484108406 263833633 992135754 709563527 274270660 253334073 741376525 164316465 460345409 189434727 871334757 395487842 516502296 533411025 854863158 240098682 947186795 949657526 561904748 608447749 213599658 484030161 386616406 588322273 938333769 951577977 259013040 376472673 77100454 613545045 706541617 605221486 91738873 796660365 881000645 454934725 3781977 511400378 529590051 142020774 780025282 155253712 148092830 853026140 307797097 504713952 323607903 887588976 39535556 771636311 124842284 267528984 879690220 442469323 819298694 196528588 784263881 732671334 399158020 930618068 717205326 108858692 890495554 57655898 470923246 467089973 784879927 816020297 145868362 259749495 533581067 30178956 174799899 576494830 203015853 197017329 613951517 759062291 938895552 401790875 243623371 252867092 118576699 838157568 176932195 480747739 429560255 889153631 761873611 258101971 54983086 623911621 634804533 685642486 754295610 109076553 311418860 344583006 635818079 774357468 91627532 184161489 722900742 743701625 872251338 335280940 897245765 797057216 47032590 836102050 814290555 955450036 908783654 481413968 35594032 651647466 602463602 1483924 554751391 573164310 412941957 991689630 347258135 188392871 626473360 249639482 255155258 27982014 605892203 136179085 517158296 246666573 304210124 806548146 821321826 189019185 602419091 102154730 882383285 733314244 350502525 699353815 657528516 456821438 397620410 102518484 230733386 872764142 134876380 397223490 585829826 729525467 398379349 224372383 257805001 235439937 649151352 125213301 294059302 991320778 99452893 991043349 496064341 401694975 466840048 72669307 954429429 529234342 605148165 118923434 416951209 53775332 158933204 754847171 435600614 63425711 766511783 804649992 689617506 852110064 381314214 691159579 481575026 44298821 874885138 840392862 876798386 836652200 908125443 747221316 896232059 254419136 852980046 382936378 924758300 2317320 82152492 92506390 301097174 837485564 753053927 668126566 687927306 80374655 318228911 926290907 179606807 894725341 574389347 80556524 733598359 775678478 498185043 571636142 621090739 632952737 473659336 547742269 336022000 942710571 859488373 666971270 351520919 222575238 991967494 951779918 904250162 305530293 320898233 312913409 218061846 737017877 227477347 720927596 344101378 532738853 411906764 533454717 425269617 393914681 848112060 489871374 861782610 964184599 201435582 841574587 279337685 396594122 199918093 283979878 928582142 780992132 751487978 455800238 662061870 233254972 565494260 30746813 537423635 725312594 22550639 41457734 519441630 789710141 473423252 52308852 584690557 327121247 535004743 4521896 862343475 687258737 381865349 285728806 216216180 528530882 511656249 32187951 480925897 813995229 970461797 487166876 110231122 359272428 693667848 431823688 988925953 344916935 31548136 888055127 378262109 506990101 403876056 110211587 123241593 287332152 405398141 932416088 2831084 679307570 494279793 601519508 985045492 850057592 164121859 771348766 221122514 221252440 89487737 872701416 38962747 682837375 700224277 565816651 350343660 668562332 51169872 557317108 787788957 855058406 68662346 962946226 401223596 387749420 593318697 703905727 386756033 169222307 494062948 6739882 533350369 821311769 227242678 828832150 843957695 826520930 765482387 619940308 794607917 429420661 135527293 489713085 387670092 498313800 447435567 991809892 560793490 682223712 599172061 212701192 835266036 951933349 612423230 178796464 105178524 216096737 896620293 234909684 588148930 505449834 622924093 34638859 805835550 561111579 891210362 887814214 473370936 867883624 186853678 526536583 154315691 141303237 108819632 614958922 286222095 275940649 708541641 812666215 20964433 940468616 439494728 856710354 667166833 712334578 602273817 262726780 819893357 24282481 681042753 795416296 235732460 597730460 503597086 591043811 796248177 525726279 138283859 170920872 679191898 151147957 37912717 544745211 211759678 872377798 945710921 535663942 805023755 497241687 170000344 779215798 941409425 255415772 8056573 559707960 271360756 723121594 190493492 366979382 421868113 547589193 922098969 754538608 799396239 442087028 984944550 167507030 520931853 141871083 4647323 864879888 116344376 558790763 423779029 823477547 652618924 109363757 533945834 839428202 811261480 636652354 132852593 999823304 145009894 74501249 821760045 195288852 940570539 858110272

[出力例]

73710316323217

■参照サイト
AtCoder Beginner Contest 163

C++の練習を兼ねて, AtCoder Regular Contest 026 の 問題A (A – ダイナミックなポーズ) ～ 問題B (B – 完全数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の 問題A (A – ゴールドラッシュ) ～ 問題B (B – チョコレート) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 164 の 問題D (D – Multiple of 2019) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 004 の 問題A (A – 2点間距離の最大値 ( The longest distance )) ～ 問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の 問題C (C – 魂の還る場所) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の 問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～ 問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 013 の 問題A (A – 梱包できるかな？) ～ 問題B (B – 引越しできるかな？) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 051 の 問題C (C – Back and Forth) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の 問題A (A – くつがくっつく) ～ 問題B (B – 赤と黒の木) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 163 の 問題E (E – Active Infants) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題A (A – ダイナミックなポーズ) ～問題B (B – 完全数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題A (A – ゴールドラッシュ) ～問題B (B – チョコレート) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 164 の問題D (D – Multiple of 2019) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 004 の問題A (A – 2点間距離の最大値 ( The longest distance )) ～問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題C (C – 魂の還る場所) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 013 の問題A (A – 梱包できるかな？) ～問題B (B – 引越しできるかな？) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題C (C – Back and Forth) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題A (A – くつがくっつく) ～問題B (B – 赤と黒の木) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 163 の問題E (E – Active Infants) を解いてみた.