はまやんはまやんはまやん

hamayanhamayan's blog

Not simply beatiful strings [Codeforces Round #471 (Div. 2) B]

http://codeforces.com/contest/955/problem/B

文字列Sがある。
これを2つのadorableな文字列に分割できるか判定せよ(連続する文字列で分割しなくてもよい)。
adorableな文字列とは「2種類の文字で構成される文字列」のこと。

解法

http://codeforces.com/contest/955/submission/36558311

「cnt[c] := 文字cが何個あるか」をmapを使って数えて、それを使って解いていこう。

  • 4<cnt.size()
    • 2種類の文字列2つに分割できないのでNo
  • 4=cnt.size()
    • 2種類に分ければいいのでYes
  • 3=cnt.size()
    • 全ての文字が1個ずつの場合は、2種類と1種類になるのでNo
    • 2個以上の文字が1つでもあれば、それを2つに分ければ2種類ずつにできるのでYes
  • 2=cnt.size()
    • どちらの文字も2個以上あれば、2種類の文字列が2つ作れるのでYes
    • そうでないならNo
  • 1=cnt.size()
    • 2種類は当然実現不可能なのでNo
string S;
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    map<char, int> cnt;
    fore(c, S) cnt[c]++;

    if (4 == cnt.size()) return yes;
    else if (cnt.size() == 3) {
        int ok = 0;
        fore(p, cnt) if (2 <= p.second) ok = 1;
        if (ok) return yes;
        return no;
    } else if (cnt.size() == 2) {
        int ok = 0;
        fore(p, cnt) if (2 <= p.second) ok++;
        if (ok == 2) return yes;
        return no;
    }
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    cout << solve() << endl;