Codeforces #694 Div1 C. Strange Shuffle

この回よく見たら割とすんなり4完してるな。
https://codeforces.com/contest/1470/problem/C

問題

N人の人が円形に並んでいる。
各人初期状態でK枚のカードを持っている。

1ターンごとに、各人カードの半分は左側、残り半分を右側の人に同時に手渡す（カード枚数が奇数の場合、右の人に多く渡す）。
ただし1名だけ、常に全カードを右側の人に渡す人がいる。

1回クエリを実行すると、1人指名してカード枚数を聞き出すことができる。
ただし、その都度直後に1回カード交換のターンが生じる。

1000ターン以内に、常に全カードを右側の人に渡す人を特定せよ。

解法

実験すると、mターン後には常に全カードを右側の人m人がK枚より多く、左側の人m人がK枚より少ないカードを持つ。
そこで、√Nターンほど過ごしてから、√N人おきにカード枚数を聞いて回ろう。
そうすると、必ずK枚より多い人とK枚より少ない人を特定できる。

あとは二分探索などで、その間にいるK枚ピッタリの人を特定しよう。

int N,K;
int P=-1;

int A[101010];
int B[101010];
int C[101010];

void turn() {
	int i;
	FOR(i,N) B[i]=0;
	FOR(i,N) {
		if(i==P-1) {
			B[(i+1)%N]+=A[i];
		}
		else {
			B[(i+N-1)%N]+=A[i]/2;
			B[(i+1)%N]+=(A[i]+1)/2;
		}
	}
	FOR(i,N) A[i]=B[i];
}


int ask(int q) {
	int num;
	q=q%N;
	if(P==-1) {
		cout<<"? "<<(q+1)<<endl;
		cin>>num;
	}
	else {
		num=A[q];
		turn();
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) A[i]=K;
	
	FOR(i,350) ask(0);
	FOR(i,350) {
		C[i*N/350]=ask(i*N/350);
	}
	
	int ma=0,mai=0;
	int mi=K+1,mii=0;
	FOR(i,N) {
		if(C[i]>ma) ma=C[i],mai=i;
		if(C[i]>0&&C[i]<mi) mi=C[i],mii=i;
	}
	if(mai<mii) mai+=N;
	
	if(mii+200<mai) {
		x=ask((mai+mii)/2);
		if(x>=ma) mai=(mai+mii)/2;
		else mii=(mai+mii)/2-1;
	}
	
	for(i=mai;i>=mii;i--) {
		if(ask(i)==K) {
			cout<<"! "<<(i%N+1)<<endl;
			break;
		}
	}
	
	
}

まとめ

頭で考えると難しいが、実験するとすぐわかる問題。