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 のように表現できることが分かる。

これを実装したのが以下

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#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);  } }

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