yukicoder No.378 名声値を稼ごう

問題

問題概要

省略

解法

星1だし単純な規則性がありそう。少し実験したら、2回目にキャラクターを利用した時が最大になりそうなことが分かった。数学で証明できると思いますが、わかりません。

ミス

なし

コード

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    ll n; cin >> n;
    ll tmp = n;
    ll an1 = 0, an2 = 2 * n;
    while(tmp > 0){
        an1 += tmp; tmp /= 2;
    }

    if(an2 - an1 >= 0) printf("%d\n", an2 - an1);
    else printf("%d\n", an1 - an2);
    return 0;
}