CodeIQ:【実力判定:Bランク】ビットカウント

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「【実力判定:Bランク】ビットカウント」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
【問題】
2つの整数値N, Mが与えられます。
0からNまでの各整数(10進数)について、2進表記したときに1の数がM個になるものを数えてください。
たとえば、9を2進表記すると1001ですので、1の数は2ということになります。

【入力】
標準入力から、半角スペースで区切られた2つの整数値N(0≦N≦100000)、M(0≦M≦17)が与えられます。

【出力】
0からNまでの整数の中で、2進表記したときに1の数がM個あるものの個数を出力してください。

【入出力サンプル】
Input
10 2
標準出力
5

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def solve(n,m)
	st = 0
	for i in 0...m do st |= (1 << i) end

	cnt = 0
	for i in st..n
		if i.to_s(2).count("1") == m then cnt += 1 end
	end

	return cnt
end

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

	n,m = line.split.map{|a| a.to_i}
	p solve(n,m)
end

解説

Bランクの問題ですが、これも総当たりで行けるので難しくありません。

考え方

Nが最大で100000なので総当たりでも間に合います。
全部の数字のビット数をチェックしてしまいます。

solve()

全ての数の1のビットの数を数えます。
大した効果はありませんが、最初の数は1がM個連続したものなのでそこからスタートします。
Rubyの場合、文字列にして1の数を数えるのが最速なのでそのようにします。

雑感

最初、動的計画法か再帰で数を構築しようかと思いましたが面倒になってやめてしまいました。