Google Code Jam 2019 Round 1B : B. Draupnir

ほんとミスが多いなぁ。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122837

問題

X-day指輪は、0日目にR[x]個あった場合、y日目にはR[x]*2^(floor(y/x))個になっている。

1-day～6-dayの指輪があり、それぞれ0日目の個数は100以下である。
以下のクエリを最大2回まで投げ、0日目の個数を特定せよ。

• 日付Dを指定すると、D日目における(全指輪の総数 mod 2^63)が返る。

解法

初期状態の指輪の個数が最大100個<128=2^7なので、互いにシフト回数が7回以上離れるようなDを指定すると、指輪の数が特定できる。
ただ、大きすぎるDを指定すると、オーバーフローしてしまう。

そこでまずR(4),R(5),R(6)を特定しよう。
D=210を投げると、1-day～3-dayの指輪の個数はオーバーフローして無視できるようになる。
返り値はR(4)*(2^52)+R(5)*(2^42)+R(6)*(2^35)なので、この3つの値がわかる。

次に、R(1),R(2),R(3)を求めるようなクエリを投げよう。
D=40を投げると、返り値はR(1)*(2^40)+R(2)*(2^20)+R(3)*(2^13)+R(4)*(2^10)+R(5)*(2^8)+R(6)*(2^6)となる。
R(4),R(5),R(6)はわかっているのでその分を引くと、R(1),R(2),R(3)はシフト回数が7回以上離れているのでそれぞれ特定できる。

int W;
ll R[7];
ll V;
ll X[7],D;

map<pair<ll,ll>,vector<int>> M;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	M.clear();
	
	cout<<210<<endl;
	cin>>V;
	
	R[6]=(V>>35)%128;
	R[5]=(V>>42)%128;
	R[4]=(V>>52)%128;
	
	cout<<40<<endl;
	cin>>V;
	
	V-=R[6]<<6;
	V-=R[5]<<8;
	V-=R[4]<<10;
	R[3]=(V>>13)%128;
	R[2]=(V>>20)%128;
	R[1]=(V>>40)%128;
	
	cout<<R[1]<<" "<<R[2]<<" "<<R[3]<<" "<<R[4]<<" "<<R[5]<<" "<<R[6]<<endl;
	cin>>x;
	assert(x==1);
	
}

まとめ

GCJのInteractiveはなんかツールが動かないときのデバッグがしんどくて嫌い…。