CodeIQ 「バイナリ・カウント」 解法
Kawazoe (@riverplus)
1〜n の整数を⼆進数で表したときの 1 の個数の総和を求める問題です。
整数を⼀つずつ調べるやり⽅では時間がかかりすぎてしまいます。
複数の 1 をうまくまとめ上げて、効率的に計算を⾏いましょう。
実際に⼆進数をいくつか書き下してみると、縦⽅向に規則性が⾒えてきます。
d-1
⾚で囲ったように、右から d 列⽬には 2 個の⻑さの 1 が縦にかたまって並んでいます。
d
このかたまりは全部で ⌊(n+1)/2 ⌋ 個あります。
d
さらに、端数部分の 1 の⻑さは max(0,((n+ 1)mod 2 )−2
d−1
) となることが⽰せます。
これらの公式を使うと、d 列⽬の 1 の総数を O(1)で求められ、トータルでは O(log n) で計算できます。
（なお、すみませんが、本問の公開終了⽇までは、この URL を周りに教えないよう、ご協⼒お願いします。）

CodeIQ 「カット・アンド・スクエア」 問題 解法

高血圧の運動療法

『笹倉交差点』の 前右側に郵便局があり、左側には｢笹倉｣のバス停

空港バス＋ことでん 印刷用地図

Document

山岡荘八（PDF）

詳細 FAX用申込用紙 - 国際カイロプラクティック師連盟

カ シ マ ゴ ー ル 栽 培 暦 - 茨城県農林振興公社

メッセージ

まもなくゴールです！ キャンプ場入口 牧場 キャンプ場

救急出動件数 - 佐久広域連合

再度拝謝 - 大阪府医師会員へのお知らせ

春に きたい学校・志望校・ 標を決めることの重要性 なぜ、わざわざ 標

ふくしゅう・まとめ①