単調増加連数

単調増加連数

締め切りが 2017/11/24 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】
正の整数を 2進数で表現したときに、1や0の続く長さがどんどん増えていく数を「単調増加連数」と呼びます。例えば以下のとおりです：

値(10進数表示)    値(2進数表示)          1や0の続く長さ      単調増加連数？
7               111                   3                 TRUE
10              1010                  1, 1, 1, 1        FALSE
77              1001101               1, 2, 2, 1, 1     FALSE
79              1001111               1, 2, 4           TRUE
240             11110000              4, 4              FALSE
399             110001111             2, 3, 4           TRUE
1136            10001110000           1, 3, 3, 4        FALSE
3975            111110000111          5, 4, 3           FALSE
293888          1000111110000000000   1, 3, 5, 10       TRUE

入力された値よりも大きな「単調増加連数」で、最も小さいものを出力してください。

【入出力】
入力は77のようになっています。普通に 10進数です。
出力も普通に10進数です。77 より大きな「単調増加連数」として最も小さい値を出力すれば良いので、77に対応する出力は79です。

【例】
入力   入力の2進数表示    出力    出力の2進数表示    出力の1や0の続く長さ
77    1001101          79     1001111          1, 2, 4
79    1001111          96     1100000          2, 5
57    111001           63     111111           6

【補足】
    •    不正な入力に対処する必要はありません。
    •    入力は 1 以上 百億以下です。
    •    「単調増加連数」は、この問題のために作った造語です。

================================================================================

n を 1 ずつ増やして...なんて，普通にやったら n が大きいときには日が暮れる。
紙に書いてやれば，簡単に答えが得られる。しかし，アルゴリズムをプログラム化するのが面倒。

n より大きい数で，その二進表記のビット列が「1 が a1 個, 0 が a2 個, また 1 が a3 個, 0 が a4 個 …」のようになっていて，a1 < a2 < a3 < a4 < … < ak である二進数の最小値を求めるということ。
n+1 のビット列の長さが 8 の場合だと，8 を要素数の相異なる部分に分割する方法は，(8), (7,1), (6,2), (5, 3), (5, 2, 1), (4, 3, 1) の 6 通り。
それぞれは
11111111
11111110
11111100
11111000
11111001
11110001
これを十進数に変換して，n より大きくて最小のものを求めればよい。

initDiv = function(length, max) {
    ary = NULL
    repeat {
        if (max >= max) {
            ary = c(ary, length)
            return(ary)
        } else {
            ary = c(ary, max)
            length = length - max
        }
    }
}

nextDiv = function(ary) {
    repeat { # 1でない要素を後ろから探す
        sum = 0
        for (pos in length(ary):1) {
            a = ary[pos]
            sum = sum + a
            if (a != 1) {
                break
            }
        }
        if (ary[1] == 1) { # 全て1
            return(FALSE)
        }
        ary = ary[1:pos]
        ary[pos] = ary[pos] - 1
        max = ary[pos]
        sum = sum - max
        pos = pos + 1
        repeat {
            if (max >= sum) {
                ary[pos] = sum
                return(ary)
            } else {
                ary[pos] = max
                sum = sum - max
            }
            pos = pos + 1
        }
    }
}

f = function(n) {
    minAns = Inf # n+1 以上で，条件を満たす最小の整数
    length = max = floor(log2(n+1))+1 # n+1 を二進表記したときの桁数
    weight = 2^((length - 1):0)
    first = TRUE
    repeat { # 整数分割
        if (first) {
            d = initDiv(length, max)
            first = FALSE
        } else {
            d = nextDiv(d)
            if (length(d) == 1) {
                break
            }
        }
        if (length(unique(d)) == length(d)) { # ある分割の要素数が全部違うものが探索対象
            D = rev(d) # 例えば，ビット列の長さが 8 なら，d は (8), (7,1), (6,2), (5, 3), (5, 2, 1), (4, 3, 1)
            bit = NULL # それぞれの D （d の逆順）の奇数番目は 1 の繰り返し数，偶数番目は 0 の繰り返し数
            for (i in seq_along(D)) { # d = (5, 2, 1), D = (1,2,5) なら bit = (1, 0, 0, 1, 1, 1, 1, 1)
                bit = c(bit, rep(i%%2, D[i]))
            }
            ans = sum(bit * weight) # 二進数の bit 列を十進数に変換
            if (minAns > ans && ans > n) { # その数が n より大きくて最小のものが解 minAns
                minAns = ans
            }
        }
    }
    cat(minAns)
}

# f(scan(file("stdin", "r")))

f(77) # 79
f(79) # 96
f(57) # 63
f(1) # 3
f(3) # 4
f(1e+10) # 10468982784
f(1228) # 1248
f(160199) # 161792
f(5368709119) # 6442450944
f(29614080) # 29614207
f(575) # 624
f(19968) # 19999
f(1278987) # 1279936
f(163831842) # 163831935
f(587776) # 588800