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

C++の練習を兼ねて, AtCoder Beginner Contest 043 の問題D（アンバランス / Unbalanced) を解いてみた.

■感想.
1. とりあえず, 解説見ずに解けたので良かったと思う.
2. 問題D は, 過半数の解釈に時間かかったように思う, ソース上のコメント通りであるが,
2パターンに集約できることに気付いたので, 解答に到達できた.
※なお, WA版は, パターン① しか考慮出来てなかったことが原因と思われる.

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

■C++版プログラム(問題D／WA版, 1_08, 1_09, 1_10, 2_18, 2_19, 2_20 で, Wrong Answer).

#include <bits/stdc++.h>

using namespace std;

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

int main() {

    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. アンバランスな (連続する) 部分文字列が存在するか判定.
    // 1_08, 1_09, 1_10, 2_18, 2_19, 2_20 で, error.
    // -> 以下の反例がある.
    // 文字列: 'aba' は, アンバランスな筈.
    int l = S.size();
    char bef = S[0];
    int ans[2] = {-1, -1};
    FOR(i, 1, l) {
        char cur = S[i];
        if(bef == cur && ans[0] == -1) {
            ans[0] = i;
            ans[1] = i + 1;
            break;
        }
        bef = cur;
    }

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. アンバランスな (連続する) 部分文字列が存在するか判定.

// 1_08, 1_09, 1_10, 2_18, 2_19, 2_20 で, error.

// -> 以下の反例がある.

// 文字列: 'aba' は, アンバランスな筈.

int l = S.size();

char bef = S[0];

int ans[2] = {-1, -1};

FOR(i, 1, l) {

char cur = S[i];

if(bef == cur && ans[0] == -1) {

ans[0] = i;

ans[1] = i + 1;

break;

}

bef = cur;

}

// 3. 出力～後処理.

cout << ans[0] << " " << ans[1] << endl;

return 0;

}

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. アンバランスな (連続する) 部分文字列が存在するか判定.
    // 1_08, 1_09, 1_10, 2_18, 2_19, 2_20 で, error.
    // -> 以下の反例がある.
    // 文字列: 'aba' は, アンバランスなはず.
    // 
    // ex.
    // アンバランスな文字列とは？
    // パターン①: 'aa'    -> 'a' が,  100% なので, 過半数と分かる.
    // パターン②: 'aba'   -> 'a' が, 約66% なので, 過半数と分かる.
    // パターン③: 'abbaa' -> 'a' が,   60% なので, 過半数と分かる.
    // -> 但し, パターン③ は, 文字列 'aa' を抽出できるので, パターン① に集約されるはず.
    int l = S.size();
    char bef_2 = S[0]; // 2文字前.
    char bef_1 = S[1]; // 1文字前.
    int ans[2] = {-1, -1};
    
    // 2-1. 1, 2文字目をチェックしておく.
    if(S[0] == S[1]) {
        ans[0] = 1;
        ans[1] = 2;
    }
    
    // 2-2. 3文字目以降もチェックする.
    FOR(i, 2, l) {
        char cur = S[i];
        if(ans[0] != -1) break;
        // 文字が連続しているかチェック(パターン①).
        if(bef_1 == cur && ans[0] == -1) {
            ans[0] = i;
            ans[1] = i + 1;
            break;
        }
        // 文字が1文字空けて再度出現しているかチェック(パターン②).
        if(bef_2 == cur && ans[0] == -1) {
            ans[0] = i - 1;
            ans[1] = i + 1;
            break;
        }
        bef_2 = bef_1;
        bef_1 = cur;
    }

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. アンバランスな (連続する) 部分文字列が存在するか判定.

// 1_08, 1_09, 1_10, 2_18, 2_19, 2_20 で, error.

// -> 以下の反例がある.

// 文字列: 'aba' は, アンバランスなはず.

// ex.

// アンバランスな文字列とは？

// パターン①: 'aa' -> 'a' が, 100% なので, 過半数と分かる.

// パターン②: 'aba' -> 'a' が, 約66% なので, 過半数と分かる.

// パターン③: 'abbaa' -> 'a' が, 60% なので, 過半数と分かる.

// -> 但し, パターン③ は, 文字列 'aa' を抽出できるので, パターン① に集約されるはず.

int l = S.size();

char bef_2 = S[0]; // 2文字前.

char bef_1 = S[1]; // 1文字前.

int ans[2] = {-1, -1};

// 2-1. 1, 2文字目をチェックしておく.

if(S[0] == S[1]) {

ans[0] = 1;

ans[1] = 2;

}

// 2-2. 3文字目以降もチェックする.

FOR(i, 2, l) {

char cur = S[i];

if(ans[0] != -1) break;

// 文字が連続しているかチェック(パターン①).

if(bef_1 == cur && ans[0] == -1) {

ans[0] = i;

ans[1] = i + 1;

break;

}

// 文字が1文字空けて再度出現しているかチェック(パターン②).

if(bef_2 == cur && ans[0] == -1) {

ans[0] = i - 1;

ans[1] = i + 1;

break;

}

bef_2 = bef_1;

bef_1 = cur;

}

// 3. 出力～後処理.

cout << ans[0] << " " << ans[1] << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 043

C++の練習を兼ねて, AtCoder Beginner Contest 043 の 問題D（アンバランス / Unbalanced) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 043 の問題D（アンバランス / Unbalanced) を解いてみた.

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