No.381

No.378 の制限が厳しいバージョンである.

名声値を半分にして足していくということは, 右シフトを繰り返しながら足していくことになる.

$N$ の立っている第 $i$ ビットに注目すると, このビットだけ立っている数値が最初の名声値だった場合, 合計は

$$2^i + 2^{i-1} + \dots + 2^0 = 2^{i+1}-1$$

となり, 最初の名声値が $N$ のとき, $N$ の立っているビットの数を $B(n)$ とすると, 合計は

$$2N - B(n)$$

となる. よって最初にそのキャラクターを使った場合に余分にもらえる名声値は,

$$2N - (2N - B(n)) = B(n)$$

となり, 立っているビットの数を数えればいいことになる. また余分にもらえる名声値の最大値は明らかに最初にそのキャラクターを使った場合である.

数が巨大なので, GMP に逃げた.