同じ問題を何度も解いてもRateを得ることができません。
http://yukicoder.me/problems/no/381
問題
あるクエストを初回クリアするとNの名声が得られる。
以後、クリアのたびに前回の半分(小数点以下切り捨て)の名声が得られる。
一方、スキルを用いるとその次のクリア時に得られる名声が倍になるが、それ以上名声を得られない。
最適なタイミングでスキルを１回用いる場合得られる名声の総和は、スキルを用いない場合に比べ最大どれだけ多いか。
解法
Nが2^kのケースを考える。
スキルを用いないと得られる名声の総和は2^k+2^(k-1)+2^(k-2)...+1 = 2^(k+1)-1である。
一方最初にスキルを用いると2^(k+1)得られる。
この事実より、最初にスキルを用いると1余分にスキルを得られる。
上記考察より、答える値はNを２進数表記したときの1のbitの数と同じであることがわかる。
ただ、入力が大きく入力をまじめに２進数に基数変換を実装しようとすると辛い。
…他の回答者があっさり解いているのを見て、Pythonの機能を使ったら簡単に解けてしまいました。
こんなんでいいのかなぁ…。
print bin(input()).count("1")
まとめ
基数変換はまじめに１度練習しておいた方がいいのかな。
