プレフィックスとサフィックスの全位置でBの数がA以上となる文字列の並べ方を求めるPythonプログラム

問題の概要

「A」がn個、「B」が2n個含まれる文字列を考えます。このとき、文字列のすべての接頭辞(プレフィックス)とすべての接尾辞(サフィックス)を取り出しても、「B」の数が常に「A」の数以上になっているような並べ方が何通り存在するかを求めるのが本記事のテーマです。

例えば、n = 2 の場合を考えてみましょう。「A」が2個、「B」が4個あるとき、条件を満たす並べ方は次の4通りになります。

• BBAABB
• BABABB
• BBABAB
• BABBAB

したがって、入力が n = 2 のとき、出力は 4 となります。

解法のアプローチ

この問題は、再帰呼び出しを利用した分割統治の考え方で解くことができます。手順は以下の通りです。

• 引数として n を受け取るメソッド solve を定義します。
• n が 1 の場合は、1 を返します。
• n が 2 の場合は、4 を返します。
• n が奇数の場合は、solve((n-1)//2) の2乗を返します。
• n が偶数の場合は、solve(n//2) の2乗を返します。

Pythonでの実装例

それでは、上記の手順を実際のコードで確認してみましょう。

def solve(n):
    if n == 1:
        return 1
    if n == 2:
        return 4
    if n % 2 != 0:
        return solve((n - 1) // 2) ** 2
    else:
        return solve(n // 2) ** 2

n = 2
print(solve(n))

実行結果

入力:

2

出力:

4

コードのポイント

この実装では、まず n = 1 と n = 2 の場合をベースケースとして扱い、それぞれ既知の答えである 1 と 4 を直接返しています。それより大きい n に対しては、n の偶奇に応じて問題を半分のサイズの部分問題へと帰着させ、再帰的に解いた結果を2乗することで最終的な答えを導いています。

このように再帰構造を活かすことで、すべての並べ方を網羅的に列挙することなく、答えをコンパクトに計算できる点がこのアプローチの特徴です。