TOYPRO解説記事 - グループ分け(400点)

1.概要

競技プログラミングサイト「TOYPRO」の400点問題
「グループ分け」の解説を行います。

2.問題

N人の生徒から2人選んだ時のグループの数、3人選んだ時のグループの数、、、N人選んだ時のグループの数を全て足していった時全部でいくつのグループになるか求めてください。

制約

$2\leq N \leq 100$

必要な変数

N

入力例

N = 3

出力例

4

3.解説

この問題には2つの解法があります。どちらも計算によって最終的に求められる値は同じになります。

3.1 解法1 それぞれの人数を選んだときのグループの数の総和を計算する

ここでは、N = 3の場合で考えます。

3.1.1(2人選んだ時のグループの通りの数)

3人の中からまず1人を選びます。その後、2人の中から1人を選びます。
したがって、3×2 = 6だ！と思った人がいると思いますが、これは間違いです。この考え方だと、考えられるグループは以下の図の通りになります。
ここで気づくのは、AさんとBさん,BさんとAさんというように、同じペアを並び方を変えて数えてしまっているということです。
並び方による影響をなくすためには、
この場合2個の並べ方の通り数である2通りで割る必要があり、
$\frac{3×2}{2} = 3$通りとする必要があります。

組み合わせを考えるときは、並び方による影響を考えましょう

これで、2人選んだ時のグループの通りの数を求める事が出来ました。

3.1.2(3人選んだ時のグループの通りの数)

3人の中からまず1人を選び、その後2人の中から1人を選び、最後に1人を選びますが、これも並び方が6通りあるので、$\frac{3×2×1}{6} = 1$通りになります。

以上により、N = 3 の場合は$4$通りあることが分かりました。

3.1.3 解法1のまとめ

上の説明はN = 3の場合ですが、N = 100の場合でも同様の計算を行うことにより、答えの組み合わせ数を求めることが出来ます。
この計算を行う場合、計算量は$2 + 3 + ... N = \frac{N(N+1)}{2} - 1$であることから
$O(N^2)$となります。これは今回の制約では十分高速です。

以下に、解答例を示します。

N = 3
ans = 0
#ans = 答えの数
for i in range(2,N+1):
    p = 1
    q = 1
    #pは分子、qは分母
    for j in range(i):
        p *= N - j
        q *= j + 1
    ans += p // q
print(ans) 

3.2 解法2 計算で求める

今回の問題の類題として

N人の中から0人以上を選ぶ組み合わせは何通りでしょうか？

という問題を考えてみます。

i人目を選ぶ・選ばないの2択に分けて組み合わせを考えてみましょう。

以下、選ぶということを1,選ばないということを0という数字で置き換えます。
組み合わせを文字列で考え、左からi$(1 \leq i \leq N)$番目の桁を
i人目についての選び方として定義します。
すると、例えばN = 3のときは以下の画像の通りとなります。

それぞれの人に対して選ぶ・選ばないという組み合わせが存在しているので 2×2×2 = 8通りの選び方となります。
これは、どのようなNに対しても同じ事がいえます。 したがって、Nに対して$2^{N}$通りが答えとなります。

$2^{N}$ は、2を$N$回かけたときの値。例)$2^2 = 4$, $2^5 = 32$

ここから、今回の問題の答えとして含まれていない

• 0人の選び方{選ばない,選ばない,...選ばない}の1通り
• 1人の選び方の$N$通り

を引いた$2^N - N - 1$通りが答えになります。

Nが100までなので、値が非常に大きくなりますが、Pythonの場合は整数型に対して上限がないので$2^{100}$についても表現することが出来ます。
よって、計算量$O(1)$でこの問題を解くことが出来ました。
以下に、解答例を示します。

N = 1
ans = 2 ** N - N - 1
#ansは答え
#2 ** Nで2のN乗を計算しています。
print(ans)

4 まとめ

今回は、2通りの解法を紹介しましたが、いかがでしたでしょうか？
組み合わせの問題はこのように答えを数式にすることで計算量を減らせるということを実感して頂いたと思います。

以上で、400点問題「グループ分け」の解説を終了します。