読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

yukicoder No.381 名声値を稼ごう Extra

解法

kmjp さんの解法を参考にしました。
kmjp.hatenablog.jp

適当に i = 1, 2, ..., 100 で実験すると, 答えが __builtin_popcount(N) となりそうなことに気付きます。

実際, (極端に) N = 2^k とすると, 単純に足し算した場合は 2^(k+1) - 1, 2 倍した場合は 2^(k+1) となり 1 得になるのでこうなります。

問題は N を 2 進数に変換する方法なんですが, 世の中便利で python では

print bin(input()).count("1")

とやれば良いようです。