問題C. ビット数 - めもめも

本番中はlarge解けなかった。考え直したら解けたっぽいのでメモ書き残す。
aとbを二進数表記したときのビットをそれぞれAn, Bnと表し、それぞれの
桁のCarryをCnと表す。Nを二進数表記したものをNnと表す。
このときan+bn+Cn=NnをAnとBnがなるべく多く立っているように満たす組み合わせでカウントする。

     An ... A2 A1 A0
+) Bn ... B2 B1 B0
+) Cn ... C2 C1  C0
-----------------
    Nn ... N2 N1  N0

方針としてCarryがない場合とある場合で考える。

Carryがない場合(Cn=0)）

(a) Nnが0のときの組み合わせ候補は(An, Bn, Cn) = {(0, 0, 0), (1, 1, 0)}である。最も多くビットが立っているAnとBnの組み合わせは(1,1,0)が選択され、立っているビット数は+2される。さらにこのときCarryが立つ。
(b) Nnが1のときの組み合わせ候補は(An, Bn, Cn) = {(1, 0, 0), (0, 1, 0)}である。どちらの組み合わせを選んでもよい.立っているビット数は+1.

Carryがある場合(Cn=1))

(a)Nnが0のときの組み合わせ候補は(An, Bn, Cn) = {(1, 0, 1), (0, 1, 1)}である。どちらの組み合わせを選んでもよい.立っているビット数は+1.このときCarryは立つ。
(b)
(b-1. Nnが最上位ビットでない場合)
Nnが1のときの組み合わせ候補は(An, Bn, Cn) = {(0, 0, 1), (1, 1, 1)}である。
最も多くビットが立っているAnとBnの組み合わせとして(1,1,1)が選択され、立っているビット数は+2される。さらにこのときCarryが立つ。
(b-2. Nnが最上位ビットの場合)
Nnが1のときの組み合わせ候補は(An, Bn, Cn) = {(0, 0, 1)}である。最上位ビットなのでCarryが立てられないためである。よって立っているビット数+0.

具体例としてN=5のケースで考えてみる。

     a2 a1 a0
+) b2 b1 b0
+)    ?   ?    0
-----------------
      1   0    1

Nを下位ビットからひとつずつみていく。n0=1となる組み合わせは(a0, b0, c0) = {(1, 0, 0), (0, 1, 0)}なのでbit0の最も多く立っているビット数は1.このときはCarryは発生しないのでc1=0となる。

     a2 a1 a0
+) b2 b1 b0
+)    ?   0   0
-----------------
      1   0    1

n1=0となる組み合わせは(a1, b1, c1) = {(1, 1, 0)}なのでbit1の最も多く立っているビット数は2.
このときCarryが発生するため、c2=1となる。

     a2 a1 a0
+) b2 b1 b0
+)    1   0   0
-----------------
      1   0    1

n2 = 1となる組み合わせは(a2, b2, c2) = {( 0, 0, 1), (1, 1, 1)}である。通常であれば、最も多く立っているビット数は2.ただし最上位ビットなので(1,1,1)の組み合わせは存在しない。よって(0, 0, 1) なので最も多く立っているビット数は0となる。

以上から各桁に関して最も多く立っているビット数の和は1+2+0=3

上記の内容を愚直に書いたこーど

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int solve(ll N) 
{
    int ret = 0;
    bool carry = false;
    
    while(N) {
        int x;
        if(carry) {
            if(N & 1) { x = 2; carry = true; }
            else      { x = 1; carry = true; }
        } else {
            if(N & 1) { x = 1; }
            else      { x = 2; carry = true; }
        }
        ret += x; 
        N >>= 1;
    }
    if(carry) ret -= 2;

    return ret;
}

int main()
{
    int T;

    scanf("%d", &T);
    for(int i = 1; i <= T; i++) {
        ll N;
        scanf("%lld", &N);
        cout << "Case #" << i << ": " << solve(N) << endl;

    }

}