Pythonでn番目のバイナリ文字列のk番目のビットを求める方法

問題の概要

2つの正の整数 n と k が与えられたとき、次の規則に従って生成されるバイナリ文字列 S_n の中から、k番目のビットを求めることを考えます。

• S₁ = 0
• i > 1 のとき、S_i = S_i-1 + "1" + reverse(invert(S_i-1))

ここで、reverse(x) は文字列 x を逆順に並べ替えた結果を返し、invert(x) は x のすべてのビットを反転(0と1を入れ替え)させた結果を返します。

この規則によって生成される最初の4つの文字列は以下のとおりです。

• S₁ = "0"
• S₂ = "011"
• S₃ = "0111001"
• S₄ = "011100110110001"

例として、n = 4、k = 10 が入力された場合を考えてみましょう。S₄ = "011100110110001" であるため、10番目のビットは「1」になります(先頭のビットを位置1として数えます)。

解き方のアプローチ

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

1. k が 1 の場合は「0」を返します(S₁ は必ず 0 だからです)。
2. それ以外の場合は、要素 0 のみを持つ配列 arr と、要素 1 のみを持つ配列 arr2 を用意します。
3. arr の長さが k 以上になるまで、次の操作を繰り返します。
   • templast := arr のコピー
   • temp2last := arr2 のコピー
   • arr := templast + [1] + temp2last
   • arr2 := templast + [0] + temp2last
4. 最後に、arr の (k-1) 番目の要素を返します。

ポイントとなるのは、arr2 が常に arr のビットを反転した文字列を保持しているという点です。つまり、arr は現在の S_i に、arr2 は invert(S_i) に対応します。この仕組みにより、毎回文字列全体を明示的に反転・逆順にする処理を行わなくても、次の段階の文字列を効率よく構築できます。また、各段階で文字列の長さは「前の長さ × 2 + 1」(1 → 3 → 7 → 15 …)と増えていくため、k 番目のビットが確定するまでの繰り返し回数はごくわずかで済みます。

Pythonでの実装例

def solve(n, k):
    if k == 1:
        return str(0)
    else:
        arr = [0]
        arr2 = [1]
        while k > len(arr):
            templast = arr.copy()
            temp2last = arr2.copy()
            arr = templast + [1] + temp2last
            arr2 = templast + [0] + temp2last
        return str(arr[k-1])

n = 4
k = 10
print(solve(n, k))

入力

n = 4, k = 10

出力

1

まとめ

本記事では、再帰的な規則で生成されるバイナリ文字列 S_n の k 番目のビットを求めるアルゴリズムを紹介しました。反転版の配列を同時に管理することで、文字列の反転や逆順の操作を省略でき、シンプルかつ効率的な実装が実現できます。同様の「自己相似的な文字列生成」の問題では、このテクニックが応用できるので、ぜひ覚えておきましょう。