Pythonで辞書順にソートされた母音文字列の数を求めるプログラム

数 n が与えられたとき、母音（a、e、i、o、u）だけから構成され、かつ辞書順（アルファベット順）にソートされている長さ n の文字列が全部で何通りあるかを求めます。ここで「文字列 s が辞書順にソートされている」とは、すべてのインデックス i について、s[i] が s[i+1] と同じ文字であるか、アルファベット上でより前に位置することを意味します。

たとえば入力が n = 2 のとき、出力は 15 になります。これは ["aa", "ae", "ai", "ao", "au", "ee", "ei", "eo", "eu", "ii", "io", "iu", "oo", "ou", "uu"] のように、条件を満たす文字列がちょうど 15 個存在するためです。

解き方の手順

この問題は、次の手順で解くことができます。

• n が 1 の場合：母音は 5 種類しかないため、5 を返します。
• サイズ 6 の配列 count を用意し、すべての要素を 1 で初期化します。
• i を 3 から n まで 1 ずつ増やしながら、以下の更新を繰り返します。
  • count[1] ← count[1] + count[2] + count[3] + count[4] + count[5]
  • count[2] ← count[2] + count[3] + count[4] + count[5]
  • count[3] ← count[3] + count[4] + count[5]
  • count[4] ← count[4] + count[5]
• total を 0 で初期化します。
• i を 1 から 5 まで動かしながら、total ← total + i × count[i] を計算します。
• total の値を返します。

このアルゴリズムは動的計画法の一種です。ループのたびに配列の後ろ側から累積和を取ることで、文字列を延長していく際の組み合わせの数を段階的に積み上げていきます。最後に各要素に重みを掛けて合計することで、条件を満たす文字列の総数が得られます。計算量は O(n) 程度と非常に効率的で、n が大きくなっても高速に動作します。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(n):
    if n == 1:
        return 5
    count = [1 for i in range(6)]
    for i in range(3, n + 1):
        count[1] = count[1] + count[2] + count[3] + count[4] + count[5]
        count[2] = count[2] + count[3] + count[4] + count[5]
        count[3] = count[3] + count[4] + count[5]
        count[4] = count[4] + count[5]
    total = 0
    for i in range(1, 6):
        total += i * count[i]
    return total

n = 2
print(solve(n))

入力

2

出力

15