【AtCoder】ABC 349 B - Commencement | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 89

問題概要

英小文字からなる文字列が次の条件を満たすとき、その文字列は「良い文字列」であるとする。英小文字からなる文字列 $S$ が与えられるので、 $S$ が「良い文字列」であるかを判定せよ。

条件 : $i \geq 1$ を満たす全ての整数 $i$ について、文字列内でちょうど $i$ 回現れる文字は、ちょうど0種類または2種類である。

制約

$S$ の長さは1以上100以下。

考察

まず、 $S$ 中の文字の種類とその個数を管理したいので、前者をkey、後者をvalueとしてmapに記録していく (ここでは変数名をmpとした) 。

次に、 $i$ を $i = 1, 2, 3, ...$ と増やしていく過程で、以下の判定を行う。

mpの全要素を走査し、mp.second == iならカウンターを増やす。その後、カウンターが0または2でないならば、「良い文字列」の条件を満たさないので即座にNoを出力してプログラムを終了する。そうでなければ、iを1増やす。

この判定全てを通過した場合はYesと出力すればよい。

最後に、 $i$ はどこまで増やすかという点についてだが、これは「 $S$ の長さが最大100」という制約から、同じ文字が最大100個続く文字列が入力されることを考えて、上限を100までにしておけば良いだろう。

コード

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

using ll = long long;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    string S;
    cin >> S;
    map<char, int> mp;
    rep(i, 0, S.size()) mp[S[i]]++;

    rep(i, 1, 101)
    {
        int cnt = 0;
        for (auto &&m : mp)
        {
            if (m.second == i)
                cnt++;
        }

        if (!(cnt == 0 || cnt == 2))
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}