C++で隣接する1がちょうどK回現れる長さNのバイナリ文字列を数える方法

問題概要

整数 N と K が与えられたとき、0 と 1 のみから構成される長さ N のバイナリ文字列のうち、隣接する 1(連続する「11」)がちょうど K 回現れるものの総数を求めるのが目標です。

たとえば N=3、K=2 の場合、「11」が 2 回現れる 3 桁のバイナリ文字列をすべて数えることになります。

• 111:隣接する 1 の組が 2 回現れます(= K 回)
• 011 / 110:隣接する 1 の組は 1 回しか現れません

この問題は、すでに計算した小さいサイズの結果を保存しておくことで、効率よく解くことができます。

解き方の考え方(動的計画法)

ここでは 3 次元配列 count[x][y][z] を使用します。各添字の意味は次のとおりです。

• x:文字列の長さ(N)
• y:隣接する 1 の出現回数(K)
• z:文字列の末尾の桁(0 または 1)

初期条件

N=1 のとき、文字列は「0」と「1」の 2 種類だけで、どちらにも隣接する 1 は存在しません。したがって K=0 の場合のみ 1 通りずつ、K>0 なら 0 通りとなります。

count[1][0][0] = 1;
count[1][0][1] = 1;

末尾が 0 の場合

長さ N-1・隣接 1 の数が K であるすべての文字列の末尾に 0 を付け加えても、隣接する 1 のカウントは変化しません。

count[N][K][0] = count[N-1][K][0] + count[N-1][K][1];

末尾が 1 の場合

次の 2 つのケースを組み合わせて数えます。

• 長さ N-1・末尾が 0・隣接 1 の数が K の文字列に 1 を付ける → count[N-1][K][0]
• 長さ N-1・末尾が 1・隣接 1 の数が K-1 の文字列に 1 を付ける(新たな組が 1 つ増える)→ count[N-1][K-1][1]

count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1];

最終的な答えは次の合計になります。

答え = count[N][K][0] + count[N][K][1]

入出力例

例 1

入力:

N=4, K=2

出力:

文字列の個数: 2

説明:条件を満たすのは 1110 と 0111 のみです。どちらも隣接する 1 の組がちょうど 2 回現れます。

1110 → 「11」が 0〜1 桁目、および 1〜2 桁目に現れる(計 2 回)
0111 → 「11」が 1〜2 桁目、および 2〜3 桁目に現れる(計 2 回)

例 2

入力:

N=3, K=1

出力:

文字列の個数: 2

説明:隣接する 1 がちょうど 1 回現れるのは 110 と 011 のみです。111 では隣接する 1 が 2 回現れるため、該当しません。

アルゴリズムの手順

• 整数 N と K で、文字列の長さと隣接する 1 の出現回数を受け取ります。
• 関数 stringcount(int n, int k) が引数として n と k を受け取り、条件を満たす文字列の個数を返します。
• 配列 count[i][j][0/1] に、長さ i・隣接 1 の数が j・末尾が 0 または 1 である文字列の個数を格納します。
• 初期条件は count[1][0][0] = 1、count[1][0][1] = 1 です。
• 長さ 2(i=2)から n まで順に処理し、各長さについて j=0〜k の範囲で、前の結果をもとに count[i][j][0] と count[i][j][1] を更新します。
• j-1 >= 0 のとき(隣接 1 の数が 1 以上のとき)、末尾が 1 の個数に count[i-1][j-1][1] を加算します。
• 最後に count[n][k][0] と count[n][k][1] を合計して結果とし、返します。

計算量は状態数が O(N×K)、各状態の更新は定数時間なので、全体で O(N×K) となり、非常に効率的です。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

int stringcount(int n, int k){
    // 長さ n、隣接する 1 の組が k 個である文字列の個数
    int count[n + 1][k + 1][2] = {0};
    // count[n][k][0] -- 長さ n・隣接 1 が k 個・末尾が 0 の文字列の個数
    // count[n][k][1] -- 長さ n・隣接 1 が k 個・末尾が 1 の文字列の個数
    // n = 1 かつ k = 0 の場合
    count[1][0][0] = 1;
    count[1][0][1] = 1;
    for (int i = 2; i <= n; i++) {
        // 隣接する 1 の数は i-1 を超えない
        for (int j = 0; j <= k; j++) {
            count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
            count[i][j][1] = count[i - 1][j][0];
            if (j - 1 >= 0)
                count[i][j][1] = count[i][j][1] + count[i - 1][j - 1][1];
        }
    }
    int result = count[n][k][0] + count[n][k][1];
    return result;
}

int main(){
    int N = 6, K = 3;
    cout << "長さ6・隣接する1が3回現れる文字列の個数:" << stringcount(N, K);
    return 0;
}

実行結果

長さ6・隣接する1が3回現れる文字列の個数:7