CSAcademy Round #27 : F. Triplet Queries

これは思いつかないな…。
https://csacademy.com/contest/round-27/task/triplet-queries/

問題

N個の異なる整数列Aがあり、その各要素を求めたい。
整数列中3つのindexを指定すると、最小値と最大値の和を返すクエリを最大min(2*N,N+50)回用いて整数列を復元せよ。

解法

N＜5の時、このクエリが返す値の種類はN通り未満なので復元不可。
それ以外の場合、まずは先頭5要素についてあり得る10通りの組み合わせを問い合わせてしまおう。
５つの値を仮にA[a]＜A[b]＜A[c]＜A[d]＜A[e]としたとき、クエリの結果は下記の通り。

• Q(a,b,c)=A[a]+A[c]
• Q(a,b,d)=A[a]+A[d]
• Q(a,b,e)=A[a]+A[e]
• Q(a,c,d)=A[a]+A[d]
• Q(a,c,e)=A[a]+A[e]
• Q(a,d,e)=A[a]+A[e]
• Q(b,c,d)=A[b]+A[d]
• Q(b,c,e)=A[b]+A[e]
• Q(b,d,e)=A[b]+A[e]
• Q(c,d,e)=A[c]+A[e]

A[a]+A[e]とA[b]+A[d]の大小関係はわからないが、それ以外のクエリ結果の大小関係は一意に決まる。
よって、先頭5要素の大小関係のうち、このクエリ結果と矛盾しないものを1つ求めよう。
これは大小関係を5!総当たりすればよい。
大小関係が求められれば、上記値からa～eの値を求められる。

ここから、残りの要素を求めていこう。
A[i]を求めるためには、Q(a,b,i)を問い合わせればよい。
A[i]＜A[a]またはA[b]＜A[i]なら、この結果はA[a]+A[b]以外のものが返るのでA[i]が求まる。
仮にA[a]＜A[i]＜A[b]の場合、改めてQ(b,c,i)を求めればA[i]＜A[b]＜A[c]なのでA[i]+A[c]を得ることができ、A[i]がわかる。

この手順だけだと、１つの要素を求めるのに2回クエリが必要となり、(N+50)回を超過する恐れがある。
しかし、仮にA[a]＜A[i]＜A[b]となるiが見つかってしまった場合、以後最初に判定するのに使う2要素を(a,b)の代わりに(a,i)または(i,b)のうち要素の差が小さい方とすればよい。
こうするとA[a]とA[b]の差は1回ごとに半分以下になるため、２回クエリが必要となるのはlog(max(A))回にとどまる。

int N;
ll ret[101010];

int ask(int a,int b,int c) {
	int x;
	_P("Q %d %d %d\n",a+1,b+1,c+1);
	fflush(stdout);
	scanf("%d",&x);
	return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	scanf("%d",&N);
	if(N<5) return _P("A -1\n");
	
	map<vector<int>,int> M;
	vector<vector<int>> V={{0,1,2},{0,1,3},{0,1,4},{0,2,3},{0,2,4},
	                       {0,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}};
	int mi=2000000000,ma=0;
	FORR(r,V) {
		x = ask(r[0],r[1],r[2]);
		M[{r[0],r[1],r[2]}]=x;
		M[{r[0],r[2],r[1]}]=x;
		M[{r[1],r[0],r[2]}]=x;
		M[{r[1],r[2],r[0]}]=x;
		M[{r[2],r[0],r[1]}]=x;
		M[{r[2],r[1],r[0]}]=x;
		mi=min(mi,x);
		ma=max(ma,x);
	}
	
	vector<int> O={0,1,2,3,4};
	int A,B,C;
	do {
		if(M[{O[0],O[1],O[2]}]!=mi) continue;
		if(M[{O[2],O[3],O[4]}]!=ma) continue;
		if(M[{O[0],O[1],O[2]}]>=M[{O[0],O[1],O[3]}]) continue;
		if(M[{O[0],O[1],O[3]}]>=M[{O[0],O[1],O[4]}]) continue;
		if(M[{O[0],O[2],O[3]}]>=M[{O[1],O[2],O[3]}]) continue;
		if(M[{O[1],O[2],O[3]}]>=M[{O[1],O[2],O[4]}]) continue;
		if(M[{O[1],O[2],O[4]}]>=M[{O[2],O[3],O[4]}]) continue;
		if(M[{O[1],O[3],O[4]}]>=M[{O[2],O[3],O[4]}]) continue;
		
		A=O[0];
		B=O[2];
		C=O[4];
		ret[A]=(M[{O[0],O[1],O[2]}]+M[{O[0],O[2],O[4]}]-M[{O[2],O[3],O[4]}])/2;
		ret[B]=(M[{O[0],O[1],O[2]}]+M[{O[2],O[3],O[4]}]-M[{O[0],O[2],O[4]}])/2;
		ret[C]=(M[{O[2],O[3],O[4]}]+M[{O[0],O[2],O[4]}]-M[{O[0],O[1],O[2]}])/2;
		ret[O[1]]=M[{O[1],O[2],O[4]}]-ret[C];
		ret[O[3]]=M[{O[0],O[1],O[3]}]-ret[A];
		
		break;
		
	} while(next_permutation(ALL(O)));
	
	FOR(i,N) if(ret[i]==0) {
		x = ask(A,B,i);
		if(x==ret[A]+ret[B]) {
			x = ask(B,C,i);
			if(x<ret[B]+ret[C]) {
				ret[i]=x-ret[C];
			}
			else {
				ret[i]=x-ret[B];
			}
			
			if(ret[i]-ret[A]<ret[B]-ret[i]) B=i;
			else A=i;
			
		}
		else if(x<ret[A]+ret[B]) {
			ret[i]=x-ret[B];
		}
		else {
			ret[i]=x-ret[A];
		}
	}
	
	_P("A");
	FOR(i,N) _P(" %lld",ret[i]);
	_P("\n");
	
}

まとめ

これだけいろんなテクニックを使うのはすぐに思いつかないよなぁ。