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

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題C (Made Up) ～問題D (aab aba baa) を解いてみた.

■感想.
1. 問題Dは, 動的計画法が使えそうに見えたので, 実装してみたところ, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 問題Dは, 動的計画法を使いながら, 文字列を確定させていく処理が, 個人的には, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    rep(i, N){
        scanf("%d", &c[i]);
        c[i]--;
    }
    
    // 2. b[c[j]] を 保存.
    rep(i, N) bc[b[c[i]]]++;
    
    // 3. 条件を満たす 整数の組(i, j) を 計算.
    LL ans = 0;
    rep(i, N) ans += bc[a[i]];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int a[101010], b[101010], c[101010];

LL bc[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

rep(i, N){

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

c[i]--;

}

// 2. b[c[j]] を保存.

rep(i, N) bc[b[c[i]]]++;

// 3. 条件を満たす整数の組(i, j) を計算.

LL ans = 0;

rep(i, N) ans += bc[a[i]];

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
39

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

[出力例]
455

[入力例]

1 2 2

3 1 2

2 3 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 3 3

1 3 3

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1 3 9 12 12 11 12 6 5 12 3 10 1 3 7 10 6 7 2

8 1 6 7 3 2 12 8 10 10 8 11 1 11 1 12 10 11 11 6

11 1 1 4 9 2 7 10 7 7 2 12 1 8 4 9 10 9 5 1

[出力例]

[入力例]

100

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

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

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

[出力例]

455

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
LL C[61][61];
LL dp[66][2]; // i番目を, 'a', 'b' のいずれを設定するか保存.

int main(){
    
    // 1. 入力情報.
    int A, B;
    LL K;
    scanf("%d %d %lld", &A, &B, &K);
    
    // 2. パスカルの三角形で, 事前計算.
    rep(i, 61){
        rep(j, 61){
            if(!j || j == i) C[i][j] = 1LL;
            else             C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    // rep(i, 20){
    //     rep(j, 20) printf("%lld ", C[i][j]);
    //     puts("");
    // }
    
    // 3. dp更新.
    string ans = "";
    int resA = A, resB = B;
    dp[0][0] = 1;
    dp[0][1] = 1 + C[resA + resB - 1][resB];
    repx(i, 1, A + B + 1){
        // 3-1. 前回分取得.
        if(dp[i - 1][1] <= K){
            dp[i][0] = dp[i][1] = dp[i - 1][1];
            ans.pb('b');
            resB--;
        }else{
            dp[i][0] = dp[i][1] = dp[i - 1][0];
            ans.pb('a');
            resA--;
        }
        assert(resA >= 0);
        assert(resB >= 0);
        
        // 3-2. i番目が, 'b' となる場合の開始番号.
        dp[i][1] += C[resA + resB - 1][resB];
    }
    // rep(i, 10) printf("%lld %lld\n", dp[i][0], dp[i][1]);
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

LL C[61][61];

LL dp[66][2]; // i番目を, 'a', 'b' のいずれを設定するか保存.

int main(){

// 1. 入力情報.

int A, B;

LL K;

scanf("%d %d %lld", &A, &B, &K);

// 2. パスカルの三角形で, 事前計算.

rep(i, 61){

rep(j, 61){

if(!j || j == i) C[i][j] = 1LL;

else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

}

// rep(i, 20){

// rep(j, 20) printf("%lld ", C[i][j]);

// puts("");

// }

// 3. dp更新.

string ans = "";

int resA = A, resB = B;

dp[0][0] = 1;

dp[0][1] = 1 + C[resA + resB - 1][resB];

repx(i, 1, A + B + 1){

// 3-1. 前回分取得.

if(dp[i - 1][1] <= K){

dp[i][0] = dp[i][1] = dp[i - 1][1];

ans.pb('b');

resB--;

}else{

dp[i][0] = dp[i][1] = dp[i - 1][0];

ans.pb('a');

resA--;

}

assert(resA >= 0);

assert(resB >= 0);

// 3-2. i番目が, 'b' となる場合の開始番号.

dp[i][1] += C[resA + resB - 1][resB];

}

// rep(i, 10) printf("%lld %lld\n", dp[i][0], dp[i][1]);

// 4. 出力.

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

return 0;

}

[入力例]
2 2 4

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

[入力例]
30 30 118264581564861424

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

[入力例]
3 2 5

[出力例]
ababa

[入力例]
1 1 1

[出力例]
ab

[入力例]
1 1 2

[出力例]
ba

[入力例]
1 3 4

[出力例]
bbba

[入力例]
5 3 25

[出力例]
abaababa

[入力例]
10 17 1234567

[出力例]
abaabbabbabbabbbababbbbbaba

[入力例]
25 11 123456789

[出力例]
aaaabbababaabaaaabbaaaaabaaabaabbaaa

[入力例]

2 2 4

[出力例]

baab

※AtCoderテストケースより

[入力例]

30 30 118264581564861424

[出力例]

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

※AtCoderテストケースより

[入力例]

3 2 5

[出力例]

ababa

[入力例]

1 1 1

[出力例]

[入力例]

1 1 2

[出力例]

[入力例]

1 3 4

[出力例]

bbba

[入力例]

5 3 25

[出力例]

abaababa

[入力例]

10 17 1234567

[出力例]

abaabbabbabbabbbababbbbbaba

[入力例]

25 11 123456789

[出力例]

aaaabbababaabaaaabbaaaaabaaabaabbaaa

■参照サイト
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

C++の練習を兼ねて, AtCoder Beginner Contest 202 の 問題C (Made Up) ～ 問題D (aab aba baa) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題C (Made Up) ～問題D (aab aba baa) を解いてみた.

コメントを残すコメントをキャンセル