AtCoder ARC #154 : D - A + B > C ?

本番中に詰め切れず…。
https://atcoder.jp/contests/arc154/tasks/arc154_d

問題

正整数Nが与えられる。そのうえで1～NのPermutation Pを当てるインタラクティブ問題である。
1回のクエリでは、3要素i,j,kを指定し、P[i]+P[j]＞P[k]かどうかを得ることができる。
このクエリを25000回まで用いてPを特定せよ。

解法

i,j,kは同じものを指してもよい。
よってP[i]+P[i]＞P[k]となるkが存在しない場合、P[i]=1である。
まずO(N)回上記クエリを用いて、P[i]=1となるiを特定しよう。

P[i]+P[j]＞P[k]について、P[i]=1であるなら、結局P[j]＞P[k]を聞くのと変わらない。
よって、残った要素についてマージソートの要領でソートして行けばよい。

int N;
int P[2525];
int re[2525];

int Q[2525];
int cnt;

int ask(int a,int b,int c) {
	
	cnt++;
	if(Q[0]||Q[1]) {
		return Q[a]+Q[b]>Q[c];
	}
	else {
		cout<<"? "<<a+1<<" "<<b+1<<" "<<c+1<<endl;
		string s;
		cin>>s;
		return s=="Yes";
	}
}

int more(int a,int b) {
	return ask(a,re[1],b);
}

void ans() {
	cout<<"!";
	int i;
	FOR(i,N) cout<<" "<<P[i];
	cout<<endl;
	cerr<<"$ ";
	FOR(i,N) cerr<<" "<<Q[i];
	cerr<<endl;
	//assert(cnt<25000);
	cerr<<cnt<<endl;
	if(Q[0]||Q[1]) {
		FOR(i,N) assert(P[i]==Q[i]);
	}
	exit(0);
}

vector<int> merge(vector<int> A,vector<int> B) {
	vector<int> R;
	int a=0,b=0;
	while(a<A.size()||b<B.size()) {
		if(a<A.size()&&b<B.size()) {
			if(more(A[a],B[b])) {
				R.push_back(B[b++]);
			}
			else {
				R.push_back(A[a++]);
			}
		}
		else if(a<A.size()) {
			R.push_back(A[a++]);
		}
		else {
			R.push_back(B[b++]);
		}
	}
	return R;
}

void solve() {
	int i,j,k,l,r,x,y; 
	MINUS(re);
	cin>>N;
	
	//FOR(i,N) Q[i]=i+1;
	random_shuffle(Q,Q+N);
	
	//1を求める
	int f=0;
	for(i=1;i<N;i++) {
		x=ask(i,i,f);
		if(x==0) f=i;
	}
	
	P[f]=1;
	re[1]=f;
	
	queue<vector<int>> Q;
	FOR(i,N) if(i!=f) {
		Q.push({i});
	}
	while(Q.size()>1) {
		auto a=Q.front();
		Q.pop();
		auto b=Q.front();
		Q.pop();
		Q.push(merge(a,b));
	}
	auto v=Q.front();
	FOR(i,N-1) P[v[i]]=i+2;
	
	
	ans();
}

まとめ

マージソートに持ち込むの思いつかなかった…。