けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 225 A - Distinct Strings (7Q, 灰色, 100 点)

これ結構難しいと思う! 数学 IA の「場合の数」をやると、よく出て来るやつですね。

問題概要

英小文字のみからなる長さ 3 の文字列  S が与えられます。

 S の各文字を並び替えて得られる文字列は、何種類ありますか?

解法

「3 個のものを並び替える場合の数」は、数学 IA だとよく出て来るやつですね。実は次の 3 パターンがあります。


  •  (a, a, a) のように、すべて同じものを並び替える方法
    • 1 通りです
  •  (a, a, b) (a, b, b) のように、2 種類のもので構成される場合に、それを並び替える方法
    • 3 通りです
  •  (a, b, c) のように、3 種類のもので構成されるとき、それを並び替える方法
    • 6 通りです

たとえば、 (a, a, b) を並び替える方法は、

 (a, a, b), (a, b, a), (b, a, a)

の 3 通りあります。 (a, b, c) を並び替える方法は、

 (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)

6 通りあります。

問題に戻って

上記のことを踏まえると、今回の問題は次のことを判別する問題だと言えます。

  • 文字列  S が 1 種類の文字で成り立つとき:1 通り
  • 文字列  S が 2 種類の文字で成り立つとき:3 通り
  • 文字列  S が 3 種類の文字で成り立つとき:6 通り

判別の手順としては、「1 種類」「3 種類」を判別するのが楽なので、「2 種類」を判別する部分は else 文に押し付けるのが楽ですね。

コード

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

int main() {
    string S;
    cin >> S;
    if (S[0] == S[1] && S[1] == S[2])
        cout << 1 << endl;
    else if (S[0] != S[1] && S[1] != S[2] && S[2] != S[0])
        cout << 6 << endl;
    else
        cout << 3 << endl;
}