yukicoder No.378 名声値を稼ごう

問題はこちら
No.378 名声値を稼ごう - yukicoder

スキルを使わない場合にk回目のクリアで得られるポイントをa[k]とする。
a[k+1]≦a[k]/2であることから帰納的にa[k]≦N/2^(k-1)とわかる。
よってとなる。
これより帰納的に、1回目にスキルを使うのが最適であることが分かる。
あとは通常時を実際に計算して比較すれば良い

long n,m,s;
int main(){
	scanf("%ld",&n);
	m=2*n;
	while(n){
		s+=n;
		n/=2;
	}
	printf("%ld",m-s);
	return 0;
}

ところで上で求めた不等式をよくみると、真に不等号が成立するのは、a[k+1]＜a[k]/2となるとき、即ちa[k]が奇数となるときだと分かる。
「2で割って切り捨て」という操作が右bitshiftに対応していることを踏まえると、（bitpop数に関する帰納法などで）結局Nのbitpop数が答えになることが分かる

s;
main(long n){
	for(scanf("%ld",&n);n;n/=2)s+=n&1;
	s=!printf("%d",s);
}

68B
__builtin_popcountという便利関数があるが、これはlongには使えないので、どうしても使いたければ
__builtin_popcount(n)+__builtin_popcount(n>>32)となる。長い
2017/08/02追記
__builtin_popcountllという便利関数がある（が、これを使っても70B）
追記終わり

2016/10/16追記
bitpop数の数え方忘れたんですかねぇ……

long n;
main(s){
	for(scanf("%ld",&n);n&=n-1;)s++;
	n=!printf("%d",s);
}

66B