C++ | 個人用メモ帳

2019年5月7日

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題A (A – Frog 1) ～問題C (C – Vacation) を解いてみた.

■感想.
1. DPが良くわかってないので, 練習問題が用意されていることが有難いです.
※最近になって, 気付いた過去問でした.

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

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL H[N + 1];
    H[0] = 0;
    for(int i = 1; i < N + 1; ++i) cin >> H[i];
    
    // 2. DP更新.
    LL DP[N + 1];
    for(int i = 0; i < N + 1; i++) DP[i] = 1e9;
    DP[0] = 0;
    DP[1] = 0;
    DP[2] = abs(H[2] - H[1]);
    for(int i = 3; i < N + 1; ++i){
        // i - 2 から ジャンプしてきた.
        DP[i] = min(DP[i], DP[i - 2] + abs(H[i] - H [i - 2]));
        // i - 1 から ジャンプしてきた.
        DP[i] = min(DP[i], DP[i - 1] + abs(H[i] - H [i - 1]));
    }
    
    // 3. 出力.
    cout << DP[N] << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL H[N + 1];

H[0] = 0;

for(int i = 1; i < N + 1; ++i) cin >> H[i];

// 2. DP更新.

LL DP[N + 1];

for(int i = 0; i < N + 1; i++) DP[i] = 1e9;

DP[0] = 0;

DP[1] = 0;

DP[2] = abs(H[2] - H[1]);

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

// i - 2 からジャンプしてきた.

DP[i] = min(DP[i], DP[i - 2] + abs(H[i] - H [i - 2]));

// i - 1 からジャンプしてきた.

DP[i] = min(DP[i], DP[i - 1] + abs(H[i] - H [i - 1]));

}

// 3. 出力.

cout << DP[N] << endl;

return 0;

}

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

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

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    cin >> N >> K;
    LL H[N + 1];
    H[0] = 0;
    for(int i = 1; i < N + 1; ++i) cin >> H[i];
    
    // 2. DP更新.
    LL DP[N + 1];
    for(int i = 0; i < N + 1; i++) DP[i] = 1e9;
    DP[0] = 0;
    DP[1] = 0;
    DP[2] = abs(H[2] - H[1]);
    for(int i = 3; i < N + 1; ++i){
        for(int k = 1; k <= K; k++){
            // i - k から ジャンプしてきた.
            if(i - k > 0) DP[i] = min(DP[i], DP[i - k] + abs(H[i] - H [i - k]));
        }
    }
    
    // 3. 出力.
    cout << DP[N] << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N, K;

cin >> N >> K;

LL H[N + 1];

H[0] = 0;

for(int i = 1; i < N + 1; ++i) cin >> H[i];

// 2. DP更新.

LL DP[N + 1];

for(int i = 0; i < N + 1; i++) DP[i] = 1e9;

DP[0] = 0;

DP[1] = 0;

DP[2] = abs(H[2] - H[1]);

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

for(int k = 1; k <= K; k++){

// i - k からジャンプしてきた.

if(i - k > 0) DP[i] = min(DP[i], DP[i - k] + abs(H[i] - H [i - k]));

}

// 3. 出力.

cout << DP[N] << endl;

return 0;

}

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

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL A[N + 1], B[N + 1], C[N + 1];
    A[0] = B[0] = C[0] = 0;
    for(int i = 1; i < N + 1; ++i){
        LL a, b, c;
        cin >> a >> b >> c;
        A[i] = a, B[i] = b, C[i] = c;
    }
    
    // 2. DP更新.
    LL DP[N + 1][3];
    for(int i = 0; i < N + 1; i++) for(int j = 0; j < 3; j++) DP[i][j] = 0;
    // 配列DP について, 第二成分を, 活動A = 0, 活動B = 1, 活動C = 2 と見る.
    DP[1][0] = A[1], DP[1][1] = B[1], DP[1][2] = C[1];
    for(int i = 2; i < N + 1; ++i){
        // i日目 の活動 が A の 場合 -> (i - 1)日目は, 活動 B or C.
        DP[i][0] = max(DP[i - 1][1] + A[i], DP[i - 1][2] + A[i]);
        // i日目 の活動 が B の 場合 -> (i - 1)日目は, 活動 A or C.
        DP[i][1] = max(DP[i - 1][0] + B[i], DP[i - 1][2] + B[i]);
        // i日目 の活動 が C の 場合 -> (i - 1)日目は, 活動 A or B.
        DP[i][2] = max(DP[i - 1][0] + C[i], DP[i - 1][1] + C[i]);
    }
    
    // 3. 出力.
    LL ans = 0;
    for(int i = 0; i < 3; i++) ans = max(ans, DP[N][i]);
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL A[N + 1], B[N + 1], C[N + 1];

A[0] = B[0] = C[0] = 0;

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

LL a, b, c;

cin >> a >> b >> c;

A[i] = a, B[i] = b, C[i] = c;

}

// 2. DP更新.

LL DP[N + 1][3];

for(int i = 0; i < N + 1; i++) for(int j = 0; j < 3; j++) DP[i][j] = 0;

// 配列DP について, 第二成分を, 活動A = 0, 活動B = 1, 活動C = 2 と見る.

DP[1][0] = A[1], DP[1][1] = B[1], DP[1][2] = C[1];

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

// i日目の活動が A の場合 -> (i - 1)日目は, 活動 B or C.

DP[i][0] = max(DP[i - 1][1] + A[i], DP[i - 1][2] + A[i]);

// i日目の活動が B の場合 -> (i - 1)日目は, 活動 A or C.

DP[i][1] = max(DP[i - 1][0] + B[i], DP[i - 1][2] + B[i]);

// i日目の活動が C の場合 -> (i - 1)日目は, 活動 A or B.

DP[i][2] = max(DP[i - 1][0] + C[i], DP[i - 1][1] + C[i]);

}

// 3. 出力.

LL ans = 0;

for(int i = 0; i < 3; i++) ans = max(ans, DP[N][i]);

cout << ans << endl;

return 0;

}

■参照サイト
Educational DP Contest / DP まとめコンテスト

2019年4月29日2019年4月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 125 の問題C (C – GCD on Blackboard) ～問題D (D – Flipping Signs) を解いてみた.

■感想.
1. 問題C, D ともに, 解答方針が全く見えなかったので, 解説を丸写しする感覚で解き直しした.

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

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

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL A[N + 1];
    A[0] = 0;
    for(int i = 1; i < N + 1; i++) cin >> A[i];
    
    // 2. 解説通り.
    // L[0], L[1], L[2], ... , L[N + 1]
    // R[0], R[1], R[2], ... , R[N + 1]
    // を用意する.
    LL L[N + 2], R[N + 2];
    L[0] = 0, R[N + 1] = 0;
    for(int i = 0; i <= N; i++) L[i + 1] = __gcd(L[i], A[i]);
    for(int i = N; i >= 0; i--) R[i] = __gcd(R[i + 1], A[i]);
    
    // 3. 解説通り.
    LL ans = 0;
    for(int i = 0; i <= N; i++) ans = max(ans, __gcd(L[i], R[i + 1]));
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL A[N + 1];

A[0] = 0;

for(int i = 1; i < N + 1; i++) cin >> A[i];

// 2. 解説通り.

// L[0], L[1], L[2], ... , L[N + 1]

// R[0], R[1], R[2], ... , R[N + 1]

// を用意する.

LL L[N + 2], R[N + 2];

L[0] = 0, R[N + 1] = 0;

for(int i = 0; i <= N; i++) L[i + 1] = __gcd(L[i], A[i]);

for(int i = N; i >= 0; i--) R[i] = __gcd(R[i + 1], A[i]);

// 3. 解説通り.

LL ans = 0;

for(int i = 0; i <= N; i++) ans = max(ans, __gcd(L[i], R[i + 1]));

// 4. 後処理.

cout << ans << endl;

return 0;

}

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

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL A[N];
    LL total = 0;
    int zero = 0, minus = 0;
    for(int i = 0; i < N; i++){
        LL a;
        cin >> a;
        A[i] = a;
        total += abs(a);
        if(a == 0) zero++;
        if(a < 0)  minus++;
    }
    
    // 2. 解説通り.
    LL ans = 0;
    for(int i = 0; i < N; i++) ans = max(ans, total - 2 * abs(A[i]));
    if(zero > 0 || minus % 2 == 0) ans = total;
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL A[N];

LL total = 0;

int zero = 0, minus = 0;

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

LL a;

cin >> a;

A[i] = a;

total += abs(a);

if(a == 0) zero++;

if(a < 0) minus++;

}

// 2. 解説通り.

LL ans = 0;

for(int i = 0; i < N; i++) ans = max(ans, total - 2 * abs(A[i]));

if(zero > 0 || minus % 2 == 0) ans = total;

// 3. 後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 125

2019年4月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 124 の問題C (Coloring Colorfully) ～問題D (Handstand) を解いてみた.

■感想.
1. 問題D は, 解答方針が全く見えなかったので, 解き直しすることになった.

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

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

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

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 塗り替えるタイルの枚数の最小値は？
    // 2-1. 1 -> 0 -> 1 -> ... パターン.
    int a1 = 0;
    char f1 = '1', f2 = '0';
    for(int i = 0; i < S.size(); i++){
        if(S[i] != f1) S[i] = f2, a1++;
        swap(f1, f2);
    }
    
    // 2-2. 0 -> 1 -> 0 -> ... パターン.
    int a2 = 0;
    f1 = '0', f2 = '1';
    for(int i = 0; i < S.size(); i++){
        if(S[i] != f1) S[i] = f2, a2++;
        swap(f1, f2);
    }
    
    // 3. 後処理.
    int ans = min(a1, a2);
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 塗り替えるタイルの枚数の最小値は？

// 2-1. 1 -> 0 -> 1 -> ... パターン.

int a1 = 0;

char f1 = '1', f2 = '0';

for(int i = 0; i < S.size(); i++){

if(S[i] != f1) S[i] = f2, a1++;

swap(f1, f2);

}

// 2-2. 0 -> 1 -> 0 -> ... パターン.

int a2 = 0;

f1 = '0', f2 = '1';

for(int i = 0; i < S.size(); i++){

if(S[i] != f1) S[i] = f2, a2++;

swap(f1, f2);

}

// 3. 後処理.

int ans = min(a1, a2);

cout << ans << endl;

return 0;

}

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

// 解き直し.
// ABC 124解説.
// https://img.atcoder.jp/abc124/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    // 2. 解説通り.
    // 連続する '0' or '1' の開始位置 i1, i2, i3, ... , ir を 取得.
    vector<int> v;
    // 前回出現文字.
    char bef = 'b';
    for(int i = 0; i < N; i++){
        // 今回出現文字.
        char cur = S[i];
        
        // 前回文字と異なる場合は, 文字位置を保存.
        if(bef != cur) v.push_back(i);
        
        // 前回出現文字更新.
        bef = cur;
    }
    v.push_back(N);
    // for(auto &p : v) cout << p << " ";
    
    // 3. S(ik) の 値 に応じて, 逆立ちした人を連続で最大何人並ばせることが出来るか計算.
    // S(ik) = '0' なら, X(ik) = i(k + 2 * K)     - i(k)
    // S(ik) = '1' なら, X(ik) = i(k + 2 * K + 1) - i(k)
    int ans = 0;
    int r = v.size();
    for(int k = 1; k < r; k++){
        if(S[v[k - 1]] == '0'){
            int u = min(r, k + 2 * K);
            ans = max(ans, v[u - 1] - v[k - 1]);
        }
        if(S[v[k - 1]] == '1'){
            int u = min(r, k + 2 * K + 1);
            ans = max(ans, v[u - 1] - v[k - 1]);
        }
    }
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// ABC 124解説.

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

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N, K;

string S;

cin >> N >> K >> S;

// 2. 解説通り.

// 連続する '0' or '1' の開始位置 i1, i2, i3, ... , ir を取得.

vector<int> v;

// 前回出現文字.

char bef = 'b';

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

// 今回出現文字.

char cur = S[i];

// 前回文字と異なる場合は, 文字位置を保存.

if(bef != cur) v.push_back(i);

// 前回出現文字更新.

bef = cur;

}

v.push_back(N);

// for(auto &p : v) cout << p << " ";

// 3. S(ik) の値に応じて, 逆立ちした人を連続で最大何人並ばせることが出来るか計算.

// S(ik) = '0' なら, X(ik) = i(k + 2 * K) - i(k)

// S(ik) = '1' なら, X(ik) = i(k + 2 * K + 1) - i(k)

int ans = 0;

int r = v.size();

for(int k = 1; k < r; k++){

if(S[v[k - 1]] == '0'){

int u = min(r, k + 2 * K);

ans = max(ans, v[u - 1] - v[k - 1]);

}

if(S[v[k - 1]] == '1'){

int u = min(r, k + 2 * K + 1);

ans = max(ans, v[u - 1] - v[k - 1]);

}

// 4. 後処理.

cout << ans << endl;

return 0;

}

[入力例]
5 1
00010

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

[入力例]
8 1
01100100

[出力例]
5

[入力例]
14 2
11101010110011

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

[入力例]
1 1
1

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

[入力例]
32 3
11100100000101101000110000000000

[出力例]
19

[入力例]

5 1

00010

[出力例]

※AtCoderテストケースより

[入力例]

8 1

01100100

[出力例]

[入力例]

14 2

11101010110011

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

32 3

11100100000101101000110000000000

[出力例]

■参照サイト
AtCoder Beginner Contest 124

2019年4月13日

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

C++の練習を兼ねて, AtCoder Grand Contest 007 の問題A (Shik and Stone) ～問題B (Construct Sequences) を解いてみた.

■感想.
1. 解答を見る前に, 解答まで辿り着いたので良かったと思う.
2. 問題B は, 条件を満たす数列の例が見つかったので, 何とか解答に辿り着けた.

本家のサイトAtCoder Grand Contest 007 Editorialをご覧下さい.

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

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

int main() {
    
    // 1. 入力情報取得.
    int H, W;
    cin >> H >> W;
    char a[H][W];
    int sharp = 0;
    for(int i = 0; i < H; i++){
        string s;
        cin >> s;
        for(int j = 0; j < W; j++){
            a[i][j] = s[j];
            if(s[j] == '#') sharp++;
        }
    }
    // for(int i = 0; i < H; i++){
    //     for(int j = 0; j < W; j++) cout << a[i][j] << " ";
    //     cout << endl;
    // }
    // cout << sharp << endl;
    
    // 2. 移動する過程で, 駒が常に右または下に動いていた可能性があるかを判定.
    // 2-1. '#' の 個数が, H + W - 1 個で無ければ, "Impossible" のはず.
    if(sharp != H + W - 1){
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 2-2. '#' の マス で, 下方向 or 右方向 で, '#' でないマスが, 一つでもあれば, "Impossible" のはず.
    bool ok = true;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            // 右下隅のマスに到達したら, break;
            if(i == H - 1 && j == W - 1) break;
            // 下方向 かつ 右方向 ともに '#' の マスが見当たらない場合.
            if(a[i][j] == '#'){
                if((i < H - 1 && a[i + 1][j] != '#') && (i < W - 1 && a[i][j + 1] != '#')){
                    // cout << "down: a[" << i << "][" << j << "]=" << a[i][j] << endl;
                    ok = false;
                    break;
                }
            }
        }
        if(!ok) break;
    }
    
    // 3. 出力.
    if(ok) cout << "Possible" << endl;
    else   cout << "Impossible" << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int H, W;

cin >> H >> W;

char a[H][W];

int sharp = 0;

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

string s;

cin >> s;

for(int j = 0; j < W; j++){

a[i][j] = s[j];

if(s[j] == '#') sharp++;

}

// for(int i = 0; i < H; i++){

// for(int j = 0; j < W; j++) cout << a[i][j] << " ";

// cout << endl;

// }

// cout << sharp << endl;

// 2. 移動する過程で, 駒が常に右または下に動いていた可能性があるかを判定.

// 2-1. '#' の個数が, H + W - 1 個で無ければ, "Impossible" のはず.

if(sharp != H + W - 1){

cout << "Impossible" << endl;

return 0;

}

// 2-2. '#' のマスで, 下方向 or 右方向で, '#' でないマスが, 一つでもあれば, "Impossible" のはず.

bool ok = true;

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

for(int j = 0; j < W; j++){

// 右下隅のマスに到達したら, break;

if(i == H - 1 && j == W - 1) break;

// 下方向かつ右方向ともに '#' のマスが見当たらない場合.

if(a[i][j] == '#'){

if((i < H - 1 && a[i + 1][j] != '#') && (i < W - 1 && a[i][j + 1] != '#')){

// cout << "down: a[" << i << "][" << j << "]=" << a[i][j] << endl;

ok = false;

break;

}

if(!ok) break;

}

// 3. 出力.

if(ok) cout << "Possible" << endl;

else cout << "Impossible" << endl;

return 0;

}

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

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

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    LL p[N + 1];
    p[0] = 0;
    for(LL i = 1; i < N + 1; i++) cin >> p[i];
    
    // 2. 整数列 a, b を 構築.
    // [イメージ(方針)]
    // ex.
    // N = 3 の 場合(上段: a1, a2, a3, 下段: b1, b2, b3).
    // 10 20 30
    // 30 20 10
    // ↓
    // (p1, p2, p3) = (2, 1, 3) などとする.
    // ↓
    // 10 20 + 1 30
    // 30 20     10
    // ↓
    // 10 + 2 20 + 1 30
    // 30     20     10
    // ↓
    // 10 + 2 20 + 1 30 + 3
    // 30     20     10
    // ↓
    // 12 21 33
    // 30 20 10
    // 
    // 2-1. 整数列 a, b の ベース を構築.
    // -> ai + bi が 全て等しい状態.
    LL a[20001], b[20001];
    a[0] = b[0] = 0;
    for(LL i = 1; i < 20001; i++) a[i] = 25000 * i;
    for(LL i = 1; i < 20001; i++) b[i] = a[20001 - i];
    
    // 2-2. 順列情報から, 順列情報 の ソート順 となるように変更.
    for(LL i = 1; i < N + 1; i++) a[p[i]] += i;
    
    // 3. 出力 ～ 後処理.
    for(LL i = 1; i < N + 1; i++) cout << a[i] << " ";
    cout << endl;
    for(LL i = 1; i < N + 1; i++) cout << b[i] << " ";
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

LL p[N + 1];

p[0] = 0;

for(LL i = 1; i < N + 1; i++) cin >> p[i];

// 2. 整数列 a, b を構築.

// [イメージ(方針)]

// ex.

// N = 3 の場合(上段: a1, a2, a3, 下段: b1, b2, b3).

// 10 20 30

// 30 20 10

// ↓

// (p1, p2, p3) = (2, 1, 3) などとする.

// ↓

// 10 20 + 1 30

// 30 20 10

// ↓

// 10 + 2 20 + 1 30

// 30 20 10

// ↓

// 10 + 2 20 + 1 30 + 3

// 30 20 10

// ↓

// 12 21 33

// 30 20 10

// 2-1. 整数列 a, b のベースを構築.

// -> ai + bi が全て等しい状態.

LL a[20001], b[20001];

a[0] = b[0] = 0;

for(LL i = 1; i < 20001; i++) a[i] = 25000 * i;

for(LL i = 1; i < 20001; i++) b[i] = a[20001 - i];

// 2-2. 順列情報から, 順列情報のソート順となるように変更.

for(LL i = 1; i < N + 1; i++) a[p[i]] += i;

// 3. 出力～後処理.

for(LL i = 1; i < N + 1; i++) cout << a[i] << " ";

cout << endl;

for(LL i = 1; i < N + 1; i++) cout << b[i] << " ";

return 0;

}

[入力例]
2
1 2

[出力例]
25001 50002 
500000000 499975000 
※AtCoderテストケースより

[入力例]
3
3 2 1

[出力例]
25003 50002 75001 
500000000 499975000 499950000 
※AtCoderテストケースより

[入力例]
3
2 3 1

[出力例]
25003 50001 75002 
500000000 499975000 499950000 
※AtCoderテストケースより

[入力例]
5
3 5 1 2 4

[出力例]
25003 50004 75001 100005 125002 
500000000 499975000 499950000 499925000 499900000 

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

[出力例]
25005 50008 75002 100003 125004 150010 175006 200001 225007 250009 
500000000 499975000 499950000 499925000 499900000 499875000 499850000 499825000 499800000 499775000

[入力例]

1 2

[出力例]

25001 50002

500000000 499975000

※AtCoderテストケースより

[入力例]

3 2 1

[出力例]

25003 50002 75001

500000000 499975000 499950000

※AtCoderテストケースより

[入力例]

2 3 1

[出力例]

25003 50001 75002

500000000 499975000 499950000

※AtCoderテストケースより

[入力例]

3 5 1 2 4

[出力例]

25003 50004 75001 100005 125002

500000000 499975000 499950000 499925000 499900000

[入力例]

8 3 4 5 1 7 9 2 10 6

[出力例]

25005 50008 75002 100003 125004 150010 175006 200001 225007 250009

500000000 499975000 499950000 499925000 499900000 499875000 499850000 499825000 499800000 499775000

■参照サイト
AtCoder Grand Contest 007

2019年4月11日

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

C++の練習を兼ねて, AtCoder Grand Contest 006 の問題A (Prefix and Suffix) ～問題B (Median Pyramid Easy) を解いてみた.

■感想.
1. 解答を見る前に, 何とか解答まで辿り着いたので良かったと思う.
2. 問題B は, 最初, X = N, N – 1, N + 1 に限定されると方針を立てて解いたが, WAとなって, 改めて調べたところ, X = 1, 2 * N – 1 以外の X で, 条件を満たす配置が見つかったので, 何とか解答に辿り着けた.

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

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

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    string s, t;
    cin >> N >> s >> t;
    
    // 2. 条件を満たす最も短い文字列を作成.
    int ans;
    for(int i = 0; i < N + 1; i++){
        string merge = s.substr(0, i) + t;
        ans = merge.size();
        string f = merge.substr(0, N);
        string e = merge.substr(ans - N, N);
        // cout << "s=" << s << " f=" << f << " t=" << t << " e=" << e << endl;
        if(f == s && e == t) break;
    }
    
    // 3. 出力.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N;

string s, t;

cin >> N >> s >> t;

// 2. 条件を満たす最も短い文字列を作成.

int ans;

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

string merge = s.substr(0, i) + t;

ans = merge.size();

string f = merge.substr(0, N);

string e = merge.substr(ans - N, N);

// cout << "s=" << s << " f=" << f << " t=" << t << " e=" << e << endl;

if(f == s && e == t) break;

}

// 3. 出力.

cout << ans << endl;

return 0;

}

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

#include <bits/stdc++.h>
using namespace std;
const string YES = "Yes";
const string NO  = "No";

int main() {
    
    // 1. 入力情報取得.
    int N, X;
    cin >> N >> X;
    
    // 2. N が 2 に等しい 場合.
    if(N == 2){
        if(X == 2){
            cout << YES << endl;
            for(int i = 1; i <= 3; i++) cout << i << endl;
        }
        if(X != 2) cout << NO << endl;
        return 0;
    }
    
    // 3. N が 3以上 の 場合.
    int baseSize = 2 * N - 1;
    if(N >= 3){
        // 3-1. X = N の 場合.
        if(X == N){
            cout << YES << endl;
            for(int i = 1; i <= baseSize; i++) cout << i << endl;
            return 0;
        }
        
        // 3-2. X = 2 ～ N - 1 の 場合.
        if(X > 1 && X < N){
            vector<int> v;
            for(int i = 1; i <= baseSize; i++) if(i < X - 1 || i > X + 2) v.push_back(i);
            // for(auto &p : v) cout << p << endl;
            int border = N - 2;
            cout << YES << endl;
            for(int i = 0; i < border - 1; i++) cout << v[i] << endl;
            cout << (X + 1) << endl;
            cout << (X - 1) << endl;
            cout << X << endl;
            cout << (X + 2) << endl;
            for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;
            return 0;
        }
        
        // 3-3. X = N + 1 ～ 2 * N - 2 の 場合.
        if(X > N && X < baseSize){
            vector<int> v;
            for(int i = 1; i <= baseSize; i++) if(i < X - 2 || i > X + 1) v.push_back(i);
            // for(auto &p : v) cout << p << endl;
            int border = N - 2;
            cout << YES << endl;
            for(int i = 0; i < border - 1; i++) cout << v[i] << endl;
            cout << (X - 1) << endl;
            cout << X << endl;
            cout << (X + 1) << endl;
            cout << (X - 2) << endl;
            for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;
            return 0;
        }
        
    }
    
    // 4. 出力 ～ 後処理.
    cout << NO << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const string YES = "Yes";

const string NO = "No";

int main() {

// 1. 入力情報取得.

int N, X;

cin >> N >> X;

// 2. N が 2 に等しい場合.

if(N == 2){

if(X == 2){

cout << YES << endl;

for(int i = 1; i <= 3; i++) cout << i << endl;

}

if(X != 2) cout << NO << endl;

return 0;

}

// 3. N が 3以上の場合.

int baseSize = 2 * N - 1;

if(N >= 3){

// 3-1. X = N の場合.

if(X == N){

cout << YES << endl;

for(int i = 1; i <= baseSize; i++) cout << i << endl;

return 0;

}

// 3-2. X = 2 ～ N - 1 の場合.

if(X > 1 && X < N){

vector<int> v;

for(int i = 1; i <= baseSize; i++) if(i < X - 1 || i > X + 2) v.push_back(i);

// for(auto &p : v) cout << p << endl;

int border = N - 2;

cout << YES << endl;

for(int i = 0; i < border - 1; i++) cout << v[i] << endl;

cout << (X + 1) << endl;

cout << (X - 1) << endl;

cout << X << endl;

cout << (X + 2) << endl;

for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;

return 0;

}

// 3-3. X = N + 1 ～ 2 * N - 2 の場合.

if(X > N && X < baseSize){

vector<int> v;

for(int i = 1; i <= baseSize; i++) if(i < X - 2 || i > X + 1) v.push_back(i);

// for(auto &p : v) cout << p << endl;

int border = N - 2;

cout << YES << endl;

for(int i = 0; i < border - 1; i++) cout << v[i] << endl;

cout << (X - 1) << endl;

cout << X << endl;

cout << (X + 1) << endl;

cout << (X - 2) << endl;

for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;

return 0;

}

// 4. 出力～後処理.

cout << NO << endl;

return 0;

}

[入力例]
4 4

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

[入力例]
2 1

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

[入力例]
2 2

[出力例]
Yes
1
2
3

[入力例]
3 2

[出力例]
Yes
3
1
2
4
5

[入力例]
3 4

[出力例]
Yes
3
4
5
2
1

[入力例]
5 2

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

[入力例]
5 8

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

[入力例]
6 3

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

[入力例]
11 2

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

[入力例]
11 20

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

[入力例]

4 4

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

Yes

[入力例]

3 2

[出力例]

Yes

[入力例]

3 4

[出力例]

Yes

[入力例]

5 2

[出力例]

Yes

[入力例]

5 8

[出力例]

Yes

[入力例]

6 3

[出力例]

Yes

[入力例]

11 2

[出力例]

Yes

[入力例]

11 20

[出力例]

Yes

■参照サイト
AtCoder Grand Contest 006

2019年4月7日

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

C++の練習を兼ねて, AtCoder Typical Contest 001 の問題A (A – 深さ優先探索) を解いてみた.

■感想.
1. 前回以前に確認した幅優先探索のソースを, 一部修正する形で対応した.

本家のサイトA – 深さ優先探索をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 3e5 + 1;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 深さ優先探索.
// https://ja.wikipedia.org/wiki/深さ優先探索
// 迷路を深さ優先探索する.
// ※dfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void dfs(int s){
    
    // 1. 空のスタック.
    deque<int> dq;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s を スタック dq に追加.
    dq.push_front(s);
    while(!dq.empty()){
        // 4. スタックから取り出す.
        int v = dq.front();
        dq.pop_front();
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            if((board[n] == '.' || board[n] == 'g') && n != s && memo[n] == 0) memo[n] = memo[v] + 1, dq.push_front(n);
            
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    cin >> R >> C;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
            // スタート地点, ゴール地点を設定.
            if(s[j] == 's') sx = j, sy = i;
            if(s[j] == 'g') gx = j, gy = i;
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    dfs(sy * C + sx);
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = memo[gy * C + gx];
    // cout << ans << endl;
    if(ans == 0) cout << "No" << endl;
    else         cout << "Yes" << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 3e5 + 1;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 深さ優先探索.

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

// 迷路を深さ優先探索する.

// ※dfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void dfs(int s){

// 1. 空のスタック.

deque<int> dq;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

// 3. 探索地点 s をスタック dq に追加.

dq.push_front(s);

while(!dq.empty()){

// 4. スタックから取り出す.

int v = dq.front();

dq.pop_front();

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

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % C , cy = v / C;

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

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

if((board[n] == '.' || board[n] == 'g') && n != s && memo[n] == 0) memo[n] = memo[v] + 1, dq.push_front(n);

}

return;

}

int main() {

// 1. 入力情報取得.

cin >> R >> C;

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

string s;

cin >> s;

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

board[i * C + j] = s[j];

// スタート地点, ゴール地点を設定.

if(s[j] == 's') sx = j, sy = i;

if(s[j] == 'g') gx = j, gy = i;

}

// 2. 探索を開始し, 探索距離を更新.

dfs(sy * C + sx);

// for(int i = 0; i < R; ++i){

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

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = memo[gy * C + gx];

// cout << ans << endl;

if(ans == 0) cout << "No" << endl;

else cout << "Yes" << endl;

return 0;

}

[入力例]
4 5
s####
....#
#####
#...g

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

[入力例]
4 4
...s
....
....
.g..

[出力例(debug版)]
9 8 1 0 
8 7 2 1 
7 6 3 2 
6 5 4 3 
5
Yes
※AtCoderテストケースより

[入力例]
10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 
0 0 0 0 0 0 0 0 0 10 
0 33 32 31 30 29 28 27 0 11 
0 34 33 0 0 0 0 26 0 12 
0 0 34 35 36 37 0 25 0 13 
0 0 0 0 0 38 0 24 0 14 
0 0 0 47 0 39 0 23 0 15 
0 0 0 46 0 40 0 22 0 16 
0 0 0 45 0 41 0 21 0 17 
0 46 45 44 43 42 0 20 19 18 
0
No
※AtCoderテストケースより

[入力例]
10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 
0 0 0 0 0 0 0 0 0 10 
0 33 32 31 30 29 28 27 0 11 
0 34 33 0 0 0 0 26 0 12 
0 0 34 35 36 37 0 25 0 13 
0 0 0 0 0 38 0 24 0 14 
50 49 0 47 0 39 0 23 0 15 
0 48 0 46 0 40 0 22 0 16 
0 47 0 45 0 41 0 21 0 17 
0 46 45 44 43 42 0 20 19 18 
50
Yes
※AtCoderテストケースより

[入力例]
1 10
s..####..g

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

[入力例]
16 12
s.##########
#.##......##
#.##.#.##.##
#....#....##
##.#########
##..########
###.########
###......###
###.####..##
###.##.....#
###.####.#.#
###.##.#.#.#
###.####.#.#
###.###..###
###.#..#..g#
###......###

[出力例(debug版)]
0 1 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 9 10 11 12 19 18 0 0 
0 3 0 0 8 0 12 0 0 17 0 0 
0 4 5 6 7 0 13 14 15 16 0 0 
0 0 6 0 0 0 0 0 0 0 0 0 
0 0 7 8 0 0 0 0 0 0 0 0 
0 0 0 9 0 0 0 0 0 0 0 0 
0 0 0 10 11 34 33 32 31 0 0 0 
0 0 0 11 0 0 0 0 30 31 0 0 
0 0 0 12 0 0 31 30 29 30 31 0 
0 0 0 13 0 0 0 0 28 0 32 0 
0 0 0 14 0 0 0 0 27 0 33 0 
0 0 0 15 0 0 0 0 26 0 34 0 
0 0 0 16 0 0 0 26 25 0 0 0 
0 0 0 17 0 21 22 0 24 25 26 0 
0 0 0 18 19 20 21 22 23 0 0 0 
26
Yes

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

[入力例]

4 5

s####

....#

#####

#...g

[出力例(debug版)]

0 0 0 0 0

1 2 3 4 0

0 0 0 0 0

※AtCoderテストケースより

[入力例]

4 4

...s

....

.g..

[出力例(debug版)]

9 8 1 0

8 7 2 1

7 6 3 2

6 5 4 3

Yes

※AtCoderテストケースより

[入力例]

10 10

s.........

#########.

#.......#.

#..####.#.

##....#.#.

#####.#.#.

g.#.#.#.#.

#.#.#.#.#.

###.#.#.#.

#.....#...

[出力例(debug版)]

0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 10

0 33 32 31 30 29 28 27 0 11

0 34 33 0 0 0 0 26 0 12

0 0 34 35 36 37 0 25 0 13

0 0 0 0 0 38 0 24 0 14

0 0 0 47 0 39 0 23 0 15

0 0 0 46 0 40 0 22 0 16

0 0 0 45 0 41 0 21 0 17

0 46 45 44 43 42 0 20 19 18

※AtCoderテストケースより

[入力例]

10 10

s.........

#########.

#.......#.

#..####.#.

##....#.#.

#####.#.#.

g.#.#.#.#.

#.#.#.#.#.

#.....#...

[出力例(debug版)]

0 1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0 10

0 33 32 31 30 29 28 27 0 11

0 34 33 0 0 0 0 26 0 12

0 0 34 35 36 37 0 25 0 13

0 0 0 0 0 38 0 24 0 14

50 49 0 47 0 39 0 23 0 15

0 48 0 46 0 40 0 22 0 16

0 47 0 45 0 41 0 21 0 17

0 46 45 44 43 42 0 20 19 18

Yes

※AtCoderテストケースより

[入力例]

1 10

s..####..g

[出力例(debug版)]

0 1 2 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

16 12

s.##########

#.##......##

#.##.#.##.##

#....#....##

##.#########

##..########

###.########

###......###

###.####..##

###.##.....#

###.####.#.#

###.##.#.#.#

###.####.#.#

###.###..###

###.#..#..g#

###......###

[出力例(debug版)]

0 1 0 0 0 0 0 0 0 0 0 0

0 2 0 0 9 10 11 12 19 18 0 0

0 3 0 0 8 0 12 0 0 17 0 0

0 4 5 6 7 0 13 14 15 16 0 0

0 0 6 0 0 0 0 0 0 0 0 0

0 0 7 8 0 0 0 0 0 0 0 0

0 0 0 9 0 0 0 0 0 0 0 0

0 0 0 10 11 34 33 32 31 0 0 0

0 0 0 11 0 0 0 0 30 31 0 0

0 0 0 12 0 0 31 30 29 30 31 0

0 0 0 13 0 0 0 0 28 0 32 0

0 0 0 14 0 0 0 0 27 0 33 0

0 0 0 15 0 0 0 0 26 0 34 0

0 0 0 16 0 0 0 26 25 0 0 0

0 0 0 17 0 21 22 0 24 25 26 0

0 0 0 18 19 20 21 22 23 0 0 0

Yes

■参照サイト
AtCoder Typical Contest 001

2019年4月1日

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

C++の練習を兼ねて, AtCoder Grand Contest 003 の問題A (Wanna go back home) ～問題C (BBuBBBlesort!) を解いてみた.

■感想.
1. 問題A, C は, 解答を見る前に, 何とか解答まで辿り着いたので良かったと思う.
2. 問題B は, 一見とっつきやすそうに見えたが, 知識不足で解けなかったため, 解答を見直して, 解きなおした.

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

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

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

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 各方角の出現数をカウント.
    int n = 0, w = 0, s = 0, e = 0;
    for(int i = 0; i < S.size(); i++){
        char c = S[i];
        if(c == 'N') n++;
        if(c == 'W') w++;
        if(c == 'S') s++;
        if(c == 'E') e++;
    }
    
    // 3. 出力.
    string ans = "Yes";
    if(n + s > 0 && n * s == 0) ans = "No";
    if(w + e > 0 && w * e == 0) ans = "No";
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 各方角の出現数をカウント.

int n = 0, w = 0, s = 0, e = 0;

for(int i = 0; i < S.size(); i++){

char c = S[i];

if(c == 'N') n++;

if(c == 'W') w++;

if(c == 'S') s++;

if(c == 'E') e++;

}

// 3. 出力.

string ans = "Yes";

if(n + s > 0 && n * s == 0) ans = "No";

if(w + e > 0 && w * e == 0) ans = "No";

cout << ans << endl;

return 0;

}

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

// 解き直し.
// AtCoderGrandContest003解説.
// http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    LL A[N + 1];
    for(int i = 0; i < N; i++) cin >> A[i];
    // 番兵設定.
    A[N] = 0;
    
    // 2. 解説通り.
    // A[i] = 0 の タイミングで, 区切って計算.
    LL ans = 0, counter = 0;
    for(int i = 0; i < N + 1; i++){
        if(A[i] != 0) counter += A[i];
        else          ans += counter / 2, counter = 0;
    }
    
    // 3. 出力.
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoderGrandContest003解説.

// http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

LL A[N + 1];

for(int i = 0; i < N; i++) cin >> A[i];

// 番兵設定.

A[N] = 0;

// 2. 解説通り.

// A[i] = 0 のタイミングで, 区切って計算.

LL ans = 0, counter = 0;

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

if(A[i] != 0) counter += A[i];

else ans += counter / 2, counter = 0;

}

// 3. 出力.

cout << ans << endl;

return 0;

}

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

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

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    LL A[N], B[N];
    for(int i = 0; i < N; i++){
        LL a;
        cin >> a;
        A[i] = a;
        B[i] = a; // 後で, 比較するための配列, sortしない.
    }
    
    // 2. 昇順sort.
    sort(A, A + N);
    
    // 3. sort済み数列の偶奇情報を保存.
    // mo: i が 奇数で保存. me: i が 偶数で保存.
    map<LL, int> mo, me;
    for(int i = 0; i < N; i++){
        if(i % 2 == 1) mo[A[i]]++;
        else           me[A[i]]++;
    }
    
    // 4. 操作２で, 昇順 sort 出来るパターンが, 限定されているように見える.
    // ex. 
    // 1 2 3 5 4 -> 操作２を何回使っても, 1 2 3 4 5 とならない.
    // 3 4 5 2 1 -> 3 2 5 4 1 -> 3 2 1 4 5 -> 1 2 3 4 5
    // -> 操作２だけ使って, 1 2 3 4 5 と出来る.
    // 数列 の 偶数番目, 奇数番目 について, 
    // 昇順 sort 前後 で,  同じ内容になっている必要があるように見える.
    LL counter = 0;
    for(int i = 0; i < N; i++){
        if(i % 2 == 0 && mo[B[i]] > 0) counter++;
        if(i % 2 == 1 && me[B[i]] > 0) counter++;
    }
    
    // 5. 出力.
    LL ans = counter / 2;
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

LL A[N], B[N];

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

LL a;

cin >> a;

A[i] = a;

B[i] = a; // 後で, 比較するための配列, sortしない.

}

// 2. 昇順sort.

sort(A, A + N);

// 3. sort済み数列の偶奇情報を保存.

// mo: i が奇数で保存. me: i が偶数で保存.

map<LL, int> mo, me;

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

if(i % 2 == 1) mo[A[i]]++;

else me[A[i]]++;

}

// 4. 操作２で, 昇順 sort 出来るパターンが, 限定されているように見える.

// ex.

// 1 2 3 5 4 -> 操作２を何回使っても, 1 2 3 4 5 とならない.

// 3 4 5 2 1 -> 3 2 5 4 1 -> 3 2 1 4 5 -> 1 2 3 4 5

// -> 操作２だけ使って, 1 2 3 4 5 と出来る.

// 数列の偶数番目, 奇数番目について,

// 昇順 sort 前後で, 同じ内容になっている必要があるように見える.

LL counter = 0;

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

if(i % 2 == 0 && mo[B[i]] > 0) counter++;

if(i % 2 == 1 && me[B[i]] > 0) counter++;

}

// 5. 出力.

LL ans = counter / 2;

cout << ans << endl;

return 0;

}

[入力例]
4
2
4
3
1

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

[入力例]
5
10
8
5
3
2

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

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

[出力例]
1

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

[出力例]
3

※操作例(操作１は, 3回と分かる)
1 2 4 3 5 6 10 9 8 7
   ↓操作１(4 3 -> 3 4)
1 2 3 4 5 6 10 9 8 7
   ↓操作１(10 9 -> 9 10)
1 2 3 4 5 6 9 10 8 7
   ↓操作１(8 7 -> 7 8)
1 2 3 4 5 6 9 10 7 8
   ↓操作２(9 10 7 -> 7 10 9)
1 2 3 4 5 6 7 10 9 8
   ↓操作２(10 9 8 -> 8 9 10)
1 2 3 4 5 6 7 8 9 10

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

※操作例(操作１は, 3回と分かる)

1 2 4 3 5 6 10 9 8 7

↓操作１(4 3 -> 3 4)

1 2 3 4 5 6 10 9 8 7

↓操作１(10 9 -> 9 10)

1 2 3 4 5 6 9 10 8 7

↓操作１(8 7 -> 7 8)

1 2 3 4 5 6 9 10 7 8

↓操作２(9 10 7 -> 7 10 9)

1 2 3 4 5 6 7 10 9 8

↓操作２(10 9 8 -> 8 9 10)

1 2 3 4 5 6 7 8 9 10

■参照サイト
AtCoder Grand Contest 003

2019年3月31日2019年3月31日

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

C++の練習を兼ねて, AtCoder Typical Contest 002 の問題A (A – 幅優先探索) を解いてみた.

■感想.
1. 幅優先探索に慣れるために, コーディングしたが, ACを取れるまで苦労した.
具体的には, 以下のような原因で, 探索イメージと実際の探索状況がズレてしまっていた.
※探索開始地点, 探索終了地点の index が 1ずつズレていた点, 探索距離の更新方法がおかしかった点.

2. 未使用の変数, コメント誤りなどがあったので, 前回の投稿から, 一部差し替えた.

本家のサイトA – 幅優先探索をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 2601;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int v = q.front();
        q.pop();
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    
    cin >> R >> C >> sy >> sx >> gy >> gx;
    sy--, sx--, gy--, gx--;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    bfs(sy * C + sx);
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = memo[gy * C + gx];
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 2601;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 幅優先探索.

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

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % C , cy = v / C;

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

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

cin >> R >> C >> sy >> sx >> gy >> gx;

sy--, sx--, gy--, gx--;

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

string s;

cin >> s;

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

board[i * C + j] = s[j];

}

// 2. 探索を開始し, 探索距離を更新.

bfs(sy * C + sx);

// for(int i = 0; i < R; ++i){

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

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = memo[gy * C + gx];

cout << ans << endl;

return 0;

}

[入力例]
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

[出力例(debug版)]
0 0 0 0 0 0 0 0 
0 0 1 2 3 4 5 0 
0 1 0 0 0 0 0 0 
0 2 3 0 11 10 11 0 
0 3 4 0 0 9 10 0 
0 0 5 6 7 8 9 0 
0 0 0 0 0 0 0 0 
11
※AtCoderテストケースより

[入力例]
5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########

[出力例(debug版)]
0 0 0 0 0 0 0 0 
0 0 0 10 9 8 9 0 
0 1 0 0 0 7 8 0 
0 2 3 4 5 6 7 0 
0 0 0 0 0 0 0 0 
10
※AtCoderテストケースより

[入力例]
16 12
1 1
15 11
..##########
#.##......##
#.##.#.##.##
#....#....##
##.#########
##..########
###.########
###......###
###.####..##
###.##.....#
###.####.#.#
###.##.#.#.#
###.####.#.#
###.###..###
###.#..#...#
###......###

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

[入力例]

7 8

2 2

4 5

########

#......#

#.######

#..#...#

#..##..#

##.....#

########

[出力例(debug版)]

0 0 0 0 0 0 0 0

0 0 1 2 3 4 5 0

0 1 0 0 0 0 0 0

0 2 3 0 11 10 11 0

0 3 4 0 0 9 10 0

0 0 5 6 7 8 9 0

0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

5 8

2 2

2 4

########

#.#....#

#.###..#

#......#

########

[出力例(debug版)]

0 0 0 0 0 0 0 0

0 0 0 10 9 8 9 0

0 1 0 0 0 7 8 0

0 2 3 4 5 6 7 0

0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

16 12

1 1

15 11

..##########

#.##......##

#.##.#.##.##

#....#....##

##.#########

##..########

###.########

###......###

###.####..##

###.##.....#

###.####.#.#

###.##.#.#.#

###.####.#.#

###.###..###

###.#..#...#

###......###

[出力例(debug版)]

0 1 0 0 0 0 0 0 0 0 0 0

0 2 0 0 9 10 11 12 13 14 0 0

0 3 0 0 8 0 12 0 0 15 0 0

0 4 5 6 7 0 13 14 15 16 0 0

0 0 6 0 0 0 0 0 0 0 0 0

0 0 7 8 0 0 0 0 0 0 0 0

0 0 0 9 0 0 0 0 0 0 0 0

0 0 0 10 11 12 13 14 15 0 0 0

0 0 0 11 0 0 0 0 16 17 0 0

0 0 0 12 0 0 19 18 17 18 19 0

0 0 0 13 0 0 0 0 18 0 20 0

0 0 0 14 0 0 0 0 19 0 21 0

0 0 0 15 0 0 0 0 20 0 22 0

0 0 0 16 0 0 0 22 21 0 0 0

0 0 0 17 0 21 22 0 22 23 24 0

0 0 0 18 19 20 21 22 23 0 0 0

■参照サイト
AtCoder Typical Contest 002

2019年3月21日

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

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

■感想.
1. 解説の方針と異なっているように見えるが, 計算量を落とすようには書けたと思うので, 及第点取れたと思う.

本家のサイトABC 090/ARC 091 解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(LL i=(a); i<=(b); ++i)

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    
    // 2. (a, b) の 候補 を カウント.
    // ex.
    // b = K + 1: (N + 1) / (K + 1)個
    // b = K + 2: (N + 2) / (K + 2)個, (N + 1) / (K + 2)個
    // b = K + 3: (N + 3) / (K + 3)個, (N + 2) / (K + 3)個, (N + 1) / (K + 3)個
    // ...
    // b = K + i: (N + i) / (K + i)個, (N + i - 1) / (K + i)個, ...,  (N + 1) / (K + i)個
    // ...
    // b = K + (N - K): (2 * N - K) / N個, (2 * N - K - 1) / N個, ...,  (N + 1) / N個 => 計(N - K)通り
    LL ans = 0;
    FOR(b, K + 1, N){
        // 2-1. 上限, 下限 を 計算.
        // ex.
        // b = K + i なら, 
        // 上限: (N + i) / (K + i)個
        // 下限: (N + 1) / (K + i)個
        LL u = (N - K + b) / b, l = (N + 1) / b;
        // cout << "b=" << b << " u=" << u  << " l=" << l << endl;
        
        // 2-2. 各区間について集計.
        // (N - K + b) ～ u * b:       u * ((N - K + b) - u * b + 1)                 =>           ...個(★①)
        // u * b - 1 ～ (u - 1) * b:       (u - 1) * ((u * b - 1) - (u - 1) * b + 1) =>   (u - 1) * b個
        // ...
        // (l + 2) * b - 1 ～ (l + 1) * b: (l + 1) * (((l + 2) * b - 1) - (l + 1) * b + 1) => (l * b)個
        // (l + 1) * b - 1 ～ (N + 1):     l * (((l + 1) * b - 1) - (N + 1) + 1) 個  =>           ...個(★②)
        
        // 下限 ～ 上限 の 場合.
        FOR(v, l, u){
            LL diff = min(N - K + b, (v + 1) * b - 1); // 上限に近い場合に注意(★①).
            diff -= max(N + 1, v * b); // 下限に近い場合に注意(★②).
            ans += v * (diff + 1);
            // cout << "b=" << b << " l=" << l << " u=" << u << " v=" << v << " diff=" << diff << " ans=" << ans << endl;
        }
    }
    
    // 3. 出力 ～ 後処理.
    // K = 0 の 場合は, a = 0 の ケース を 除外する必要がある.
    if(K == 0) ans -= N;
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

// 2. (a, b) の候補をカウント.

// ex.

// b = K + 1: (N + 1) / (K + 1)個

// b = K + 2: (N + 2) / (K + 2)個, (N + 1) / (K + 2)個

// b = K + 3: (N + 3) / (K + 3)個, (N + 2) / (K + 3)個, (N + 1) / (K + 3)個

// ...

// b = K + i: (N + i) / (K + i)個, (N + i - 1) / (K + i)個, ..., (N + 1) / (K + i)個

// ...

// b = K + (N - K): (2 * N - K) / N個, (2 * N - K - 1) / N個, ..., (N + 1) / N個 => 計(N - K)通り

LL ans = 0;

FOR(b, K + 1, N){

// 2-1. 上限, 下限を計算.

// ex.

// b = K + i なら,

// 上限: (N + i) / (K + i)個

// 下限: (N + 1) / (K + i)個

LL u = (N - K + b) / b, l = (N + 1) / b;

// cout << "b=" << b << " u=" << u << " l=" << l << endl;

// 2-2. 各区間について集計.

// (N - K + b) ～ u * b: u * ((N - K + b) - u * b + 1) => ...個(★①)

// u * b - 1 ～ (u - 1) * b: (u - 1) * ((u * b - 1) - (u - 1) * b + 1) => (u - 1) * b個

// ...

// (l + 2) * b - 1 ～ (l + 1) * b: (l + 1) * (((l + 2) * b - 1) - (l + 1) * b + 1) => (l * b)個

// (l + 1) * b - 1 ～ (N + 1): l * (((l + 1) * b - 1) - (N + 1) + 1) 個 => ...個(★②)

// 下限～上限の場合.

FOR(v, l, u){

LL diff = min(N - K + b, (v + 1) * b - 1); // 上限に近い場合に注意(★①).

diff -= max(N + 1, v * b); // 下限に近い場合に注意(★②).

ans += v * (diff + 1);

// cout << "b=" << b << " l=" << l << " u=" << u << " v=" << v << " diff=" << diff << " ans=" << ans << endl;

}

// 3. 出力～後処理.

// K = 0 の場合は, a = 0 のケースを除外する必要がある.

if(K == 0) ans -= N;

cout << ans << endl;

return 0;

}

[入力例]
5 2

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

[入力例]
10 0

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


[入力例]
31415 9265

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

[入力例]
100000 12345

[出力例]
5746887726

[入力例]
123456 54321

[出力例]
2444729736

[入力例]
654321 123456

[出力例]
190231592490

[入力例]

5 2

[出力例]

※AtCoderテストケースより

[入力例]

10 0

[出力例]

100

※AtCoderテストケースより

[入力例]

31415 9265

[出力例]

287927211

※AtCoderテストケースより

[入力例]

100000 12345

[出力例]

5746887726

[入力例]

123456 54321

[出力例]

2444729736

[入力例]

654321 123456

[出力例]

190231592490

■参照サイト
AtCoder Beginner Contest 090

2019年3月20日2019年3月20日

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

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

■感想.
1. 問題D は, DPを使うと思って解答しようとしたが, 方針がまとまらず, 解説を見て, 解き直したものである.
※なお, 問題C は, 難しすぎたので, 正解者のソースを勉強する方針に切り替え, 自力での解答は放棄している.

本家のサイトABC 104 Editorialをご覧下さい.

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

// 解き直し.
// ABC 104 Editorial
// https://img.atcoder.jp/abc104/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 動的計画法(DP)の適用(解説通り).
    LL l = S.size();
    LL dp[l + 1][4] = {};
    dp[l][3] = 1;
    dp[l][2] = 0, dp[l][1] = 0, dp[l][0] = 0;
    for(int i = l - 1; i >= 0; i--){
        char c = S[i];
        for(int j = 3; j >= 0; j--){
            if(j == 3){
                if(c == '?') dp[i][j] = 3 * dp[i + 1][j], dp[i][j] %= MOD;
                else         dp[i][j] = 1 * dp[i + 1][j], dp[i][j] %= MOD;
            }
            if(j < 3){
                if(c == '?'){
                    dp[i][j] = 3 * dp[i + 1][j];
                    dp[i][j] %= MOD;
                    dp[i][j] += 1 * dp[i + 1][j + 1];
                    dp[i][j] %= MOD;
                }else{
                    string ABC = "ABC";
                    dp[i][j] = 1 * dp[i + 1][j];
                    dp[i][j] %= MOD;
                    if(c == ABC.substr(j, 1)[0]) dp[i][j] += 1 * dp[i + 1][j + 1], dp[i][j] %= MOD;
                }
            }
        }
    }

    // 3. 出力 ～ 後処理.
    cout << dp[0][0] << endl;
    return 0;
    
}

// 解き直し.

// ABC 104 Editorial

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 動的計画法(DP)の適用(解説通り).

LL l = S.size();

LL dp[l + 1][4] = {};

dp[l][3] = 1;

dp[l][2] = 0, dp[l][1] = 0, dp[l][0] = 0;

for(int i = l - 1; i >= 0; i--){

char c = S[i];

for(int j = 3; j >= 0; j--){

if(j == 3){

if(c == '?') dp[i][j] = 3 * dp[i + 1][j], dp[i][j] %= MOD;

else dp[i][j] = 1 * dp[i + 1][j], dp[i][j] %= MOD;

}

if(j < 3){

if(c == '?'){

dp[i][j] = 3 * dp[i + 1][j];

dp[i][j] %= MOD;

dp[i][j] += 1 * dp[i + 1][j + 1];

dp[i][j] %= MOD;

}else{

string ABC = "ABC";

dp[i][j] = 1 * dp[i + 1][j];

dp[i][j] %= MOD;

if(c == ABC.substr(j, 1)[0]) dp[i][j] += 1 * dp[i + 1][j + 1], dp[i][j] %= MOD;

}

// 3. 出力～後処理.

cout << dp[0][0] << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 104

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題A (A – Frog 1) ～ 問題C (C – Vacation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 125 の 問題C (C – GCD on Blackboard) ～ 問題D (D – Flipping Signs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 124 の 問題C (Coloring Colorfully) ～ 問題D (Handstand) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 007 の 問題A (Shik and Stone) ～ 問題B (Construct Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 006 の 問題A (Prefix and Suffix) ～ 問題B (Median Pyramid Easy) を解いてみた.

C++の練習を兼ねて, AtCoder Typical Contest 001 の 問題A (A – 深さ優先探索) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 003 の 問題A (Wanna go back home) ～ 問題C (BBuBBBlesort!) を解いてみた.

C++の練習を兼ねて, AtCoder Typical Contest 002 の 問題A (A – 幅優先探索) を解いてみた.

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

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

C++の練習を兼ねて, Educational DP Contest / DP まとめコンテストの問題A (A – Frog 1) ～問題C (C – Vacation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 125 の問題C (C – GCD on Blackboard) ～問題D (D – Flipping Signs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 124 の問題C (Coloring Colorfully) ～問題D (Handstand) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 007 の問題A (Shik and Stone) ～問題B (Construct Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 006 の問題A (Prefix and Suffix) ～問題B (Median Pyramid Easy) を解いてみた.

C++の練習を兼ねて, AtCoder Typical Contest 001 の問題A (A – 深さ優先探索) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 003 の問題A (Wanna go back home) ～問題C (BBuBBBlesort!) を解いてみた.

C++の練習を兼ねて, AtCoder Typical Contest 002 の問題A (A – 幅優先探索) を解いてみた.

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

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