C++で文法列のN行目・K番目の記号を再帰的に求める方法

この問題では、最初の行が 0 から始まる特別な数列を扱います。それ以降の各行では、直前の行を参照し、0 を「01」に、1 を「10」に置き換えることで新しい行を生成していきます。

N 行とインデックス K が与えられたとき、N 行目の K 番目の記号を求めるのが目的です(※ K は 1 から始まるインデックスです)。

たとえば N = 4、K = 5 の場合、出力は 1 になります。その理由は以下の通りです。

• 行 1: 0
• 行 2: 01
• 行 3: 0110
• 行 4: 01101001

行 4 の 5 番目の文字を数えると「1」であることが確認できます。

解法のアプローチ

この問題は、行が生成される規則性に注目すると再帰的に解くことができます。各行は前の行の各記号が必ず 2 文字に展開されるため、N 行目の位置 K は、N−1 行目の位置 ⌈K/2⌉ に対応します。

具体的には次の手順で解きます。

• メソッド名を kthGrammar とし、引数として N と K を受け取ります。
• N が 1 の場合は、行全体が「0」なので 0 を返す。
• K が偶数の場合、その記号は親の記号が反転したものです。つまり kthGrammar(N − 1, K / 2) が 0 なら 1 を返し、そうでなければ 0 を返す。
• K が奇数の場合、その記号は親の記号と同じなので、kthGrammar(N − 1, (K + 1) / 2) の結果をそのまま返す。

C++での実装例

以下のコードで実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int kthGrammar(int N, int K) {
      if(N == 1) return 0;
      if(K % 2 == 0){
      return kthGrammar(N - 1, K / 2) == 0 ? 1 : 0;
      }else{
         return kthGrammar(N - 1, (K + 1) / 2);
      }
   }
};
main(){
   Solution ob;
   cout << (ob.kthGrammar(4, 5));
}

入力

4
5

出力

1

計算量について

この再帰解法は、各呼び出しごとに行数 N が 1 ずつ減り、探索範囲も半分になるため、時間計算量は O(N)、再帰による空間計算量も O(N) となります。行を実際に構築して保存する必要がないため、N が大きい場合でも効率的に動作する点が大きなメリットです。