kmjp's blog

競技プログラミング参加記です

Codeforces #1031 : Div2 D. Cheater

不参加だった回。
https://codeforces.com/contest/2113/problem/D

問題

1~2Nの番号が書かれたカードが1枚ずつあり、プレイヤーとディーラーににN枚ずつ山として渡される。

以下の手順をN回行うゲームを行う。

  • 両者の山の最上段のカードの番号を比較し、大きい番号を持つカードを山から取り除き、そのカードを持つ側に1ポイントを与える。

プレイヤーは1回だけ2枚のカードの位置を入れ替えられる場合、ポイントの最大値を求めよ。

解法

解Pを二分探索する。
プレイヤーのカードの先頭P毎の最小値が、ディーラーのカードの(N-P+1)枚の最小値より大きければよいため、違反するカードを1回だけスワップして追い出せるか判定すればよい。

int T,N;
int A[202020],B[202020];

int hoge() {
	int i,x,y;
	for(i=x=y=0;i<N;i++) {
		if(A[x]>B[y]) x++;
		else y++;
	}
	return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		
		int L=hoge();
		int R=N;
		while(R-L>1) {
			int M=(L+R)/2;
			x=0;
			FOR(i,M) if(A[i]<A[x]) x=i;
			y=N-1;
			for(i=N-2;i>=M;i--) if(A[i]>A[y]) y=i;
			swap(A[x],A[y]);
			if(hoge()>=M) {
				L=M;
			}
			else {
				R=M;
			}
			swap(A[x],A[y]);
		}
		cout<<L<<endl;
	}
}

まとめ

Editorialもえらく短いね。