CodeIQ：単調増加連数

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「単調増加連数」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
【概要】
正の整数を 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 以上 百億以下です。
「単調増加連数」は、この問題のために作った造語です。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def part(nums)
	ret = [nums]
	arr = nums.dup

	n = arr.pop
	if n % 2 == 1 then h = n/2
	else h = n/2-1
	end

	min = arr.last != nil ? arr.last+1 : 1
	if h >= min then
		for left in min..h
			right = n - left

			nxt = arr + [left, right]
			ret += part(nxt)
		end
	end

	return ret
end

def toNum(arr)
	str = "0b"
	for i in 0...arr.size
		v = (i+1) % 2
		str += v.to_s * arr[i]
	end

	return str.to_i(2)
end

def solve(n)
	sz = n.to_s(2).size
	ps = part([sz])
	f = ps.shift
	ps.push(f)

	ret = (n == 1) ? 3 : toNum([1,sz])

	for arr in ps
		cand = toNum(arr)
		if cand <= n then next
		elsif cand < ret then ret = cand
		end
	end

	return ret
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i)
end

解説

結構難しいです。
入力値の最大値が大きいので単純にやるとできないと思います。

考え方

この問題は自然数の分割を利用します。
単調増加連数の「0や1の続く長さ」をみてください。
例えば293888のビット長は19です。293888の「0や1の続く長さ」は「1, 3, 5, 10」でこれは19を全て異なる自然数で分割した場合の分割数のパターンの1つを小さい数字から順に並べたものです。
他の単純増加連数もそうです。
その数字のビット長は「1の続く長さ ＋ 0の続く長さ ＋ 1の続く長さ ＋ ...」です。それぞれの0や1の続く長さやは全て異なる数で大きくなってゆき、その合計がビット長になる ＝ ビット長を全て異なる自然数に分割し、そのパターンのうち1つを小さい数から並べたもの、が成り立つわけです。

なので入力値のビット長を求め、その分割数を「1の並び, 0の並び, 1の並び, ...」とした場合の数値を小さい方から入力値と比較し、初めて入力値を超えたものが答えになります。

唯一例外が7（0b111）の様な全て1だけで構成される入力値の場合で、この場合だけは答えが「1, 入力値のビット長の数の0」になります（7の次の単調増加連数は8(0b1000)です）。

main

入力値を数値にしてsolve()に渡します。
結果が配列で帰るのでjoin()して印字します。

solve(n)

問題を解きます。

36行目で入力値のビット長を求めます。ビット長は2進数の文字列表現の場合の文字列の長さです。
37行目で全て異なる数で構成される分割数のリストを生成します。このリストはリストの分割数を単純増加連数にした場合、最初の要素を除いて小さい値から大きい値になるリストになっています。最初の要素は単純増加連数にした場合、最大の数なので38〜39行目でリストの最後に移動しています。

41行目のretは返却値で初期値は0b1000...の様な最初だけが1、それ以降が0の数です。これは入力値が0b111...の様な1だけで構成される数の場合の答えで、入力値が0b111...の様な数の場合、psのリスト内に答えがない時の答えになります。

43〜48行目で入力値の次の単調増加連数を探します。
toNum()は[1,2,3]の様な配列を数値（[1,2,3]の場合は39（0b100111））にします。
これがnより大きく、retより小さければretを置き換えます。

最終的にループを終えた時点のretが答えになります。

part(nums)

この関数はnumsの値を全て異なる自然数に分割した場合のパターンを列挙して返します。
引数numsは[1,2,3]の様な分割途中の数列で、最初の呼び出し時は[6]の様に分割したい数を1つだけ要素にもつ配列です。

retは返却値で[nums]は分割数の一つなのでretに含めます（4行目）。
arrは分割操作を行う数列で、初期値はnumsのコピー（[入力値]）です。

arrから最後の値をpop()してnに取ります。
8〜10はこの操作の分割数の最大値hを計算しており、nが奇数ならn/2、偶数ならn/2-1になります。

12行目はこの操作での分割の最小数で、arrに数字があればその最後の数+1、なければ1に設定します。

13行目のif文はh（分割の最大値）がmin（分割の最小値）より大きければmin〜hの間の数で分割できるので、そのチェックをしています。

14〜19行目のループでmin〜hまでの数で1回の分割を行います。
leftはある数を2つに分割した時の小さい方の値で、例えば7を[3,4]に分けた時の3がleftになります。
15行目のrightはn-leftなのである数を2つに分割した時の残り、例えば7を[3,4]に分割した時の4になります。

nxtは1回の分割を行った結果の数列でarrに[left, right]を付け加えたものになります。

ここまでの操作を具体的に示すと8を分割する場合だと次の様になります。
arr = [8]
n = 8, arr = []
h = 3
min = 1
1〜3で分割を実施。
 []+[1,7]
 []+[2,6]
 []+[3,5]

18行目でこの様にしてできた結果に対し、partを再起的に呼び出すことで末尾の数をさらに分割します。そしてそれ以上分割できなくなった結果をretに順次追加することでリストを得ます。

toNum(arr)

arrの配列の値に従ってビット列を生成して数値にします。
arrは[1,2,3]の様な単調増加連数の1と0の連続数を大きな位の方から列挙したものです。
配列の要素番号が偶数の時は1、奇数の時は0として文字列にします。
文字列を2進数数値に変換して返します。

雑感

この問題、私が最初の正解者でした（バッジの獲得者を見たら1人でした）。
ビット長の分割数というアイデアを比較的早く思いついたことと、分割数列挙のプログラムを持っていた（昔に作ってあった）のでそのまま流用できたのが大きいですが。
分割数の問題は時々出題されますが、検索しても分割数列挙のプログラムはあんまり見つからないし、自分で考えると結構難しいです。