Codeforces #882 : Div2 E. Triangle Platinum?

結構考察めんどいな。
https://codeforces.com/contest/1847/problem/E

問題

1～4で構成されるN要素の数列Aを求めるinteractive問題である。
3つの添え字(i,j,k)を指定すると、3辺A[i],A[j],A[k]の三角形が成立するか、またその面積が与えられる。
このクエリをN+500回まで使用し、Aを特定せよ。

解法

Nが少ないときは適当に総当たりすればよい。

先頭9個を総当たりすると、鳩ノ巣原理からうち3つは等しい長さを持つ。
その長さが2以上の場合、そのうち2辺と、他の残り(N-3)辺のうち1辺を指定すれば、残り1辺の長さを特定できる。
もしその長さが1の場合、そのうち2辺と、他の残り(N-3)辺のうち1辺を指定すれば、その1辺が1かどうか判定できるので、いずれ2,3,4の辺を2辺見つけられる。

int A[5][5][5];
int N;
int ret[5050];
string B="";

int ask(int a,int b,int c) {
	if(a>b) swap(a,b);
	if(b>c) swap(b,c);
	if(a>b) swap(a,b);
	cout<<"? "<<(a+1)<<" "<<(b+1)<<" "<<(c+1)<<endl;
	if(B.size()) return A[B[a]-'0'][B[b]-'0'][B[c]-'0'];
	cin>>a;
	return a;
}

void slow() {
	int R[9][9][9];
	int a,b,c;
	FOR(a,N) for(b=a+1;b<N;b++) for(c=b+1;c<N;c++) {
		R[a][b][c]=ask(a,b,c);
	}
	
	int mask,i;
	int B[9],C[9];
	int ok=0;
	FOR(mask,1<<(2*N)) {
		FOR(i,N) B[i]=(mask>>(2*i))%4+1;
		int ng=0;
		FOR(a,N) for(b=a+1;b<N;b++) for(c=b+1;c<N;c++) if(R[a][b][c]!=A[B[a]][B[b]][B[c]]) ng=1;
		if(ng==0) {
			ok++;
			FOR(a,N) C[a]=B[a];
		}
	}
	
	if(ok==1) {
		cout<<"!";
		FOR(a,N) cout<<" "<<C[a];
		cout<<endl;
	}
	else {
		cout<<"! -1"<<endl;
	}
	
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(x=1;x<=4;x++) {
		for(y=1;y<=4;y++) {
			for(k=1;k<=4;k++) {
				if(k>=y+x) continue;
				if(y>=x+k) continue;
				if(x>=y+k) continue;
				int s=x+y+k;
				A[x][y][k]=s*(s-2*x)*(s-2*y)*(s-2*k);
			}
		}
	}
	
	cin>>N;
	
	if(N<9) {
		slow();
	}
	int a[5][3]={};
	MINUS(a);
	int t=0;
	FOR(x,9) for(y=x+1;y<9;y++) for(k=y+1;k<9;k++) {
		i=ask(x,y,k);
		for(j=1;j<=4;j++) if(i==A[j][j][j]) {
			t=j;
			a[t][0]=x,a[t][1]=y,a[t][2]=k;
			ret[x]=ret[y]=ret[k]=t;
		}
	}
	
	if(t==1) {
		vector<int> C;
		int A0=a[t][0];
		int A1=a[t][1];
		FOR(i,N) if(t==1&&ret[i]==0) {
			x=ask(A0,A1,i);
			if(x!=0) {
				ret[i]=1;
			}
			else {
				FORR(c,C) {
					y=ask(A0,i,c);
					if(y==A[1][2][2]) t=2;
					if(y==A[1][3][3]) t=3;
					if(y==A[1][4][4]) t=4;
					if(t>1) {
						a[t][0]=i;
						a[t][1]=c;
						ret[i]=ret[c]=t;
						break;
					}
				}
				if(t>1) break;
				C.push_back(i);
			}
		}
	}
	
	if(t!=1) {
		int A0=a[t][0];
		int A1=a[t][1];
		FOR(i,N) if(ret[i]==0) {
			y=ask(i,A0,A1);
			FOR(j,4) if(A[t][t][j+1]==y) ret[i]=j+1;
		}
	}
	FOR(i,N) if(ret[i]==0) {
		cout<<"! -1"<<endl;
		return;
	}
	cout<<"!";
	FOR(i,N) cout<<" "<<ret[i];
	cout<<endl;
	
}

まとめ

方針はともかくコードが長くなるな…。