「レッド・アンド・ホワイト」問題の解答と解き方

CodeIQにて、Kawazoeさん（@riverplus）の問題「『レッド・アンド・ホワイト』問題」を解きました。解き方と解答を書いておきます。

■問題概要

最初（0秒後）、横に直線状に並ぶ白いマス目（左右どこまでも続く）の1つが赤で塗られている。
以降、次のルールに従って、マス目の色を塗り替えていく。
1秒後、左右隣のマス目の色が白赤または赤白となるマス目を全て赤色で塗り、そうでないマス目（つまり左右隣が白白または赤赤）を全て白色で塗る。
同様に、1秒ごとに赤白でマス目を塗り替えていきます（「■解き方」の図に31秒後まで示す）。
自然数nに対し、n秒後の赤色のマス目の個数をF(n)と定義する。
標準入力から、自然数n（1≦n≦10⁸）が与えられ、標準出力にF(n)の値を出力するプログラムを作成する。

■解き方

n秒後の状態を表した図を上に示す。
nが0〜(2²-1)，0〜(2³-1)，0〜(2⁴-1)，…の範囲でピラミッド形ができる。
これを利用すれば、例えばn=29のとき（図中の網掛け部分参照）、F(29)=2・F(13)=2・2・F(5)=2・2・2・F(1)と求めることができる。
つまり、2^m-1＜n≦2^m+1-1(mは自然数)のとき、
F(n)=2・F(n-2^m)となり、再帰的に求めることができる。

■解答

C++で書いた解答を以下に示します。

int getRedNum(int m) {
    switch (m) {
    	case 0 : return 1;
	case 1 : return 2;
	case 2 : return 2;
	case 3 : return 4;
    }
    
    int l = 4;
    
    while(l <= m) {
        l *= 2;
    }
    
    l /= 2;
    
    return getRedNum(m - l) * 2;
}

int main() {
    string line;
    int n = 0;
    
    for(int i = 0; getline(cin,line); ++i) {
        n = stoi(line);
    }
    
    cout<<getRedNum(n)<<endl;
}