C++で長さNのバイナリ文字列のうち3つ以上の連続した1を含むものの個数を求める方法

問題の概要

整数Nが与えられたとき、長さNのすべての異なるバイナリ文字列のうち、少なくとも3つの連続した1を含むものの総数を求めます。例えば、N = 4の場合、条件を満たす文字列は「0111」「1110」「1111」の3つであるため、出力は3となります。

アプローチ:動的計画法(DP)

この問題は動的計画法を用いることで効率的に解くことができます。ここで、DP(i, x)を「長さiの文字列のうち、位置i+1からi+xまでにx個の連続した1が並んでいる文字列の数」と定義します。すると、漸化式は次のように表されます。

DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)

この漸化式は、位置iに0と1のどちらが来るかという事実に基づいています。

• 位置iに0が来る場合:(i – 1)番目の位置でのxの値は0になります
• 位置iに1が来る場合:(i – 1)番目の位置でのxの値は、位置iでのxの値に1を加えたものになります

C++での実装例

以下は、メモ化再帰を用いたC++による実装例です。

#include<iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
    if (i < 0)
        return x == 3;
    if (table[i][x] != -1)
        return table[i][x];
    table[i][x] = numberCount(i - 1, 0, table);
    table[i][x] += numberCount(i - 1, x + 1, table);
    return table[i][x];
}
int main() {
    n = 4;
    int table[n][4];
    for (int i = 0; i < n; i++)
    for (int j = 0; j < 4; j++)
        table[i][j] = -1;
    for (int i = 0; i < n; i++) {
        table[i][3] = (1 << (i + 1));
    }
    cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}

コードのポイント

• numberCount関数:再帰的に文字列の数を数えます。i < 0になった時点で、xが3に達しているかどうか(x == 3)を判定して返します。
• メモ化テーブル:table配列で計算済みの値をキャッシュすることで、重複する計算を避け、計算量を大幅に削減しています。
• 初期化の工夫:table[i][3] = (1 << (i + 1)) は、すでに3つの連続した1を持つ文字列の残りの部分は0と1を自由に選べることを利用した初期化です。

出力結果

The number of binary strings with at least 3 consecutive 1s: 3

N = 4の場合、条件を満たす文字列「0111」「1110」「1111」が正しくカウントされ、3が出力されます。この手法を使えば、Nが大きい場合でも全列挙(2^N通り)を避け、効率的に答えを求めることができます。