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

kmjp's blog

競技プログラミング参加記です

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

yukicoder

同じ問題を何度も解いてもRateを得ることができません。
http://yukicoder.me/problems/no/381

問題

あるクエストを初回クリアするとNの名声が得られる。
以後、クリアのたびに前回の半分(小数点以下切り捨て)の名声が得られる。

一方、スキルを用いるとその次のクリア時に得られる名声が倍になるが、それ以上名声を得られない。

最適なタイミングでスキルを1回用いる場合得られる名声の総和は、スキルを用いない場合に比べ最大どれだけ多いか。

解法

Nが2^kのケースを考える。
スキルを用いないと得られる名声の総和は2^k+2^(k-1)+2^(k-2)...+1 = 2^(k+1)-1である。
一方最初にスキルを用いると2^(k+1)得られる。
この事実より、最初にスキルを用いると1余分にスキルを得られる。

上記考察より、答える値はNを2進数表記したときの1のbitの数と同じであることがわかる。
ただ、入力が大きく入力をまじめに2進数に基数変換を実装しようとすると辛い。

…他の回答者があっさり解いているのを見て、Pythonの機能を使ったら簡単に解けてしまいました。
こんなんでいいのかなぁ…。

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

まとめ

基数変換はまじめに1度練習しておいた方がいいのかな。

広告を非表示にする