GCJJ

GCJJに行ってきた。
起きたのが17：50ぐらい。
とりあえず軽くメシ食って、始めたのが18：20分ちょい前ぐらいだったか。

時間がヤバ過ぎたので正解率の高いCを選択。

正の整数Nを、0以上の整数であるa と b を使い

a + b = N

と表す。
f(x)を、xを二進数で表した場合の１の数とし、

f(a) + f(b) = k

のkが最大になる場合のkの値を求めよ。

という問題。
例えば、９ならば、

f(9) + f(0) = 2
f(8) + f(1) = 3
f(7) + f(2) = 4
f(6) + f(3) = 4
f(5) + f(4) = 3

と、それぞれなるので、正解は4となる。

初めは愚直に探索していくのかなと思ったが、largeの制約が N < 10^18だったため、どう考えてもそれでは間に合わない。
二進数ならではの考え方がある。
ビット単位で考えてやると、 10 < 2^4であるから、最大でも4*18 = 72より少ない計算量で達成出来る。

a + b の形になっているので、二進数の特質が大いに生かせそうだ。

暫く考えていたところ、0がキーになっていることが分かった。
11100100111のような場合、右から考えてやって、最初に0が出るまでの1は、aかbどちらかの該当ビットだけに1を設定してやることによってしか表現出来ないが、それ以降の1は、aとbの両方の該当ビット一つ下に１を設定してやることで表現出来そうだ。
これを拡張して、1001001のように0が続いている場合、a = 0111111, b = 0001010 のように表現できることが分かる。

これを実装したのが以下

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <time.h>
using namespace std;

#define REP(i,s,e) for (int i = int(s); i != int(e); i++)
#define rep(i,e) REP(i,0,e)
#define foreach(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
#define ll long long
#define INF 1<<30



int main(){
 unsigned ll n;
 int testCase,bits_after_zero,bits_before_zero,num_zero;
 scanf("%d", &testCase);
 rep(i,testCase)
 {
  bits_after_zero = 0; bits_before_zero = 0; num_zero = 0;
  scanf("%lld", &n);
  do{
   if(n & 1) bits_before_zero++; else{
    n >>= 1;
    break;
   }
  }while( (n >>= 1) > 0);
  do{
   if(!(n > 0)) break;
   if(n & 1) bits_after_zero++; else num_zero++;
  }while( ( n >>= 1 ) > 0);
  printf("Case #%d: %d\n", i+1, bits_after_zero * 2 + bits_before_zero + num_zero);
 }
}

残りの問題は後でまた解く