Codeforces #564 Div1 A. Nauuo and Cards

ほとんどレート変動しなかった回。
https://codeforces.com/contest/1172/problem/A

問題

2N枚のカードで行うゲームを考える。
うちN枚は1～Nの数字が書いてあるカードが1枚ずつあり、残りN枚は何も書かれていない。

2N枚のうちN枚はプレイヤーが保持しており、残りはキューに積まれている。
1ターン毎に、プレイヤーは手持ちのカードのうち好きな1枚をキューの末尾に追加し、先頭のカードを手持ちに加える、ということを行う。
キュー内のカードを1～Nのカードが昇順に来るようにするには、最短で何回処理をすればよいか。

解法

1～Nのカードをすべて一旦手持ちを経由されるとすると、各カード最短で何ターン後に所定の位置に移動できるか考える。
各カードをキューに入れるタイミングは異なるので、カード同士が衝突することはないため、上記値の最大値がまず1つ解の候補になる。

あとは、すでにキューにあるカードが手持ちに来る前に終わるケースを求めよう。
これはキュー内で1のカード以降、数がインクリメントされる順に並んでいて、かつ1より手前にあるカードは速く手元に来て適切なタイミングでキューに追加できるか判定すればよい。

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

int F[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		F[A[i]]=1;
	}
	FOR(i,N) {
		cin>>B[i];
		if(B[i]) {
			F[B[i]]=i+2;
		}
	}
	
	int ma=0;
	for(i=1;i<=N;i++) {
		ma=max(ma,F[i]+(N-i));
	}
	
	if(F[1]>1) {
		int cand=F[1]-2;
		int ok=1;
		for(i=1;i<=N;i++) {
			if(F[i]==1) {
				if(N-(cand-1)>i) ok=0;
			}
			else {
				if(F[i]>F[1] && F[i]!=F[1]+(i-1)) ok=0;
				if(F[i]<F[1]) {
					if(N-(cand-F[i])>i) ok=0;
				}
			}
		}
		if(ok) ma=min(ma,cand);
	}
	cout<<ma<<endl;
	
}

まとめ

これは色んな実装法がありそうだね。