Mail.Ru Cup 2018 Round 3 : C. Pick Heroes

Dより難しくない？
http://codeforces.com/contest/1056/problem/C

問題

2N個の整数を、2人で交互に取り合うInteractive問題である。
取った整数の総和をできるだけ大きくしたい。
なお、一部の整数はペアになっており、片方がペアのいずれかを取ると、次のターンで相手はペアの反対側を取らなければならない。
自分の取ることのできる最適手を答えよ。

解法

相手がペアの片方を取ってきた場合、しょうがないので自分はもう片方を取る。
それ以外には、

• ペアが余っていたら、ペアのうち大きい方を取る。そうすると相手の取る手は固定されるので、実質相手に選択権を取らせず自分だけ好きなものを取り続けることができる。
• ペアがなくなったら、あとは大きい順に取る。

int N,M,T;
int A[2020];
int O[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,2*N) cin>>A[i+1];
	FOR(i,M) {
		cin>>x>>y;
		O[x]=y;
		O[y]=x;
	}
	cin>>T;
	int F=T;
	FOR(j,N) {
		if(T==2) {
			cin>>x;
			A[x]=-1;
			if(O[x]&&A[O[x]]>=1) {
				cout<<O[x]<<endl;
				A[O[x]]=-1;
				continue;
			}
			T=1;
		}
		
		vector<pair<int,int>> V;
		
		for(i=1;i<=2*N;i++) if(A[i]>0) {
			if(O[i]==0) {
				V.push_back({A[i],i});
			}
			else if(A[i]>A[O[i]] || (A[i]==A[O[i]] && i<O[i])) {
				break;
			}
		}
		
		
		if(i<=2*N) {
			cout<<i<<endl;
			A[i]=-1;
		}
		else {
			assert(V.size());
			sort(ALL(V));
			reverse(ALL(V));
			cout<<V[0].second<<endl;
			A[V[0].second]=-1;
			
		}
		T=2;
	}
	
	if(F==1) {
		cin>>x;
	}
	
}

まとめ

Dの方がとっつきやすい…。