7月, 2019 | 個人用メモ帳

2019年7月30日2019年7月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 007 の問題D (D – 禁止された数字) を解いてみた.

■感想.
1. 解答を見る前に, 正解に辿り着けたので, 時間はかかったものの, 及第点は取れたと思う.
2. 禁止された数字の個数を, 直接数えるのが大変そうだったので, 禁止されてない文字を数えてから, 逆算する方針で解いた.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL pow8[21];

// N以下に含まれる許容された数字の個数を数える.
// @param N: 正の整数.
// @param P: 計算済みの許容された数字の数.
// @return : 再帰計算を行う.
LL acceptable(string N, LL P){
    
    // 1. 文字列長が, 1桁 の 場合.
    int l = N.size();
    if(l == 1){
        if(N[0]  < '4') return P + (N[0] - '0');
        if(N[0]  < '9') return P + (N[0] - '1');
        if(N[0] == '9') return P + (N[0] - '2');
    
    }
    
    // 2. 最上位の桁を確認.
    // ex.
    // 123456
    // -> 100000 と 23456 に 分割.
    // -> 100000 は, (8種類の数字) の 5乗 × 1 とカウント.
    // ->  23456 は, 20000 と 3456 に 分割.
    // ->  20000 は, (8種類の数字) の 5乗 × 2 とカウント.
    // ->   3456 は, 3000 と 456 に 分割.
    // ->   以下繰り返し.
    char c = N[0];
    
    // 2-1. 最上位の桁が, '0' の 場合.
    if(c == '0') return acceptable(N.substr(1, l - 1), P);
    
    // 2-2. 最上位の桁が, '1' - '3' の 場合.
    LL cp = 0;
    if(c >= '1' && c <= '3') cp = pow8[l - 1] * (c - '0');
    
    // 2-3. 最上位の桁が, '4' の 場合.
    if(c == '4'){
        cp = pow8[l - 1] * (c - '0') - 1;
        return P + cp;
    }
    
    // 2-4. 最上位の桁が, '5' - '8' の 場合.
    if(c >= '5' && c <= '8') cp = pow8[l - 1] * (c - '1');
    
    // 2-5. 最上位の桁が, '9' の 場合.
    if(c == '9'){
        cp = pow8[l - 1] * (c - '1') - 1;
        return P + cp;
    }
    
    // 3. 再帰計算を行う.
    return acceptable(N.substr(1, l - 1), P + cp);
    
}

int main() {
    
    // 1. 入力情報取得.
    LL A, B;
    scanf("%llu %llu", &A, &B);
    
    // 2. 8 の べき乗 を 保存.
    pow8[0] = 1;
    for(int i = 1; i < 21; i++) pow8[i] = pow8[i - 1] * 8;
    
    // 3. N 以下 に 含まれる 禁止された数字 以外 の 数字 の 個数 を計算.
    LL a = acceptable(to_string(A - 1), 0);
    LL b = acceptable(to_string(B), 0);
    // printf("%llu %llu\n", a, b);
    
    // 4. 区間[A, B]内 の ('4', '9' を含む)禁止された数字 の 個数 を計算.
    LL ans = (B - (A - 1)) - (b - a);
    
    // 5. 出力.
    printf("%llu\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL pow8[21];

// N以下に含まれる許容された数字の個数を数える.

// @param N: 正の整数.

// @param P: 計算済みの許容された数字の数.

// @return : 再帰計算を行う.

LL acceptable(string N, LL P){

// 1. 文字列長が, 1桁の場合.

int l = N.size();

if(l == 1){

if(N[0] < '4') return P + (N[0] - '0');

if(N[0] < '9') return P + (N[0] - '1');

if(N[0] == '9') return P + (N[0] - '2');

}

// 2. 最上位の桁を確認.

// ex.

// 123456

// -> 100000 と 23456 に分割.

// -> 100000 は, (8種類の数字) の 5乗 × 1 とカウント.

// -> 23456 は, 20000 と 3456 に分割.

// -> 20000 は, (8種類の数字) の 5乗 × 2 とカウント.

// -> 3456 は, 3000 と 456 に分割.

// -> 以下繰り返し.

char c = N[0];

// 2-1. 最上位の桁が, '0' の場合.

if(c == '0') return acceptable(N.substr(1, l - 1), P);

// 2-2. 最上位の桁が, '1' - '3' の場合.

LL cp = 0;

if(c >= '1' && c <= '3') cp = pow8[l - 1] * (c - '0');

// 2-3. 最上位の桁が, '4' の場合.

if(c == '4'){

cp = pow8[l - 1] * (c - '0') - 1;

return P + cp;

}

// 2-4. 最上位の桁が, '5' - '8' の場合.

if(c >= '5' && c <= '8') cp = pow8[l - 1] * (c - '1');

// 2-5. 最上位の桁が, '9' の場合.

if(c == '9'){

cp = pow8[l - 1] * (c - '1') - 1;

return P + cp;

}

// 3. 再帰計算を行う.

return acceptable(N.substr(1, l - 1), P + cp);

}

int main() {

// 1. 入力情報取得.

LL A, B;

scanf("%llu %llu", &A, &B);

// 2. 8 のべき乗を保存.

pow8[0] = 1;

for(int i = 1; i < 21; i++) pow8[i] = pow8[i - 1] * 8;

// 3. N 以下に含まれる禁止された数字以外の数字の個数を計算.

LL a = acceptable(to_string(A - 1), 0);

LL b = acceptable(to_string(B), 0);

// printf("%llu %llu\n", a, b);

// 4. 区間[A, B]内の ('4', '9' を含む)禁止された数字の個数を計算.

LL ans = (B - (A - 1)) - (b - a);

// 5. 出力.

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

return 0;

}

[入力例]
1 9

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

[入力例]
40 49

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

[入力例]
1 1000

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

[入力例]
1 1000000000000000000

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

[入力例]
12345678987654321 1234567890987654321

[出力例]
1199086288328337409

[入力例]

1 9

[出力例]

※AtCoderテストケースより

[入力例]

40 49

[出力例]

※AtCoderテストケースより

[入力例]

1 1000

[出力例]

488

※AtCoderテストケースより

[入力例]

1 1000000000000000000

[出力例]

981985601490518016

※AtCoderテストケースより

[入力例]

12345678987654321 1234567890987654321

[出力例]

1199086288328337409

■参照サイト
AtCoder Beginner Contest 007

2019年7月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Worst Case) を解いてみた.

■感想.
1. 解答方針が見えなかったので, 解説を参照して確認した.
2. 復習出来てない問題が, まだまだ, たくさんあるので, 今後も, 少しずつ進めていきたいと思う.

本家のサイトARC094/ABC093解説をご覧下さい.

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

// 解き直し.
// ARC094/ABC093解説
// https://img.atcoder.jp/arc094/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {

    // 1. 入力情報取得.
    int Q;
    scanf("%d", &Q);
    
    // 2. 各クエリに解答.
    // 解説通り.
    for(int i = 0; i < Q; i++){
        LL a, b;
        scanf("%llu %llu", &a, &b);
        if(a > b) swap(a, b);
        
        // 2-1. A = B の 場合.
        if(a == b){
            printf("%llu\n", 2 * a - 2);
            continue;
        }
        
        // 2-2. A + 1 = B の 場合.
        if(a + 1 == b){
            printf("%llu\n", 2 * a - 2);
            continue;
        }
        
        // 2-3. 上記以外 の 場合.
        if(a != b && a + 1 != b){
            LL c = sqrt(a * b);
            if(c * c == a * b) c--;
            
            // C * (C + 1) >= A * B の 場合.
            if(c * (c + 1) >= a * b){
                printf("%llu\n", 2 * c - 2);
                continue;
            }
            
            // C * C < A * B の 場合.
            if(c * c < a * b){
                printf("%llu\n", 2 * c - 1);
                continue;
            }
        }
    }
    
    // 3. 後処理.
    return 0;

}

// 解き直し.

// ARC094/ABC093解説

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int Q;

scanf("%d", &Q);

// 2. 各クエリに解答.

// 解説通り.

for(int i = 0; i < Q; i++){

LL a, b;

scanf("%llu %llu", &a, &b);

if(a > b) swap(a, b);

// 2-1. A = B の場合.

if(a == b){

printf("%llu\n", 2 * a - 2);

continue;

}

// 2-2. A + 1 = B の場合.

if(a + 1 == b){

printf("%llu\n", 2 * a - 2);

continue;

}

// 2-3. 上記以外の場合.

if(a != b && a + 1 != b){

LL c = sqrt(a * b);

if(c * c == a * b) c--;

// C * (C + 1) >= A * B の場合.

if(c * (c + 1) >= a * b){

printf("%llu\n", 2 * c - 2);

continue;

}

// C * C < A * B の場合.

if(c * c < a * b){

printf("%llu\n", 2 * c - 1);

continue;

}

// 3. 後処理.

return 0;

}

[入力例]
8
1 4
10 5
3 3
4 11
8 9
22 40
8 36
314159265 358979323

[出力例]
1
12
4
11
14
57
31
671644785
※AtCoderテストケースより

[入力例]

1 4

10 5

3 3

4 11

8 9

22 40

8 36

314159265 358979323

[出力例]

671644785

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 093

2019年7月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Good Grid) を解いてみた.

■感想.
1. 解説を見る前に解けたので, 及第点は, 取れたように思う.
2. グリッドを, 対角線方向に眺めて, i + j = 0 ～ (2 × N – 2) の範囲で, 集計する方針で対応したが, 解説見たところ, もっと簡潔に解けることが示されていたので, 大変勉強になった.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
typedef pair<LL, int> pli;
LL d[33][33], c[555][555];
// i + j = k の 場合に, 色X から 色Y に 塗り替えた場合の違和感を保存.
// -> k と 色Y に塗り替えた場合の違和感 を 保存.
LL discomfort[1111][33];
// k を 3で割った余りが, 0, 1, 2 の パターン に 集約.
LL dp[3][33]; 

int main() {

    // 1. 入力情報取得.
    int N, C;
    scanf("%d %d", &N, &C);
    for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) scanf("%lld", &d[i][j]);
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) scanf("%lld", &c[i][j]);
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) c[i][j]--;
    
    // 2. 違和感を集計.
    // マス(i, j) (但し, i + j = k とする) を, 色y に塗り替えた場合の違和感を調査.
    for(int k = 0; k < N; k++){
        for(int i = 0; i <= k && i < N; i++){
            int j = k - i;
            for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y];
        }
    }
    for(int k = N; k < 2 * N - 1; k++){
        for(int i = k - (N - 1); i < N; i++){
            int j = k - i;
            for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y];
        }
    }
    // for(int k = 0; k < 2 * N - 1; k++){
    //     for(int y = 0; y < C; y++) printf("discomfort[%d][%d]=%lld ", k, y, discomfort[k][y]);
    //     printf("\n");
    // }
    
    // 3. 違和感の和を集計(k を 3 で割ったときの余りで分類).
    // 各 k ごとに, 色y に塗り替えた場合の違和感の最小値を選択.
    for(int k = 0; k < 2 * N - 1; k++){
        for(int y = 0; y <= 32; y++){
            int kmod = k % 3;
            if(kmod == 0) dp[kmod][y] += discomfort[k][y];
            if(kmod == 1) dp[kmod][y] += discomfort[k][y];
            if(kmod == 2) dp[kmod][y] += discomfort[k][y];
        }
    }
    // for(int k = 0; k < C; k++){
    //     for(int y = 0; y < C; y++) printf("dp[%d][%d]=%lld ", k, y, dp[k][y]);
    //     printf("\n");
    // }
    
    // 4. 最小値を計算.
    // 以下の条件で, 色を変更したと仮定して, 全探索で確認.
    // kmod == 0: 色 y0
    // kmod == 1: 色 y1
    // kmod == 2: 色 y2
    LL ans = 1e9;
    for(int y0 = 0; y0 < C; y0++){
        for(int y1 = 0; y1 < C; y1++){
            for(int y2 = 0; y2 < C; y2++){
                if(y0 != y1 && y1 != y2 && y2 != y0){
                    ans = min(ans, dp[0][y0] + dp[1][y1] + dp[2][y2]);
                }
            }
        }
    }
    
    // 5. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

typedef pair<LL, int> pli;

LL d[33][33], c[555][555];

// i + j = k の場合に, 色X から色Y に塗り替えた場合の違和感を保存.

// -> k と色Y に塗り替えた場合の違和感を保存.

LL discomfort[1111][33];

// k を 3で割った余りが, 0, 1, 2 のパターンに集約.

LL dp[3][33];

int main() {

// 1. 入力情報取得.

int N, C;

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

for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) scanf("%lld", &d[i][j]);

for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) scanf("%lld", &c[i][j]);

for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) c[i][j]--;

// 2. 違和感を集計.

// マス(i, j) (但し, i + j = k とする) を, 色y に塗り替えた場合の違和感を調査.

for(int k = 0; k < N; k++){

for(int i = 0; i <= k && i < N; i++){

int j = k - i;

for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y];

}

for(int k = N; k < 2 * N - 1; k++){

for(int i = k - (N - 1); i < N; i++){

int j = k - i;

for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y];

}

// for(int k = 0; k < 2 * N - 1; k++){

// for(int y = 0; y < C; y++) printf("discomfort[%d][%d]=%lld ", k, y, discomfort[k][y]);

// printf("\n");

// }

// 3. 違和感の和を集計(k を 3 で割ったときの余りで分類).

// 各 k ごとに, 色y に塗り替えた場合の違和感の最小値を選択.

for(int k = 0; k < 2 * N - 1; k++){

for(int y = 0; y <= 32; y++){

int kmod = k % 3;

if(kmod == 0) dp[kmod][y] += discomfort[k][y];

if(kmod == 1) dp[kmod][y] += discomfort[k][y];

if(kmod == 2) dp[kmod][y] += discomfort[k][y];

}

// for(int k = 0; k < C; k++){

// for(int y = 0; y < C; y++) printf("dp[%d][%d]=%lld ", k, y, dp[k][y]);

// printf("\n");

// }

// 4. 最小値を計算.

// 以下の条件で, 色を変更したと仮定して, 全探索で確認.

// kmod == 0: 色 y0

// kmod == 1: 色 y1

// kmod == 2: 色 y2

LL ans = 1e9;

for(int y0 = 0; y0 < C; y0++){

for(int y1 = 0; y1 < C; y1++){

for(int y2 = 0; y2 < C; y2++){

if(y0 != y1 && y1 != y2 && y2 != y0){

ans = min(ans, dp[0][y0] + dp[1][y1] + dp[2][y2]);

}

// 5. 出力～後処理.

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

return 0;

}

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

[出力例(debug版)]
dp[0][0]=0 dp[0][1]=1 dp[0][2]=1 
dp[1][0]=2 dp[1][1]=4 dp[1][2]=1 
dp[2][0]=1 dp[2][1]=4 dp[2][2]=0 
3
※AtCoderテストケースより

[入力例]
4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

[出力例(debug版)]
dp[0][0]=162 dp[0][1]=48 dp[0][2]=390 
dp[1][0]=162 dp[1][1]=36 dp[1][2]=319 
dp[2][0]=257 dp[2][1]=104 dp[2][2]=230 
428
※AtCoderテストケースより

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

[出力例(debug版)]
dp[0][0]=505 dp[0][1]=483 dp[0][2]=521 dp[0][3]=487 dp[0][4]=539 dp[0][5]=585 dp[0][6]=474 
dp[1][0]=634 dp[1][1]=643 dp[1][2]=637 dp[1][3]=594 dp[1][4]=521 dp[1][5]=706 dp[1][6]=594 
dp[2][0]=567 dp[2][1]=552 dp[2][2]=567 dp[2][3]=546 dp[2][4]=568 dp[2][5]=605 dp[2][6]=528 
dp[3][0]=0 dp[3][1]=7 dp[3][2]=0 dp[3][3]=8 dp[3][4]=9 dp[3][5]=10 dp[3][6]=11 
dp[4][0]=0 dp[4][1]=50 dp[4][2]=52 dp[4][3]=54 dp[4][4]=56 dp[4][5]=0 dp[4][6]=58 
dp[5][0]=0 dp[5][1]=56 dp[5][2]=59 dp[5][3]=62 dp[5][4]=65 dp[5][5]=39 dp[5][6]=34 
dp[6][0]=0 dp[6][1]=76 dp[6][2]=72 dp[6][3]=83 dp[6][4]=43 dp[6][5]=89 dp[6][6]=57 
1532

[入力例]

2 3

0 1 1

1 0 1

1 4 0

1 2

3 3

[出力例(debug版)]

dp[0][0]=0 dp[0][1]=1 dp[0][2]=1

dp[1][0]=2 dp[1][1]=4 dp[1][2]=1

dp[2][0]=1 dp[2][1]=4 dp[2][2]=0

※AtCoderテストケースより

[入力例]

4 3

0 12 71

81 0 53

14 92 0

1 1 2 1

2 1 1 2

2 2 1 3

1 1 2 2

[出力例(debug版)]

dp[0][0]=162 dp[0][1]=48 dp[0][2]=390

dp[1][0]=162 dp[1][1]=36 dp[1][2]=319

dp[2][0]=257 dp[2][1]=104 dp[2][2]=230

428

※AtCoderテストケースより

[入力例]

10 7

0 1 2 3 4 5 6

7 0 8 9 10 11 12

13 14 0 15 16 17 18

19 20 21 0 22 23 24

25 26 27 28 0 29 30

31 32 33 34 35 0 36

37 38 39 40 41 42 0

2 5 5 4 2 3 4 5 3 3

5 6 2 7 1 7 6 6 1 5

1 6 4 5 4 2 1 1 2 7

4 7 4 1 4 4 7 4 2 2

4 4 7 3 5 5 5 1 6 1

2 2 6 6 2 7 3 7 1 4

1 3 7 3 7 7 1 1 5 5

7 4 4 4 7 1 5 7 2 1

1 5 1 2 1 3 1 2 5 3

3 3 2 1 4 2 1 5 2 7

[出力例(debug版)]

dp[0][0]=505 dp[0][1]=483 dp[0][2]=521 dp[0][3]=487 dp[0][4]=539 dp[0][5]=585 dp[0][6]=474

dp[1][0]=634 dp[1][1]=643 dp[1][2]=637 dp[1][3]=594 dp[1][4]=521 dp[1][5]=706 dp[1][6]=594

dp[2][0]=567 dp[2][1]=552 dp[2][2]=567 dp[2][3]=546 dp[2][4]=568 dp[2][5]=605 dp[2][6]=528

dp[3][0]=0 dp[3][1]=7 dp[3][2]=0 dp[3][3]=8 dp[3][4]=9 dp[3][5]=10 dp[3][6]=11

dp[4][0]=0 dp[4][1]=50 dp[4][2]=52 dp[4][3]=54 dp[4][4]=56 dp[4][5]=0 dp[4][6]=58

dp[5][0]=0 dp[5][1]=56 dp[5][2]=59 dp[5][3]=62 dp[5][4]=65 dp[5][5]=39 dp[5][6]=34

dp[6][0]=0 dp[6][1]=76 dp[6][2]=72 dp[6][3]=83 dp[6][4]=43 dp[6][5]=89 dp[6][6]=57

1532

■参照サイト
AtCoder Beginner Contest 099

2019年7月25日2019年7月25日

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

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

■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. キューに追加されたことが無いかどうかの判定をするための実装が, 結構苦労した(set で対応しようとしたが, 上手く行かなかった, 他に良い方法が思いつかず, 結局, map で, 対応した).
3. map の key に, prefix(接頭語) を追加したが, おそらく, 不要だと思う.

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

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

// 解き直し.
// AtCoder Beginner Contest 123 解説.
// https://img.atcoder.jp/abc123/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
using LL = long long;
const int MAX = 1e3 + 1;
LL A[MAX], B[MAX], C[MAX];

struct cake{
    LL  d; // 美味しさの合計.
    int a; // A の index.
    int b; // B の index.
    int c; // C の index.
    bool operator < (const cake &C) const { return d < C.d; }
};

// 与えられた情報を結合して, 文字列を返却.
// @param prefix: 接頭語.
// @param d: 美味しさの合計.
// @param a: A の index.
// @param b: B の index.
// @param c: C の index.
// @return ret: map に 登録する 文字列 key.
string makeKey(string prefix, LL d, int a, int b, int c){
    string ret = prefix;
    ret += {"_"};
    ret += to_string(A[a] + B[b] + C[c]);
    ret += {"_"};
    ret += to_string(a);
    ret += {"_"};
    ret += to_string(b);
    ret += {"_"};
    ret += to_string(c);
    return ret;
}

int main(){
    
    // 1. 入力情報取得.
    int X, Y, Z, K;
    scanf("%d %d %d %d", &X, &Y, &Z, &K);
    FOR(i, 0, X) scanf("%lld", A + i);
    FOR(i, 0, Y) scanf("%lld", B + i);
    FOR(i, 0, Z) scanf("%lld", C + i);
    
    // 2. 降順sort.
    sort(A, A + MAX, greater<LL>());
    sort(B, B + MAX, greater<LL>());
    sort(C, C + MAX, greater<LL>());
    
    // 3. 解説通り(※Priority Queue (優先度付きキュー) を 使うパターン).
    int a = 0, b = 0, c = 0;
    priority_queue<cake> pq;
    map<string, int> m;
    pq.push({A[a] + B[b] + C[c], a, b, c});
    string s = makeKey("p", A[a] + B[b] + C[c], a, b, c);
    m[s]++;
    int index = 1;
    while(!pq.empty()){
        // 3-1. pq の中で, 一番美味しさの大きい要素を取得.
        cake i = pq.top();
        a = i.a, b = i.b, c = i.c;
        pq.pop();
        
        // 3-2. 追加されてないパターンを追加.
        cake p1 = {A[a + 1] + B[b] + C[c], a + 1, b, c};
        string s1 = makeKey("p", A[a + 1] + B[b] + C[c], a + 1, b, c);
        cake p2 = {A[a] + B[b + 1] + C[c], a, b + 1, c};
        string s2 = makeKey("p", A[a] + B[b + 1] + C[c], a, b + 1, c);
        cake p3 = {A[a] + B[b] + C[c + 1], a, b, c + 1};
        string s3 = makeKey("p", A[a] + B[b] + C[c + 1], a, b, c + 1);
        if(a < X - 1 && m[s1] == 0) pq.push(p1), m[s1]++;
        if(b < Y - 1 && m[s2] == 0) pq.push(p2), m[s2]++;
        if(c < Z - 1 && m[s3] == 0) pq.push(p3), m[s3]++;

        // 3-3. index番目 のケーキの美味しさの合計を出力.
        printf("%lld\n", i.d);
        
        // 3-4. increment.
        index++;
        
        // 3-5. index番目 が Kより大きくなったら終了.
        if(index > K) break;
    }
    // printf with std::string?
    // https://stackoverflow.com/questions/10865957/printf-with-stdstring
    // for(auto &e : m) printf("key=%s, value=%d\n", e.first.c_str(), e.second);
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 123 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

using LL = long long;

const int MAX = 1e3 + 1;

LL A[MAX], B[MAX], C[MAX];

struct cake{

LL d; // 美味しさの合計.

int a; // A の index.

int b; // B の index.

int c; // C の index.

bool operator < (const cake &C) const { return d < C.d; }

};

// 与えられた情報を結合して, 文字列を返却.

// @param prefix: 接頭語.

// @param d: 美味しさの合計.

// @param a: A の index.

// @param b: B の index.

// @param c: C の index.

// @return ret: map に登録する文字列 key.

string makeKey(string prefix, LL d, int a, int b, int c){

string ret = prefix;

ret += {"_"};

ret += to_string(A[a] + B[b] + C[c]);

ret += {"_"};

ret += to_string(a);

ret += {"_"};

ret += to_string(b);

ret += {"_"};

ret += to_string(c);

return ret;

}

int main(){

// 1. 入力情報取得.

int X, Y, Z, K;

scanf("%d %d %d %d", &X, &Y, &Z, &K);

FOR(i, 0, X) scanf("%lld", A + i);

FOR(i, 0, Y) scanf("%lld", B + i);

FOR(i, 0, Z) scanf("%lld", C + i);

// 2. 降順sort.

sort(A, A + MAX, greater<LL>());

sort(B, B + MAX, greater<LL>());

sort(C, C + MAX, greater<LL>());

// 3. 解説通り(※Priority Queue (優先度付きキュー) を使うパターン).

int a = 0, b = 0, c = 0;

priority_queue<cake> pq;

map<string, int> m;

pq.push({A[a] + B[b] + C[c], a, b, c});

string s = makeKey("p", A[a] + B[b] + C[c], a, b, c);

m[s]++;

int index = 1;

while(!pq.empty()){

// 3-1. pq の中で, 一番美味しさの大きい要素を取得.

cake i = pq.top();

a = i.a, b = i.b, c = i.c;

pq.pop();

// 3-2. 追加されてないパターンを追加.

cake p1 = {A[a + 1] + B[b] + C[c], a + 1, b, c};

string s1 = makeKey("p", A[a + 1] + B[b] + C[c], a + 1, b, c);

cake p2 = {A[a] + B[b + 1] + C[c], a, b + 1, c};

string s2 = makeKey("p", A[a] + B[b + 1] + C[c], a, b + 1, c);

cake p3 = {A[a] + B[b] + C[c + 1], a, b, c + 1};

string s3 = makeKey("p", A[a] + B[b] + C[c + 1], a, b, c + 1);

if(a < X - 1 && m[s1] == 0) pq.push(p1), m[s1]++;

if(b < Y - 1 && m[s2] == 0) pq.push(p2), m[s2]++;

if(c < Z - 1 && m[s3] == 0) pq.push(p3), m[s3]++;

// 3-3. index番目のケーキの美味しさの合計を出力.

printf("%lld\n", i.d);

// 3-4. increment.

index++;

// 3-5. index番目が Kより大きくなったら終了.

if(index > K) break;

}

// printf with std::string?

// https://stackoverflow.com/questions/10865957/printf-with-stdstring

// for(auto &e : m) printf("key=%s, value=%d\n", e.first.c_str(), e.second);

return 0;

}

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

[出力例(debug版)]
19
17
15
14
13
12
10
8
key=p_10_0_1_1, value=1
key=p_12_1_0_1, value=1
key=p_13_1_1_0, value=1
key=p_14_0_0_1, value=1
key=p_15_0_1_0, value=1
key=p_17_1_0_0, value=1
key=p_19_0_0_0, value=1
key=p_8_1_1_1, value=1
※AtCoderテストケースより

[入力例]
3 3 3 5
1 10 100
2 20 200
1 10 100

[出力例(debug版)]
400
310
310
301
301
key=p_121_0_1_2, value=1
key=p_121_2_1_0, value=1
key=p_130_0_1_1, value=1
key=p_130_1_1_0, value=1
key=p_211_1_0_2, value=1
key=p_211_2_0_1, value=1
key=p_220_0_1_0, value=1
key=p_220_1_0_1, value=1
key=p_301_0_0_2, value=1
key=p_301_2_0_0, value=1
key=p_310_0_0_1, value=1
key=p_310_1_0_0, value=1
key=p_400_0_0_0, value=1
※AtCoderテストケースより

[入力例]
10 10 10 20
7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488
1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338
4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

[出力例(debug版)]
23379871545
22444657051
22302177772
22095691512
21667941469
21366963278
21287912315
21279176669
21160477018
21085311041
21059876163
21017997739
20703329561
20702387965
20590247696
20383761436
20343962175
20254073196
20210218542
20150096547
key=p_18359588776_6_0_0, value=1
key=p_18445954391_1_0_3, value=1
key=p_18926038509_3_1_1, value=1
key=p_18969893163_0_4_1, value=1
key=p_19059782142_1_2_1, value=1
key=p_19072402774_1_1_2, value=1
key=p_19187217439_3_2_0, value=1
key=p_19306067663_2_1_1, value=1
key=p_19318858702_1_4_0, value=1
key=p_19373380965_2_0_2, value=1
key=p_19381168885_0_0_3, value=1
key=p_19418207932_5_0_1, value=1
key=p_19419149528_0_3_1, value=1
key=p_19567246593_2_2_0, value=1
key=p_19624694192_5_1_0, value=1
key=p_19768115067_1_3_0, value=1
key=p_19775696130_4_0_1, value=1
key=p_19953166481_0_5_0, value=1
key=p_19982182390_4_1_0, value=1
key=p_19994996636_0_2_1, value=1
key=p_20003732282_3_0_1, value=1
key=p_20007617268_0_1_2, value=1
key=p_20082783245_1_1_1, value=1
key=p_20150096547_1_0_2, value=1
key=p_20210218542_3_1_0, value=1
key=p_20254073196_0_4_0, value=1
key=p_20343962175_1_2_0, value=1
key=p_20383761436_2_0_1, value=1
key=p_20590247696_2_1_0, value=1
key=p_20702387965_5_0_0, value=1
key=p_20703329561_0_3_0, value=1
key=p_21017997739_0_1_1, value=1
key=p_21059876163_4_0_0, value=1
key=p_21085311041_0_0_2, value=1
key=p_21160477018_1_0_1, value=1
key=p_21279176669_0_2_0, value=1
key=p_21287912315_3_0_0, value=1
key=p_21366963278_1_1_0, value=1
key=p_21667941469_2_0_0, value=1
key=p_22095691512_0_0_1, value=1
key=p_22302177772_0_1_0, value=1
key=p_22444657051_1_0_0, value=1
key=p_23379871545_0_0_0, value=1
※AtCoderテストケースより

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

2 2 2 8

4 6

1 5

3 8

[出力例(debug版)]

key=p_10_0_1_1, value=1

key=p_12_1_0_1, value=1

key=p_13_1_1_0, value=1

key=p_14_0_0_1, value=1

key=p_15_0_1_0, value=1

key=p_17_1_0_0, value=1

key=p_19_0_0_0, value=1

key=p_8_1_1_1, value=1

※AtCoderテストケースより

[入力例]

3 3 3 5

1 10 100

2 20 200

1 10 100

[出力例(debug版)]

400

310

301

key=p_121_0_1_2, value=1

key=p_121_2_1_0, value=1

key=p_130_0_1_1, value=1

key=p_130_1_1_0, value=1

key=p_211_1_0_2, value=1

key=p_211_2_0_1, value=1

key=p_220_0_1_0, value=1

key=p_220_1_0_1, value=1

key=p_301_0_0_2, value=1

key=p_301_2_0_0, value=1

key=p_310_0_0_1, value=1

key=p_310_1_0_0, value=1

key=p_400_0_0_0, value=1

※AtCoderテストケースより

[入力例]

10 10 10 20

7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488

1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338

4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736

[出力例(debug版)]

23379871545

22444657051

22302177772

22095691512

21667941469

21366963278

21287912315

21279176669

21160477018

21085311041

21059876163

21017997739

20703329561

20702387965

20590247696

20383761436

20343962175

20254073196

20210218542

20150096547

key=p_18359588776_6_0_0, value=1

key=p_18445954391_1_0_3, value=1

key=p_18926038509_3_1_1, value=1

key=p_18969893163_0_4_1, value=1

key=p_19059782142_1_2_1, value=1

key=p_19072402774_1_1_2, value=1

key=p_19187217439_3_2_0, value=1

key=p_19306067663_2_1_1, value=1

key=p_19318858702_1_4_0, value=1

key=p_19373380965_2_0_2, value=1

key=p_19381168885_0_0_3, value=1

key=p_19418207932_5_0_1, value=1

key=p_19419149528_0_3_1, value=1

key=p_19567246593_2_2_0, value=1

key=p_19624694192_5_1_0, value=1

key=p_19768115067_1_3_0, value=1

key=p_19775696130_4_0_1, value=1

key=p_19953166481_0_5_0, value=1

key=p_19982182390_4_1_0, value=1

key=p_19994996636_0_2_1, value=1

key=p_20003732282_3_0_1, value=1

key=p_20007617268_0_1_2, value=1

key=p_20082783245_1_1_1, value=1

key=p_20150096547_1_0_2, value=1

key=p_20210218542_3_1_0, value=1

key=p_20254073196_0_4_0, value=1

key=p_20343962175_1_2_0, value=1

key=p_20383761436_2_0_1, value=1

key=p_20590247696_2_1_0, value=1

key=p_20702387965_5_0_0, value=1

key=p_20703329561_0_3_0, value=1

key=p_21017997739_0_1_1, value=1

key=p_21059876163_4_0_0, value=1

key=p_21085311041_0_0_2, value=1

key=p_21160477018_1_0_1, value=1

key=p_21279176669_0_2_0, value=1

key=p_21287912315_3_0_0, value=1

key=p_21366963278_1_1_0, value=1

key=p_21667941469_2_0_0, value=1

key=p_22095691512_0_0_1, value=1

key=p_22302177772_0_1_0, value=1

key=p_22444657051_1_0_0, value=1

key=p_23379871545_0_0_0, value=1

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 123

2019年7月24日2019年7月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 118 の問題D (D – Match Matching) を解いてみた.

■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 複雑怪奇に感じたものの, 苦手な DP の訓練となったと思う.

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

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

// 解き直し.
// ABC 118 解説.
// https://img.atcoder.jp/abc118/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
const int MATCH[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6};
int dp[12321];
struct match{
    int n; // マッチ棒で表現する数字.
    int u; // 数字1文字を構成するのに必要なマッチの使用本数.
    bool operator<(const match& rhs) const {
        return (u < rhs.u) || ((u == rhs.u) && (n > rhs.n));
    }
};

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<match> A;
    FOR(i, 0, M){
        int a;
        scanf("%d", &a);
        match m;
        m.n = a, m.u = MATCH[a - 1];
        A.push_back(m);
    }
    
    // 2. 初期化, sort.
    FOR(i, 0, N + 1) dp[i] = -123454321;
    sort(A.begin(), A.end());
    // for(auto &a : A) printf("%d %d\n", a.u, a.n);
    
    // 3. 解説通り.
    // dp[i]: ちょうどi本のマッチ棒を使って, 条件を満たす整数を作る場合の最大桁数.
    dp[0] = 0;
    FOR(i, 1, N + 1) for(auto &a : A) if(i >= a.u) dp[i] = max(dp[i], dp[i - a.u] + 1);
    // printf("dp[%d]=%d\n", N, dp[N]);
    
    // 4. dp の 結果をもとに, 出力.
    while(N > 0){
        // 4-1. 最上位の桁 を 抽出.
        int d = 0;
        for(auto &a : A){
            // a.n が 最上位の桁 に使えるかどうかは, 
            // dp[N - a.u] = dp[N] - 1 であるかを確認すれば良い, とのこと.
            if(N - a.u >= 0 && dp[N - a.u] == dp[N] - 1) d = max(d, a.n);
        }
        // 4-2. 最上位の桁が確定したので, 未使用のマッチ棒の本数 N を デクリメント.
        N -= MATCH[d - 1];
        printf("%d", d);
    }
    return 0;
    
}

// 解き直し.

// ABC 118 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

const int MATCH[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6};

int dp[12321];

struct match{

int n; // マッチ棒で表現する数字.

int u; // 数字1文字を構成するのに必要なマッチの使用本数.

bool operator<(const match& rhs) const {

return (u < rhs.u) || ((u == rhs.u) && (n > rhs.n));

}

};

int main(){

// 1. 入力情報取得.

int N, M;

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

vector<match> A;

FOR(i, 0, M){

int a;

scanf("%d", &a);

match m;

m.n = a, m.u = MATCH[a - 1];

A.push_back(m);

}

// 2. 初期化, sort.

FOR(i, 0, N + 1) dp[i] = -123454321;

sort(A.begin(), A.end());

// for(auto &a : A) printf("%d %d\n", a.u, a.n);

// 3. 解説通り.

// dp[i]: ちょうどi本のマッチ棒を使って, 条件を満たす整数を作る場合の最大桁数.

dp[0] = 0;

FOR(i, 1, N + 1) for(auto &a : A) if(i >= a.u) dp[i] = max(dp[i], dp[i - a.u] + 1);

// printf("dp[%d]=%d\n", N, dp[N]);

// 4. dp の結果をもとに, 出力.

while(N > 0){

// 4-1. 最上位の桁を抽出.

int d = 0;

for(auto &a : A){

// a.n が最上位の桁に使えるかどうかは,

// dp[N - a.u] = dp[N] - 1 であるかを確認すれば良い, とのこと.

if(N - a.u >= 0 && dp[N - a.u] == dp[N] - 1) d = max(d, a.n);

}

// 4-2. 最上位の桁が確定したので, 未使用のマッチ棒の本数 N をデクリメント.

N -= MATCH[d - 1];

printf("%d", d);

}

return 0;

}

[入力例]
2 1
1

[出力例]
1

[入力例]
5 2
1 7

[出力例]
71

[入力例]
20 4
3 7 8 4

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

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

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

[入力例]
15 3
5 4 6

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

[入力例]
31 5
2 3 5 7 9

[出力例]
777777755

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

[出力例]
9999555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555

[入力例]

2 1

[出力例]

[入力例]

5 2

1 7

[出力例]

[入力例]

20 4

3 7 8 4

[出力例]

777773

※AtCoderテストケースより

[入力例]

101 9

9 8 7 6 5 4 3 2 1

[出力例]

71111111111111111111111111111111111111111111111111

※AtCoderテストケースより

[入力例]

15 3

5 4 6

[出力例]

654

※AtCoderテストケースより

[入力例]

31 5

2 3 5 7 9

[出力例]

777777755

[入力例]

999 7

9 8 6 5 3 2

[出力例]

9999555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555

■参照サイト
AtCoder Beginner Contest 118

2019年7月21日2019年7月21日

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

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題A (A – Triangle) を解いてみた.

■感想.
1. 基本的には, 座標平面上で三角形の面積を計算する公式をベースに実装した.
2. とりあえず, 解説見る前に解けたので, 及第点は, 取れたように思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL UPPER = 1e9;

int main(){
    
    // 1. 入力情報取得.
    LL S;
    scanf("%lld", &S);
    
    // 2. 三頂点を計算.
    // (X1, Y1) は, 原点と設定.
    // 座標平面上で三角形の面積を計算する公式.
    // https://mathwords.net/x1y2hikux2y
    LL X1, X2, X3, Y1, Y2, Y3;
    X1 = 0LL;
    Y1 = 0LL;
    X2 = min((LL)sqrt(S) + 1LL, UPPER);
    Y3 = min((LL)sqrt(S) + 1LL, UPPER);
    Y2 = 1LL;
    X3 = X2 * Y3 - S;
    // printf("%lld\n", X2 * Y3 - Y2 * X3);
    
    // 3. 出力 ～ 後処理.
    printf("%lld %lld %lld %lld %lld %lld\n", X1, Y1, X2, Y2, X3, Y3);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL UPPER = 1e9;

int main(){

// 1. 入力情報取得.

LL S;

scanf("%lld", &S);

// 2. 三頂点を計算.

// (X1, Y1) は, 原点と設定.

// 座標平面上で三角形の面積を計算する公式.

// https://mathwords.net/x1y2hikux2y

LL X1, X2, X3, Y1, Y2, Y3;

X1 = 0LL;

Y1 = 0LL;

X2 = min((LL)sqrt(S) + 1LL, UPPER);

Y3 = min((LL)sqrt(S) + 1LL, UPPER);

Y2 = 1LL;

X3 = X2 * Y3 - S;

// printf("%lld\n", X2 * Y3 - Y2 * X3);

// 3. 出力～後処理.

printf("%lld %lld %lld %lld %lld %lld\n", X1, Y1, X2, Y2, X3, Y3);

return 0;

}

[入力例]
1

[出力例(debug版)]
1
0 0 2 1 3 2

[入力例]
2

[出力例(debug版)]
2
0 0 2 1 2 2

[入力例]
3

[出力例(debug版)]
3
0 0 3 0 3 1
※AtCoderテストケースより

[入力例]
4

[出力例(debug版)]
4
0 0 3 1 5 3

[入力例]
100

[出力例(debug版)]
100
0 0 11 1 21 11
※AtCoderテストケースより

[入力例]
54321

[出力例(debug版)]
54321
0 0 234 1 435 234

[入力例]
311114770564041497

[出力例(debug版)]
311114770564041497
0 0 557776632 1 641221927 557776632
※AtCoderテストケースより

[入力例]
1000000000000000000

[出力例(debug版)]
1000000000000000000
0 0 1000000000 1 0 1000000000

[入力例]
999999999999999999

[出力例(debug版)]
999999999999999999
0 0 1000000000 1 1 1000000000

[入力例]

[出力例(debug版)]

0 0 2 1 3 2

[入力例]

[出力例(debug版)]

0 0 2 1 2 2

[入力例]

[出力例(debug版)]

0 0 3 0 3 1

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

0 0 3 1 5 3

[入力例]

100

[出力例(debug版)]

100

0 0 11 1 21 11

※AtCoderテストケースより

[入力例]

54321

[出力例(debug版)]

54321

0 0 234 1 435 234

[入力例]

311114770564041497

[出力例(debug版)]

311114770564041497

0 0 557776632 1 641221927 557776632

※AtCoderテストケースより

[入力例]

1000000000000000000

[出力例(debug版)]

1000000000000000000

0 0 1000000000 1 0 1000000000

[入力例]

999999999999999999

[出力例(debug版)]

999999999999999999

0 0 1000000000 1 1 1000000000

■参照サイト
AtCoder Grand Contest 036
座標平面上で三角形の面積を計算する公式

2019年7月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 119 の問題D (D – Lazy Faith) を解いてみた.

■感想.
1. (if文の条件指定で, インデックス範囲を混乱して, 苦労したが)lower_bound の使い方を復習できたので, 良かったと思う.
2. とりあえず, 解説見る前に解けたので, 及第点は, 取れたように思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL S[123321], T[123321];
const LL MAX = 1e11;

int main(){
    
    // 1. 入力情報取得.
    LL A, B, Q;
    scanf("%lld %lld %lld", &A, &B, &Q);
    for(LL i = 0; i < A; i++) scanf("%lld", S + i);
    for(LL i = 0; i < B; i++) scanf("%lld", T + i);
    // for(LL i = 0; i < A; i++) printf("%lld ", S[i]);
    // printf("\n");
    // for(LL i = 0; i < B; i++) printf("%lld ", T[i]);
    // printf("\n");
    
    // 2. 最小の移動距離を計算し, 出力.
    for(LL i = 0; i < Q; i++){
        LL x;
        scanf("%lld", &x);
        // 神社一社を探索.
        LL s = lower_bound(S, S + A, x) - S;
        // 寺一軒を探索.
        LL t = lower_bound(T, T + B, x) - T;
        
        // 現在位置から, 左, 右 のいずれに進めば移動距離が, 最小となるかを検証.
        // 2-1. 神社: 左, 寺: 左.
        LL moveLL = MAX;
        if(s > 0 && t > 0) moveLL = max(x - S[s - 1], x - T[t - 1]);
        
        // 2-2. 神社: 左, 寺: 右.
        LL moveLR = MAX;
        if(s > 0 && t < B) moveLR = max(x - S[s - 1], T[t] - x) + 2 * min(x - S[s - 1], T[t] - x);
        
        // 2-3. 神社: 右, 寺: 左.
        LL moveRL = MAX;
        if(s < A && t > 0) moveRL = max(S[s] - x, x - T[t - 1]) + 2 * min(S[s] - x, x - T[t - 1]);

        // 2-4. 神社: 右, 寺: 右.
        LL moveRR = MAX;
        if(s < A && t < B) moveRR = max(S[s] - x, T[t] - x);
        
        // 2-5. 最小値を検証.
        LL move = min(moveLL, moveLR);
        move = min(move, moveRL);
        move = min(move, moveRR);
        // printf("x=%lld s=%lld t=%lld move=%lld\n", x, s, t, move);
        // printf("moveLL=%lld moveLR=%lld moveRL=%lld moveRR=%lld\n", moveLL, moveLR, moveRL, moveRR);
        printf("%lld\n", move);
    }
    
    // 3. 後処理.
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL S[123321], T[123321];

const LL MAX = 1e11;

int main(){

// 1. 入力情報取得.

LL A, B, Q;

scanf("%lld %lld %lld", &A, &B, &Q);

for(LL i = 0; i < A; i++) scanf("%lld", S + i);

for(LL i = 0; i < B; i++) scanf("%lld", T + i);

// for(LL i = 0; i < A; i++) printf("%lld ", S[i]);

// printf("\n");

// for(LL i = 0; i < B; i++) printf("%lld ", T[i]);

// printf("\n");

// 2. 最小の移動距離を計算し, 出力.

for(LL i = 0; i < Q; i++){

LL x;

scanf("%lld", &x);

// 神社一社を探索.

LL s = lower_bound(S, S + A, x) - S;

// 寺一軒を探索.

LL t = lower_bound(T, T + B, x) - T;

// 現在位置から, 左, 右のいずれに進めば移動距離が, 最小となるかを検証.

// 2-1. 神社: 左, 寺: 左.

LL moveLL = MAX;

if(s > 0 && t > 0) moveLL = max(x - S[s - 1], x - T[t - 1]);

// 2-2. 神社: 左, 寺: 右.

LL moveLR = MAX;

if(s > 0 && t < B) moveLR = max(x - S[s - 1], T[t] - x) + 2 * min(x - S[s - 1], T[t] - x);

// 2-3. 神社: 右, 寺: 左.

LL moveRL = MAX;

if(s < A && t > 0) moveRL = max(S[s] - x, x - T[t - 1]) + 2 * min(S[s] - x, x - T[t - 1]);

// 2-4. 神社: 右, 寺: 右.

LL moveRR = MAX;

if(s < A && t < B) moveRR = max(S[s] - x, T[t] - x);

// 2-5. 最小値を検証.

LL move = min(moveLL, moveLR);

move = min(move, moveRL);

move = min(move, moveRR);

// printf("x=%lld s=%lld t=%lld move=%lld\n", x, s, t, move);

// printf("moveLL=%lld moveLR=%lld moveRL=%lld moveRR=%lld\n", moveLL, moveLR, moveRL, moveRR);

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

}

// 3. 後処理.

return 0;

}

[入力例]
2 3 4
100
600
400
900
1000
150
2000
899
799

[出力例(debug版)]
x=150 s=1 t=0 move=350
moveLL=100000000000 moveLR=350 moveRL=100000000000 moveRR=450
350
x=2000 s=2 t=3 move=1400
moveLL=1400 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000
1400
x=899 s=2 t=1 move=301
moveLL=499 moveLR=301 moveRL=100000000000 moveRR=100000000000
301
x=799 s=2 t=1 move=399
moveLL=399 moveLR=401 moveRL=100000000000 moveRR=100000000000
399
※AtCoderテストケースより

[入力例]
1 1 3
1
10000000000
2
9999999999
5000000000

[出力例(debug版)]
x=2 s=1 t=0 move=10000000000
moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000
10000000000
x=9999999999 s=1 t=0 move=10000000000
moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000
10000000000
x=5000000000 s=1 t=0 move=14999999998
moveLL=100000000000 moveLR=14999999998 moveRL=100000000000 moveRR=100000000000
14999999998
※AtCoderテストケースより

[入力例]
5 4 15
200
500
700
900
1200
100
350
650
1100
0
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
1400

[出力例(debug版)]
x=0 s=0 t=0 move=200
moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=200
200
x=100 s=0 t=0 move=100
moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=100
100
x=200 s=0 t=1 move=100
moveLL=100000000000 moveLR=100000000000 moveRL=100 moveRR=150
100
x=300 s=1 t=1 move=200
moveLL=200 moveLR=200 moveRL=600 moveRR=200
200
x=400 s=1 t=2 move=200
moveLL=200 moveLR=650 moveRL=200 moveRR=250
200
x=500 s=1 t=2 move=150
moveLL=300 moveLR=600 moveRL=150 moveRR=150
150
x=600 s=2 t=2 move=100
moveLL=250 moveLR=200 moveRL=450 moveRR=100
100
x=700 s=2 t=3 move=50
moveLL=200 moveLR=800 moveRL=50 moveRR=400
50
x=800 s=3 t=3 move=150
moveLL=150 moveLR=500 moveRL=350 moveRR=300
150
x=900 s=3 t=3 move=200
moveLL=250 moveLR=600 moveRL=250 moveRR=200
200
x=1000 s=4 t=3 move=200
moveLL=350 moveLR=300 moveRL=750 moveRR=200
200
x=1100 s=4 t=3 move=100
moveLL=450 moveLR=200 moveRL=650 moveRR=100
100
x=1200 s=4 t=4 move=100
moveLL=300 moveLR=100000000000 moveRL=100 moveRR=100000000000
100
x=1300 s=5 t=4 move=200
moveLL=200 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000
200
x=1400 s=5 t=4 move=300
moveLL=300 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000
300

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

[入力例]

2 3 4

100

600

400

900

1000

150

2000

899

799

[出力例(debug版)]

x=150 s=1 t=0 move=350

moveLL=100000000000 moveLR=350 moveRL=100000000000 moveRR=450

350

x=2000 s=2 t=3 move=1400

moveLL=1400 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000

1400

x=899 s=2 t=1 move=301

moveLL=499 moveLR=301 moveRL=100000000000 moveRR=100000000000

301

x=799 s=2 t=1 move=399

moveLL=399 moveLR=401 moveRL=100000000000 moveRR=100000000000

399

※AtCoderテストケースより

[入力例]

1 1 3

10000000000

9999999999

5000000000

[出力例(debug版)]

x=2 s=1 t=0 move=10000000000

moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000

10000000000

x=9999999999 s=1 t=0 move=10000000000

moveLL=100000000000 moveLR=10000000000 moveRL=100000000000 moveRR=100000000000

10000000000

x=5000000000 s=1 t=0 move=14999999998

moveLL=100000000000 moveLR=14999999998 moveRL=100000000000 moveRR=100000000000

14999999998

※AtCoderテストケースより

[入力例]

5 4 15

200

500

700

900

1200

100

350

650

1100

100

200

300

400

500

600

700

800

900

1000

1100

1200

1300

1400

[出力例(debug版)]

x=0 s=0 t=0 move=200

moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=200

200

x=100 s=0 t=0 move=100

moveLL=100000000000 moveLR=100000000000 moveRL=100000000000 moveRR=100

100

x=200 s=0 t=1 move=100

moveLL=100000000000 moveLR=100000000000 moveRL=100 moveRR=150

100

x=300 s=1 t=1 move=200

moveLL=200 moveLR=200 moveRL=600 moveRR=200

200

x=400 s=1 t=2 move=200

moveLL=200 moveLR=650 moveRL=200 moveRR=250

200

x=500 s=1 t=2 move=150

moveLL=300 moveLR=600 moveRL=150 moveRR=150

150

x=600 s=2 t=2 move=100

moveLL=250 moveLR=200 moveRL=450 moveRR=100

100

x=700 s=2 t=3 move=50

moveLL=200 moveLR=800 moveRL=50 moveRR=400

x=800 s=3 t=3 move=150

moveLL=150 moveLR=500 moveRL=350 moveRR=300

150

x=900 s=3 t=3 move=200

moveLL=250 moveLR=600 moveRL=250 moveRR=200

200

x=1000 s=4 t=3 move=200

moveLL=350 moveLR=300 moveRL=750 moveRR=200

200

x=1100 s=4 t=3 move=100

moveLL=450 moveLR=200 moveRL=650 moveRR=100

100

x=1200 s=4 t=4 move=100

moveLL=300 moveLR=100000000000 moveRL=100 moveRR=100000000000

100

x=1300 s=5 t=4 move=200

moveLL=200 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000

200

x=1400 s=5 t=4 move=300

moveLL=300 moveLR=100000000000 moveRL=100000000000 moveRR=100000000000

300

■参照サイト
AtCoder Beginner Contest 119

2019年7月21日

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

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

■感想.
1. 問題E は, 解答方針が見えなかったので, 解説を参照して確認した.
2. LIS(Longest increase subsequence) のアルゴリズムを使う必要があるとの指摘があったが, “広義”単調減少と記載されていたので, プログラム上, 部分的に修正した.

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

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

// 解き直し.
// ABC 134解説.
// https://img.atcoder.jp/abc134/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<LL> A(N);
    vector<LL> dp;
    // 解説通りだが, LIS使う必要があるため, 後ろ側から値を保存.
    for(int i = 0; i < N; i++) scanf("%lld", &A[N - i - 1]);
    // for(int i = 0; i < N; i++) printf("%lld ", A[i]);
    
    // 2. 解説通り.
    // -> LIS で 解く必要があるとのこと.
    // -> "広義"単調減少列 との 記載から, lower_bound を upper_bound に 変更.
    dp.push_back(A[0]);
    for(int i = 1; i < N; i++){
        // 2-1. dpテーブル末尾 の 要素(last)以上 の 値(A[i])であれば, dpテーブル に 追加.
        int last = dp.back();
        // if(last < A[i]) dp.push_back(A[i]);
        if(last <= A[i]) dp.push_back(A[i]);    // "広義"用.
        // 2-2. dpテーブル末尾 の 要素(last) より小さな値(A[i])であれば, 
        // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新.
        if(last > A[i]){
            // auto it = lower_bound(dp.begin(), dp.end(), A[i]);
            auto it = upper_bound(dp.begin(), dp.end(), A[i]);    // "広義"用.
            int dist = it - dp.begin();
            dp[dist] = A[i];
            // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
            // cout << endl;
        }
    }
    // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
    // cout << endl;
    
    // 3. 出力 ～ 後処理.
    printf("%d\n", dp.size());
    return 0;
    
}

// 解き直し.

// ABC 134解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

vector<LL> A(N);

vector<LL> dp;

// 解説通りだが, LIS使う必要があるため, 後ろ側から値を保存.

for(int i = 0; i < N; i++) scanf("%lld", &A[N - i - 1]);

// for(int i = 0; i < N; i++) printf("%lld ", A[i]);

// 2. 解説通り.

// -> LIS で解く必要があるとのこと.

// -> "広義"単調減少列との記載から, lower_bound を upper_bound に変更.

dp.push_back(A[0]);

for(int i = 1; i < N; i++){

// 2-1. dpテーブル末尾の要素(last)以上の値(A[i])であれば, dpテーブルに追加.

int last = dp.back();

// if(last < A[i]) dp.push_back(A[i]);

if(last <= A[i]) dp.push_back(A[i]); // "広義"用.

// 2-2. dpテーブル末尾の要素(last) より小さな値(A[i])であれば,

// dpテーブル上の更新場所を探索後, dpテーブルを更新.

if(last > A[i]){

// auto it = lower_bound(dp.begin(), dp.end(), A[i]);

auto it = upper_bound(dp.begin(), dp.end(), A[i]); // "広義"用.

int dist = it - dp.begin();

dp[dist] = A[i];

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

}

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

// 3. 出力～後処理.

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

return 0;

}

[入力例]
5
2
1
4
5
3

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

[入力例]
4
0
0
0
0

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

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

[出力例]
5

[入力例]
100
14
13
66
96
30
78
79
29
84
22
91
29
12
77
78
59
97
17
91
57
78
59
61
78
0
93
8
60
28
12
37
12
80
34
5
63
3
14
22
92
6
19
60
58
18
37
95
2
41
49
14
62
20
75
56
78
13
47
69
66
77
71
33
67
13
1
83
31
47
85
51
78
32
42
17
48
35
26
77
80
44
46
30
58
85
4
40
15
78
79
10
0
95
6
63
87
63
1
54
54

[出力例]
18

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

■参照サイト
AtCoder Beginner Contest 134

2019年7月18日2019年7月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題D (D – Candidates of No Shortest Paths) を解いてみた.

■感想.
1. バグに気付くまでに時間かかってしまった(※M辺の入力情報を, N辺に誤記していた, debug中に, 漸く気付いた).
2. ほとんど馴染みのないダイクストラ法の訓練を出来たので良かったと思う.
3. 解説を見る前に, 何とか解答出来たので, とりあえず良かったと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int N, M;

struct edge {
    int to; // 次の頂点.
    int d;  // 距離.
    bool operator < (const edge &E) const { return d > E.d; }
};

int dist[101][101];    // 頂点(i, j) の 最短距離 を 保存.
vector<edge> graph[1001];

// https://ja.wikipedia.org/wiki/ダイクストラ法
// グラフを最良優先探索する.
// ※dijkstraの動作確認用.
// @param s: 今回探索する頂点番号.
// @return: 特に無し.
void dijkstra(int s) {
    
    // 1. 初期化.
    priority_queue<edge> pq;
    
    // 2. 始点設定.
    dist[s][s] = 0;
    pq.push({s, 0});

    // 3. キュー pq が 空になるまで, 探索.
    while(!pq.empty()){
        // 4. 探索を継続するために, 頂点を取得.
        int u = pq.top().to;
        int d = pq.top().d;
        pq.pop();
        
        // 5. より小さい距離が設定済みなら, Skip.
        if(dist[s][u] < d) continue;

        // 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新.
        for(int i = 0; i < graph[u].size(); ++i){
            int nu = graph[u][i].to;
            int nd = d + graph[u][i].d;
            // 最短経路更新.
            if(dist[s][nu] > nd) dist[s][nu] = nd, pq.push({nu, nd});
        }
    }
}

int main() {

    // 1. 入力情報取得.
    scanf("%d %d", &N, &M);
    map<pair<int, int>, int> m; // 二頂点間の距離を保存.
    for(int i = 0; i < M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        if(a > b) swap(a, b);
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
        m[{a, b}] = c;
    }
    
    // 2. 各二頂点間の最短経路を求める(ダイクストラ法).
    int ans = 0;
    for(int i = 0; i < 101; i++) for(int j = 0; j < 101; j++) dist[i][j] = INF;
    for(int i = 0; i < N - 1; i++){
        dijkstra(i);
        for(int j = i + 1; j < N; j++){
            // 始めに保存した二頂点間の距離が, 最短経路探索後の二頂点間の距離と異なっているのであれば, 
            // この辺は, 最短経路に含まれてないと判定.
            if(m[{i, j}] > 0 && m[{i, j}] != dist[i][j]) ans++;
            // printf("m[{%d, %d}]=%d dist[%d][%d]=%d\n", i, j, m[{i, j}], i, j, dist[i][j]);
        }
    }
    
    // 3. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e8;

int N, M;

struct edge {

int to; // 次の頂点.

int d; // 距離.

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

};

int dist[101][101]; // 頂点(i, j) の最短距離を保存.

vector<edge> graph[1001];

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

// グラフを最良優先探索する.

// ※dijkstraの動作確認用.

// @param s: 今回探索する頂点番号.

// @return: 特に無し.

void dijkstra(int s) {

// 1. 初期化.

priority_queue<edge> pq;

// 2. 始点設定.

dist[s][s] = 0;

pq.push({s, 0});

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

while(!pq.empty()){

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

int u = pq.top().to;

int d = pq.top().d;

pq.pop();

// 5. より小さい距離が設定済みなら, Skip.

if(dist[s][u] < d) continue;

// 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新.

for(int i = 0; i < graph[u].size(); ++i){

int nu = graph[u][i].to;

int nd = d + graph[u][i].d;

// 最短経路更新.

if(dist[s][nu] > nd) dist[s][nu] = nd, pq.push({nu, nd});

}

int main() {

// 1. 入力情報取得.

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

map<pair<int, int>, int> m; // 二頂点間の距離を保存.

for(int i = 0; i < M; i++){

int a, b, c;

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

a--, b--;

if(a > b) swap(a, b);

graph[a].push_back({b, c});

graph[b].push_back({a, c});

m[{a, b}] = c;

}

// 2. 各二頂点間の最短経路を求める(ダイクストラ法).

int ans = 0;

for(int i = 0; i < 101; i++) for(int j = 0; j < 101; j++) dist[i][j] = INF;

for(int i = 0; i < N - 1; i++){

dijkstra(i);

for(int j = i + 1; j < N; j++){

// 始めに保存した二頂点間の距離が, 最短経路探索後の二頂点間の距離と異なっているのであれば,

// この辺は, 最短経路に含まれてないと判定.

if(m[{i, j}] > 0 && m[{i, j}] != dist[i][j]) ans++;

// printf("m[{%d, %d}]=%d dist[%d][%d]=%d\n", i, j, m[{i, j}], i, j, dist[i][j]);

}

// 3. 出力～後処理.

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

return 0;

}

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

[出力例(debug版)]
m[{0, 1}]=1 dist[0][1]=1
m[{0, 2}]=1 dist[0][2]=1
m[{1, 2}]=3 dist[1][2]=2
1
※AtCoderテストケースより

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

[出力例(debug版)]
m[{0, 1}]=1 dist[0][1]=1
m[{0, 2}]=0 dist[0][2]=2
m[{1, 2}]=1 dist[1][2]=1
0
※AtCoderテストケースより

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

[出力例(debug版)]
m[{0, 1}]=5 dist[0][1]=5
m[{0, 2}]=0 dist[0][2]=3
m[{0, 3}]=2 dist[0][3]=2
m[{1, 2}]=3 dist[1][2]=3
m[{1, 3}]=0 dist[1][3]=4
m[{2, 3}]=1 dist[2][3]=1
0

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

[出力例(debug版)]
m[{0, 1}]=2 dist[0][1]=2
m[{0, 2}]=0 dist[0][2]=4
m[{0, 3}]=0 dist[0][3]=5
m[{0, 4}]=0 dist[0][4]=9
m[{0, 5}]=0 dist[0][5]=9
m[{0, 6}]=0 dist[0][6]=15
m[{0, 7}]=0 dist[0][7]=3
m[{0, 8}]=0 dist[0][8]=6
m[{0, 9}]=0 dist[0][9]=7
m[{0, 10}]=0 dist[0][10]=10
m[{0, 11}]=0 dist[0][11]=8
m[{1, 2}]=2 dist[1][2]=2
m[{1, 3}]=0 dist[1][3]=3
m[{1, 4}]=0 dist[1][4]=7
m[{1, 5}]=0 dist[1][5]=7
m[{1, 6}]=0 dist[1][6]=13
m[{1, 7}]=1 dist[1][7]=1
m[{1, 8}]=0 dist[1][8]=4
m[{1, 9}]=0 dist[1][9]=5
m[{1, 10}]=0 dist[1][10]=8
m[{1, 11}]=0 dist[1][11]=6
m[{2, 3}]=1 dist[2][3]=1
m[{2, 4}]=0 dist[2][4]=5
m[{2, 5}]=5 dist[2][5]=5
m[{2, 6}]=0 dist[2][6]=11
m[{2, 7}]=0 dist[2][7]=3
m[{2, 8}]=12 dist[2][8]=6
m[{2, 9}]=0 dist[2][9]=3
m[{2, 10}]=0 dist[2][10]=6
m[{2, 11}]=0 dist[2][11]=4
m[{3, 4}]=10 dist[3][4]=4
m[{3, 5}]=0 dist[3][5]=6
m[{3, 6}]=0 dist[3][6]=12
m[{3, 7}]=0 dist[3][7]=4
m[{3, 8}]=0 dist[3][8]=7
m[{3, 9}]=2 dist[3][9]=2
m[{3, 10}]=0 dist[3][10]=5
m[{3, 11}]=0 dist[3][11]=3
m[{4, 5}]=15 dist[4][5]=10
m[{4, 6}]=0 dist[4][6]=16
m[{4, 7}]=0 dist[4][7]=8
m[{4, 8}]=0 dist[4][8]=11
m[{4, 9}]=0 dist[4][9]=2
m[{4, 10}]=1 dist[4][10]=1
m[{4, 11}]=1 dist[4][11]=1
m[{5, 6}]=6 dist[5][6]=6
m[{5, 7}]=0 dist[5][7]=8
m[{5, 8}]=0 dist[5][8]=11
m[{5, 9}]=0 dist[5][9]=8
m[{5, 10}]=0 dist[5][10]=11
m[{5, 11}]=0 dist[5][11]=9
m[{6, 7}]=0 dist[6][7]=14
m[{6, 8}]=0 dist[6][8]=17
m[{6, 9}]=0 dist[6][9]=14
m[{6, 10}]=0 dist[6][10]=17
m[{6, 11}]=0 dist[6][11]=15
m[{7, 8}]=3 dist[7][8]=3
m[{7, 9}]=0 dist[7][9]=6
m[{7, 10}]=0 dist[7][10]=9
m[{7, 11}]=0 dist[7][11]=7
m[{8, 9}]=0 dist[8][9]=9
m[{8, 10}]=0 dist[8][10]=12
m[{8, 11}]=0 dist[8][11]=10
m[{9, 10}]=0 dist[9][10]=3
m[{9, 11}]=1 dist[9][11]=1
m[{10, 11}]=0 dist[10][11]=2
3

[入力例(subtask_1_16.txt)]
12 66
1 2 410
1 3 546
1 4 980
1 5 360
1 6 878
1 7 134
1 8 126
1 9 463
1 10 699
1 11 822
1 12 743
2 3 879
2 4 558
2 5 893
2 6 206
2 7 909
2 8 544
2 9 730
2 10 575
2 11 200
2 12 598
3 4 221
3 5 864
3 6 245
3 7 618
3 8 894
3 9 396
3 10 749
3 11 185
3 12 655
4 5 787
4 6 90
4 7 715
4 8 61
4 9 664
4 10 941
4 11 870
4 12 74
5 6 593
5 7 747
5 8 611
5 9 30
5 10 547
5 11 219
5 12 64
6 7 138
6 8 804
6 9 905
6 10 356
6 11 163
6 12 439
7 8 727
7 9 973
7 10 589
7 11 739
7 12 511
8 9 493
8 10 717
8 11 444
8 12 98
9 10 753
9 11 670
9 12 849
10 11 436
10 12 585
11 12 949

[出力例(debug版)]
m[{0, 1}]=410 dist[0][1]=410
m[{0, 2}]=546 dist[0][2]=408
m[{0, 3}]=980 dist[0][3]=187
m[{0, 4}]=360 dist[0][4]=288
m[{0, 5}]=878 dist[0][5]=272
m[{0, 6}]=134 dist[0][6]=134
m[{0, 7}]=126 dist[0][7]=126
m[{0, 8}]=463 dist[0][8]=318
m[{0, 9}]=699 dist[0][9]=628
m[{0, 10}]=822 dist[0][10]=435
m[{0, 11}]=743 dist[0][11]=224
m[{1, 2}]=879 dist[1][2]=385
m[{1, 3}]=558 dist[1][3]=296
m[{1, 4}]=893 dist[1][4]=419
m[{1, 5}]=206 dist[1][5]=206
m[{1, 6}]=909 dist[1][6]=344
m[{1, 7}]=544 dist[1][7]=357
m[{1, 8}]=730 dist[1][8]=449
m[{1, 9}]=575 dist[1][9]=562
m[{1, 10}]=200 dist[1][10]=200
m[{1, 11}]=598 dist[1][11]=370
m[{2, 3}]=221 dist[2][3]=221
m[{2, 4}]=864 dist[2][4]=359
m[{2, 5}]=245 dist[2][5]=245
m[{2, 6}]=618 dist[2][6]=383
m[{2, 7}]=894 dist[2][7]=282
m[{2, 8}]=396 dist[2][8]=389
m[{2, 9}]=749 dist[2][9]=601
m[{2, 10}]=185 dist[2][10]=185
m[{2, 11}]=655 dist[2][11]=295
m[{3, 4}]=787 dist[3][4]=138
m[{3, 5}]=90 dist[3][5]=90
m[{3, 6}]=715 dist[3][6]=228
m[{3, 7}]=61 dist[3][7]=61
m[{3, 8}]=664 dist[3][8]=168
m[{3, 9}]=941 dist[3][9]=446
m[{3, 10}]=870 dist[3][10]=253
m[{3, 11}]=74 dist[3][11]=74
m[{4, 5}]=593 dist[4][5]=228
m[{4, 6}]=747 dist[4][6]=366
m[{4, 7}]=611 dist[4][7]=162
m[{4, 8}]=30 dist[4][8]=30
m[{4, 9}]=547 dist[4][9]=547
m[{4, 10}]=219 dist[4][10]=219
m[{4, 11}]=64 dist[4][11]=64
m[{5, 6}]=138 dist[5][6]=138
m[{5, 7}]=804 dist[5][7]=151
m[{5, 8}]=905 dist[5][8]=258
m[{5, 9}]=356 dist[5][9]=356
m[{5, 10}]=163 dist[5][10]=163
m[{5, 11}]=439 dist[5][11]=164
m[{6, 7}]=727 dist[6][7]=260
m[{6, 8}]=973 dist[6][8]=396
m[{6, 9}]=589 dist[6][9]=494
m[{6, 10}]=739 dist[6][10]=301
m[{6, 11}]=511 dist[6][11]=302
m[{7, 8}]=493 dist[7][8]=192
m[{7, 9}]=717 dist[7][9]=507
m[{7, 10}]=444 dist[7][10]=314
m[{7, 11}]=98 dist[7][11]=98
m[{8, 9}]=753 dist[8][9]=577
m[{8, 10}]=670 dist[8][10]=249
m[{8, 11}]=849 dist[8][11]=94
m[{9, 10}]=436 dist[9][10]=436
m[{9, 11}]=585 dist[9][11]=520
m[{10, 11}]=949 dist[10][11]=283
46
※AtCoderテストケースより

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

[入力例]

3 3

1 2 1

1 3 1

2 3 3

[出力例(debug版)]

m[{0, 1}]=1 dist[0][1]=1

m[{0, 2}]=1 dist[0][2]=1

m[{1, 2}]=3 dist[1][2]=2

※AtCoderテストケースより

[入力例]

3 2

1 2 1

2 3 1

[出力例(debug版)]

m[{0, 1}]=1 dist[0][1]=1

m[{0, 2}]=0 dist[0][2]=2

m[{1, 2}]=1 dist[1][2]=1

※AtCoderテストケースより

[入力例]

4 4

1 2 5

2 3 3

4 1 2

3 4 1

[出力例(debug版)]

m[{0, 1}]=5 dist[0][1]=5

m[{0, 2}]=0 dist[0][2]=3

m[{0, 3}]=2 dist[0][3]=2

m[{1, 2}]=3 dist[1][2]=3

m[{1, 3}]=0 dist[1][3]=4

m[{2, 3}]=1 dist[2][3]=1

[入力例]

12 14

1 2 2

8 2 1

8 9 3

2 3 2

9 3 12

3 4 1

3 6 5

5 6 15

6 7 6

4 10 2

10 12 1

4 5 10

12 5 1

5 11 1

[出力例(debug版)]

m[{0, 1}]=2 dist[0][1]=2

m[{0, 2}]=0 dist[0][2]=4

m[{0, 3}]=0 dist[0][3]=5

m[{0, 4}]=0 dist[0][4]=9

m[{0, 5}]=0 dist[0][5]=9

m[{0, 6}]=0 dist[0][6]=15

m[{0, 7}]=0 dist[0][7]=3

m[{0, 8}]=0 dist[0][8]=6

m[{0, 9}]=0 dist[0][9]=7

m[{0, 10}]=0 dist[0][10]=10

m[{0, 11}]=0 dist[0][11]=8

m[{1, 2}]=2 dist[1][2]=2

m[{1, 3}]=0 dist[1][3]=3

m[{1, 4}]=0 dist[1][4]=7

m[{1, 5}]=0 dist[1][5]=7

m[{1, 6}]=0 dist[1][6]=13

m[{1, 7}]=1 dist[1][7]=1

m[{1, 8}]=0 dist[1][8]=4

m[{1, 9}]=0 dist[1][9]=5

m[{1, 10}]=0 dist[1][10]=8

m[{1, 11}]=0 dist[1][11]=6

m[{2, 3}]=1 dist[2][3]=1

m[{2, 4}]=0 dist[2][4]=5

m[{2, 5}]=5 dist[2][5]=5

m[{2, 6}]=0 dist[2][6]=11

m[{2, 7}]=0 dist[2][7]=3

m[{2, 8}]=12 dist[2][8]=6

m[{2, 9}]=0 dist[2][9]=3

m[{2, 10}]=0 dist[2][10]=6

m[{2, 11}]=0 dist[2][11]=4

m[{3, 4}]=10 dist[3][4]=4

m[{3, 5}]=0 dist[3][5]=6

m[{3, 6}]=0 dist[3][6]=12

m[{3, 7}]=0 dist[3][7]=4

m[{3, 8}]=0 dist[3][8]=7

m[{3, 9}]=2 dist[3][9]=2

m[{3, 10}]=0 dist[3][10]=5

m[{3, 11}]=0 dist[3][11]=3

m[{4, 5}]=15 dist[4][5]=10

m[{4, 6}]=0 dist[4][6]=16

m[{4, 7}]=0 dist[4][7]=8

m[{4, 8}]=0 dist[4][8]=11

m[{4, 9}]=0 dist[4][9]=2

m[{4, 10}]=1 dist[4][10]=1

m[{4, 11}]=1 dist[4][11]=1

m[{5, 6}]=6 dist[5][6]=6

m[{5, 7}]=0 dist[5][7]=8

m[{5, 8}]=0 dist[5][8]=11

m[{5, 9}]=0 dist[5][9]=8

m[{5, 10}]=0 dist[5][10]=11

m[{5, 11}]=0 dist[5][11]=9

m[{6, 7}]=0 dist[6][7]=14

m[{6, 8}]=0 dist[6][8]=17

m[{6, 9}]=0 dist[6][9]=14

m[{6, 10}]=0 dist[6][10]=17

m[{6, 11}]=0 dist[6][11]=15

m[{7, 8}]=3 dist[7][8]=3

m[{7, 9}]=0 dist[7][9]=6

m[{7, 10}]=0 dist[7][10]=9

m[{7, 11}]=0 dist[7][11]=7

m[{8, 9}]=0 dist[8][9]=9

m[{8, 10}]=0 dist[8][10]=12

m[{8, 11}]=0 dist[8][11]=10

m[{9, 10}]=0 dist[9][10]=3

m[{9, 11}]=1 dist[9][11]=1

m[{10, 11}]=0 dist[10][11]=2

[入力例(subtask_1_16.txt)]

12 66

1 2 410

1 3 546

1 4 980

1 5 360

1 6 878

1 7 134

1 8 126

1 9 463

1 10 699

1 11 822

1 12 743

2 3 879

2 4 558

2 5 893

2 6 206

2 7 909

2 8 544

2 9 730

2 10 575

2 11 200

2 12 598

3 4 221

3 5 864

3 6 245

3 7 618

3 8 894

3 9 396

3 10 749

3 11 185

3 12 655

4 5 787

4 6 90

4 7 715

4 8 61

4 9 664

4 10 941

4 11 870

4 12 74

5 6 593

5 7 747

5 8 611

5 9 30

5 10 547

5 11 219

5 12 64

6 7 138

6 8 804

6 9 905

6 10 356

6 11 163

6 12 439

7 8 727

7 9 973

7 10 589

7 11 739

7 12 511

8 9 493

8 10 717

8 11 444

8 12 98

9 10 753

9 11 670

9 12 849

10 11 436

10 12 585

11 12 949

[出力例(debug版)]

m[{0, 1}]=410 dist[0][1]=410

m[{0, 2}]=546 dist[0][2]=408

m[{0, 3}]=980 dist[0][3]=187

m[{0, 4}]=360 dist[0][4]=288

m[{0, 5}]=878 dist[0][5]=272

m[{0, 6}]=134 dist[0][6]=134

m[{0, 7}]=126 dist[0][7]=126

m[{0, 8}]=463 dist[0][8]=318

m[{0, 9}]=699 dist[0][9]=628

m[{0, 10}]=822 dist[0][10]=435

m[{0, 11}]=743 dist[0][11]=224

m[{1, 2}]=879 dist[1][2]=385

m[{1, 3}]=558 dist[1][3]=296

m[{1, 4}]=893 dist[1][4]=419

m[{1, 5}]=206 dist[1][5]=206

m[{1, 6}]=909 dist[1][6]=344

m[{1, 7}]=544 dist[1][7]=357

m[{1, 8}]=730 dist[1][8]=449

m[{1, 9}]=575 dist[1][9]=562

m[{1, 10}]=200 dist[1][10]=200

m[{1, 11}]=598 dist[1][11]=370

m[{2, 3}]=221 dist[2][3]=221

m[{2, 4}]=864 dist[2][4]=359

m[{2, 5}]=245 dist[2][5]=245

m[{2, 6}]=618 dist[2][6]=383

m[{2, 7}]=894 dist[2][7]=282

m[{2, 8}]=396 dist[2][8]=389

m[{2, 9}]=749 dist[2][9]=601

m[{2, 10}]=185 dist[2][10]=185

m[{2, 11}]=655 dist[2][11]=295

m[{3, 4}]=787 dist[3][4]=138

m[{3, 5}]=90 dist[3][5]=90

m[{3, 6}]=715 dist[3][6]=228

m[{3, 7}]=61 dist[3][7]=61

m[{3, 8}]=664 dist[3][8]=168

m[{3, 9}]=941 dist[3][9]=446

m[{3, 10}]=870 dist[3][10]=253

m[{3, 11}]=74 dist[3][11]=74

m[{4, 5}]=593 dist[4][5]=228

m[{4, 6}]=747 dist[4][6]=366

m[{4, 7}]=611 dist[4][7]=162

m[{4, 8}]=30 dist[4][8]=30

m[{4, 9}]=547 dist[4][9]=547

m[{4, 10}]=219 dist[4][10]=219

m[{4, 11}]=64 dist[4][11]=64

m[{5, 6}]=138 dist[5][6]=138

m[{5, 7}]=804 dist[5][7]=151

m[{5, 8}]=905 dist[5][8]=258

m[{5, 9}]=356 dist[5][9]=356

m[{5, 10}]=163 dist[5][10]=163

m[{5, 11}]=439 dist[5][11]=164

m[{6, 7}]=727 dist[6][7]=260

m[{6, 8}]=973 dist[6][8]=396

m[{6, 9}]=589 dist[6][9]=494

m[{6, 10}]=739 dist[6][10]=301

m[{6, 11}]=511 dist[6][11]=302

m[{7, 8}]=493 dist[7][8]=192

m[{7, 9}]=717 dist[7][9]=507

m[{7, 10}]=444 dist[7][10]=314

m[{7, 11}]=98 dist[7][11]=98

m[{8, 9}]=753 dist[8][9]=577

m[{8, 10}]=670 dist[8][10]=249

m[{8, 11}]=849 dist[8][11]=94

m[{9, 10}]=436 dist[9][10]=436

m[{9, 11}]=585 dist[9][11]=520

m[{10, 11}]=949 dist[10][11]=283

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 051
atcoder_testcases ABC051

2019年7月15日2019年7月18日

■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 但し, 実装上, 部分的に, いくつも推測(ex. 同じ座標を二度通らない, kの上限など)しているため, 題意と, ズレている可能性があると思われる.
3. テストケースの自作が困難だったため実装後, ネット上のatcoder_testcases ABC128で, テストケースをいくつか確認後, 提出した.
4. 余談としては, 前問である問題E (E – Roadwork) は, 知識不足(イベントソート) かつ (解説を読んだものの)解答不能だったため, 時間を見つけて, 類題など探して, 理解を深めていく必要があると思っている.

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

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

// 解き直し.
// ABC 128解説.
// https://img.atcoder.jp/abc128/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL S[123321];

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%lld", S + i);
    
    // 2. 解説通り.
    // 以下の情報から, 計算するとのこと.
    // 0, (N - 1) - k * C, C, (N - 1) - (k - 1) * C, 2 * C, ... k * C, N - 1.
    // -> f(k + 1, C) = f(k, C) + S[N - 1 - k * C] + S[k * C] (k >= 0)
    LL ans = 0;
    for(int c = 1; c < N; c++){
        LL cur = 0, bef = 0;
        map<LL, int> route; // 経路情報を保存.
        for(int k = 0; k < (N - 1) / c; k++){
            
            // 2-1. 経路情報チェック.
            // すでに通っていた場合は, 終了.
            int pos1 = N - 1 - k * c;
            int pos2 = k * c;
            route[pos1]++, route[pos2]++;
            if(route[pos1] != 1 || route[pos2] != 1) break;
            
            // 2-2. cur更新.
            cur = bef + S[pos1] + S[pos2];
            
            // 2-3. 最終得点更新.
            ans = max(ans, cur);
            
            // 2-4. bef更新.
            bef = cur;
        }
    }
    
    // 3. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// ABC 128解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL S[123321];

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 0; i < N; i++) scanf("%lld", S + i);

// 2. 解説通り.

// 以下の情報から, 計算するとのこと.

// 0, (N - 1) - k * C, C, (N - 1) - (k - 1) * C, 2 * C, ... k * C, N - 1.

// -> f(k + 1, C) = f(k, C) + S[N - 1 - k * C] + S[k * C] (k >= 0)

LL ans = 0;

for(int c = 1; c < N; c++){

LL cur = 0, bef = 0;

map<LL, int> route; // 経路情報を保存.

for(int k = 0; k < (N - 1) / c; k++){

// 2-1. 経路情報チェック.

// すでに通っていた場合は, 終了.

int pos1 = N - 1 - k * c;

int pos2 = k * c;

route[pos1]++, route[pos2]++;

if(route[pos1] != 1 || route[pos2] != 1) break;

// 2-2. cur更新.

cur = bef + S[pos1] + S[pos2];

// 2-3. 最終得点更新.

ans = max(ans, cur);

// 2-4. bef更新.

bef = cur;

}

// 3. 出力～後処理.

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

return 0;

}

[入力例]
5
0 2 5 1 0

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

[入力例]
6
0 10 -7 -4 -13 0

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

[入力例]
11
0 -4 0 -99 31 14 -15 -39 43 18 0

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

[入力例(09.txt)]
35
0 7 0 -4 -2 -2 -10 3 9 -4 10 8 4 4 7 -10 0 -10 8 -1 -5 -7 -2 -7 3 0 -4 8 -2 -2 -2 3 9 4 0

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

[入力例(10.txt)]
22
0 -10 -8 -5 10 -1 -5 -9 4 0 -1 -4 -4 -1 -6 -7 8 -5 -2 4 0 0

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

[入力例]

0 2 5 1 0

[出力例]

※AtCoderテストケースより

[入力例]

0 10 -7 -4 -13 0

[出力例]

※AtCoderテストケースより

[入力例]

0 -4 0 -99 31 14 -15 -39 43 18 0

[出力例]

※AtCoderテストケースより

[入力例(09.txt)]

0 7 0 -4 -2 -2 -10 3 9 -4 10 8 4 4 7 -10 0 -10 8 -1 -5 -7 -2 -7 3 0 -4 8 -2 -2 -2 3 9 4 0

[出力例]

※AtCoderテストケースより

[入力例(10.txt)]

0 -10 -8 -5 10 -1 -5 -9 4 0 -1 -4 -4 -1 -6 -7 8 -5 -2 4 0 0

[出力例]

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 128
atcoder_testcases ABC128

月: 2019年7月

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

C++の練習を兼ねて, AtCoder Beginner Contest 007 の問題D (D – 禁止された数字) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Worst Case) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Good Grid) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 118 の問題D (D – Match Matching) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題A (A – Triangle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 119 の問題D (D – Lazy Faith) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題D (D – Candidates of No Shortest Paths) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 128 の問題F (F – Frog Jump) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 007 の 問題D (D – 禁止された数字) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 099 の 問題D (D – Worst Case) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 099 の 問題D (D – Good Grid) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 118 の 問題D (D – Match Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 036 の 問題A (A – Triangle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 119 の 問題D (D – Lazy Faith) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の 問題D (D – Candidates of No Shortest Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 128 の 問題F (F – Frog Jump) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 007 の問題D (D – 禁止された数字) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Worst Case) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 099 の問題D (D – Good Grid) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 118 の問題D (D – Match Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題A (A – Triangle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 119 の問題D (D – Lazy Faith) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題D (D – Candidates of No Shortest Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 128 の問題F (F – Frog Jump) を解いてみた.