私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「【実力判定：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なので総当たりでも間に合います。
全部の数字のビット数をチェックしてしまいます。
全ての数の1のビットの数を数えます。
大した効果はありませんが、最初の数は1がM個連続したものなのでそこからスタートします。
Rubyの場合、文字列にして1の数を数えるのが最速なのでそのようにします。
最初、動的計画法か再帰で数を構築しようかと思いましたが面倒になってやめてしまいました。