Hello 2023 : E. Anya's Simultaneous Exhibition

明けましておめでとうございます？
https://codeforces.com/contest/1779/problem/E

問題

N人のチェス大会を考える。
2人の選手間では勝ち負けが確定する。
この勝ち負けは推移律は成り立つとは限らない。

彼らで(N-1)試合からなる勝ち抜きトーナメント戦を考える。
もし試合順次第で最後勝者になりうる選手は、candidate masterと呼ぶ。

以下のクエリを2N回用いて、candidate masterを列挙せよ。

• 1人選手を選び、対戦相手を任意の数選ぶ。すると、最初に選んだ選手が、対戦相手に何勝できるかが返る。

解法

総当たりしたとき最多勝利できる人は、candidate masterである。
まずこれをN手クエリを行う。
あとは勝利数の多い順に、candidate masterの誰かに勝てるかどうかを順にみて行けばよい。

int N;
int ask(int t,vector<int> V) {
	cout<<"? "<<t+1<<" ";
	int i;
	FOR(i,N) cout<<count(ALL(V),i);
	cout<<endl;
	cin>>t;
	return t;
}
void ans(vector<int> V) {
	cout<<"! ";
	FORR(v,V) cout<<v;
	cout<<endl;
	exit(0);
}

vector<int> vis;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vis.resize(N);
	vector<int> C;
	C={0};
	for(i=1;i<N;i++) {
		k=ask(i,C);
		C.insert(C.begin()+((int)C.size()-k),i);
	}
	vis[C[0]]=1;
	for(i=1;i<N;i++) {
		vector<int> cand;
		FOR(x,i) if(vis[C[x]]) cand.push_back(C[x]);
		k=ask(C[i],cand);
		if(k) {
			FOR(x,i+1) vis[C[x]]=1;
		}
	}
	ans(vis);
	
}

まとめ

本番だいぶてこずってるなぁ。