kmjp's blog

競技プログラミング参加記です

yukicoder : No.1959 Prefix MinMax

これは賢い。
https://yukicoder.me/problems/no/1959

問題

1~Nの順列Pを特定するインタラクティブ問題である。
0/1で構成され長さN-1の数列Aを指定すると、下記数列Bが返る。
このクエリを10回まで用いて、Pを特定せよ。

  • B[0]=P[0]
  • B[i+1]=max(B[i],P[i]) (A[i]==0の場合)
  • B[i+1]=min(B[i],P[i]) (A[i]==1の場合)

解法

B[i]!=B[i+1]の場合B[i+1]=P[i]となる。
この状態を作るには、A=(0,1,0,1,...)と(1,0,1,0,....)と2種類のクエリを投げれば、各添え字について、いずれかの返り値でB[i]!=B[i+1]となるBが得られる。

int T,N;
int A[1010],B[1010],C[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<"?";
		FOR(i,N-1) {
			cout<<" "<<(i%2);
		}
		cout<<endl;
		FOR(i,N) cin>>A[i];
		cout<<"?";
		FOR(i,N-1) {
			cout<<" "<<((i%2)^1);
		}
		cout<<endl;
		FOR(i,N) cin>>B[i];
		C[0]=A[0];
		for(i=1;i<N;i++) {
			if(A[i]!=A[i-1]) C[i]=A[i];
			if(B[i]!=B[i-1]) C[i]=B[i];
		}
		cout<<"!";
		FOR(i,N) cout<<" "<<C[i];
		cout<<endl;
	}
}

まとめ

クエリ回数がO(logN)ぐらいかかるように見えて、O(1)というのがいいね。