【競プロ】樹形図

競プロでよく出題される問題には、「何通りありますか？」「何個・何組ありますか？」といった、数え上げる問題があります。ここでは、簡単な問題を例にして考え方を見ていきます。競プロ 記事の一覧はこちら。

基本的な数え上げの方法

「何通りありますか？」というような問題を考える場合、一番基本的な数え方は、「すべて書き出す」方法です。

例えば、「○」と「×」を使って、横一列に3つ並べる方法が何通りあるか考えてみます。「○」も「×」も、いくつ使ってもいいし、使わないものがあってもいいとします。

この場合、数が少ないので、簡単に書き出すことができます。次のようになります。

　○○○
　○○×
　○×○
　○××
　×○○
　×○×
　××○
　×××

すべてを書き出して数える方法は確実ですが、漏れやダブりがないようにしなければいけない点に注意します。そのためには、ルールを決めて書き出していくのがいいです。上の例では、左側に○があるほうが上に来るように書き出しています。

書き出す順序にルールを設けて順番に書き出せば、漏れやダブりが起こりにくいです。このように書き出せば、 $8$ 通りであることがわかります。

樹形図

先ほどは、すべて書き出して数えましたが、同じ文字を何度も書くのが少し大変ですね。

たとえば、先ほど書き出した内容をよく見ると、上の4つは、1番左が全部○で、下の4つは1番左が全部×です。これらをまとめて次のように書いてみます。

左から2つ目も共通しているものがあるので、まとめてみます。

こうすると、共通しているものがまとめられるので、文字を書く量が減っていいですね。これを反時計回りに90度回転すると、地面から木が生えているように見えるので、このような図を樹形図(tree diagram) といいます。

樹形図を用いてすべてのケースを書き出すと、文字を書く量が減るだけではありません。数え方もわかりやすくなります。

上半分と下半分をよく見ると、左から2つ目と3つ目の並び方はまったく同じことがわかります。そのため、並べ方は、

　2×（左から2つ目と3つ目の並べ方）

となることがわかります。「2×」というのは、一番左が○のときと×のときの2セットある、ということです。

同じように考えると、左から2つ目と3つ目の並べ方は、左から2つ目の決め方が2通りあって、左から3つ目の決め方も2通りあります。つまり、すべての並べ方は、\[ 2×2×2 \]通りであることがわかります。

樹形図をかけば、同じ構造になっている場所を見つけやすくなり、どのように数えればいいかがわかりやすくなります。左から1つ目、2つ目、3つ目は、それぞれ○か×の2通りあって、これらは互いに無関係に決まるものなので、 $2^3$ 通りだとわかります。

この考え方がわかれば、「3つ並べる」の部分が変わっても、同じように数えられることが分かります。5つ並べるなら $2^5$ 通りだし、10個並べるなら $2^{10}$ 通りです。「 $n$ 個並べる」場合に、どういう答えを出せばいいか、どういうコードを書けばいいかがわかるでしょう。 $n$ が $10$ 以下の正の整数という制約であれば、次のようなコードで求められます（参考：整数の整数乗）。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  int a = 1;
  for (int i = 0; i < n; i++) a *= 2;
  cout << a;
  return 0;
}

$n$ がもう少し大きい可能性があるなら、 $10^9 + 7$ で割った余りを答えることが多いです。例えば、100個並べるときでも正しい答えを出そうとすると、次のようになります（参考：余りの計算）。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  long long a = 1, MOD = 1e9 + 7;
  for (int i = 0; i < n; i++) {
    a = (a * 2) % MOD;
  }
  cout << a;

  return 0;
}

例えば、100 を入力すると、976371285 が返ってきます。これは、 $2^{100}$ を $10^9+7$ で割った余りです。

「○, ×」の2種類ではなく、「○, ×, △」というように、3種類の文字を並べる場合も、樹形図がどうなるかを考えれば、数え方がわかるでしょう。線が2つに分かれていた部分が、3つに分かれるように変わり、同じ構造が3つできることがわかります。そのため、「3つ並べる」なら $3^3$ 通りで、10個並べるなら $3^{10}$ 通りとなることがわかります。

ここまでの内容を踏まえると、AtCoder ABC 140 A - Password がわかるでしょう。

積の法則

樹形図をかくと、同じ構造を見つけやすいですね。同じ構造があれば、まとめて数えることができて便利です。先ほどの例であれば、1つ目を決めれば、2つ目・3つ目の決め方は同じ図が続くので、「2×（左から2つ目と3つ目の並べ方）」と掛け算で求められますからね。

このように、同じ構造があれば、掛けて計算できることを、積の法則といいます。少し抽象的に書くと、次のようになります。

上の例では、1つ目の決まり方が2通り、2つ目の決まり方が2通り、3つ目の決まり方が2通りあって、それぞれ独立に決まるので、3つの並べ方は $2\times 2\times 2$ 通りになる、ということです。

簡単な例であればそれほど難しくはない（というか、当たり前に思える）のですが、競プロでの数え上げの問題では頻繁に使う考え方です。

おわりに

ここでは、競プロの数え上げの問題を考えるときに使える、樹形図を紹介しました。簡単な問題では、先ほど紹介した樹形図を使った書き出しが役に立つでしょう。

他にも数え方についてはいくつかの考え方があります。高校生向けのページですが、【導入】数え方の基本 で紹介しています。下にある5つあるリンクのうち、下の3つが該当します。簡単に内容をいうと、「わざとダブらせて数えてから不要なものを引いたり、2重に数えてからあとで2で割ったりする方法」「全体から、不要なものを引く方法」「今数えたいものに関連する、別のわかりやすいものを数える方法」を取り上げています。

なお、樹形図について数学の内容として解説しているページは、【基本】まとめて数えるにあります。