C++で二進表現に連続する1を含まない非負整数の個数を求める方法

正の整数 n が与えられたとき、n 以下の非負整数のうち、二進表現に「1」が連続して現れないものの個数を求める問題を考えます。例えば入力が 7 の場合、答えは 5 になります。これは、7 以下で条件を満たす整数が 0（0）、1（1）、2（10）、4（100）、5（101）の 5 個しか存在しないためです。3（11）、6（110）、7（111）は「1」が連続しているため除外されます。

解法のアプローチ

この問題は、桁ごとの動的計画法（DP）を用いることで効率的に解けます。各桁について「その桁が 0 で終わるパターン数」と「1 で終わるパターン数」を管理し、実際のビット列と照らし合わせながら答えを調整していきます。

具体的な手順は以下の通りです。

• 関数 convert() を定義します。引数として n を受け取ります。
• ret := 空文字列とします。
• n が 0 でない間、次を繰り返します。
  • ret := ret + (n mod 2)
  • n := n を 1 ビット右シフト
• ret を返します。
• メイン処理では以下を実行します。
• bits := convert(num) の呼び出し結果（num の二進表現）
• n := bits の長さ
• サイズ n の配列 ones と zeroes を定義します。
• ones[0] := 1、zeroes[0] := 1 で初期化します。
• i := 1 から i < n の間、i を 1 ずつ増やしながら次を繰り返します。
  • zeroes[i] := zeroes[i - 1] + ones[i - 1]
  • ones[i] := zeroes[i - 1]
• ret := ones[n - 1] + zeroes[n - 1] とします。
• i := n - 2 から i >= 0 の間、i を 1 ずつ減らしながら次を繰り返します。
  • bits[i] が '0' かつ bits[i + 1] が '0' の場合：
    • ret := ret - ones[i]
  • そうでなく、bits[i] が '1' かつ bits[i + 1] が '1' の場合：
    • ループを抜けます。
• ret を返します。

ここで、zeroes[i] は「長さ i+1 のビット列のうち、末尾が 0 で連続する 1 を含まないものの数」、ones[i] は「同様に末尾が 1 であるものの数」を表します。この遷移はフィボナッチ数列と同じ構造を持っている点がポイントです。

それでは、理解を深めるために以下の実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n >>= 1;
      }
      return ret;
   }
   int findIntegers(int num) {
      string bits = convert(num);
      int n = bits.size();
      vector <int> ones(n);
      vector <int> zeroes(n);
      ones[0] = zeroes[0] = 1;
      for(int i = 1; i < n; i++){
         zeroes[i] = zeroes[i - 1] + ones[i - 1];
         ones[i] = zeroes[i - 1];
      }
      int ret = ones[n - 1] + zeroes[n - 1];
      for(int i = n - 2; i >= 0; i--){
         if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
         else if(bits[i] == '1' && bits[i + 1]== '1') break;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findIntegers(7));
}

入力

7

出力

5