CodeForces #564 Div2 C. Nauuo and Cards

Problem - C - Codeforces

概要

N項の数列a, bがある。a, bに含まれる要素はあわせて2N個であるが、このうちN個は1からNまでの整数で、うちN個は全て0である。

aを手札、bを山札とし、次の操作を繰り返す。

• 手札から1枚選び、山札の底に入れる。その後、山札の1番上の札を手札に入れる。

この操作を繰り返し、山札を1, 2, …, Nとなるようにするとき、最小の操作回数を求めよ。

制約

1 ≦ N ≦ 2 * 10^5

方針

場合分け。

①山札が*****123のようになっており、その続きを手札から挿入することで12...Nの並びを完成できる場合
実際にシミュレーションして可能ならば、その回数を出力する。

②山札が全て0の場合
nを出力する

③上記以外
山札の中の0以外のカードは、早くとも引いた次の操作でないと山札の底に挿入できない。
よって、最小の操作回数は、山札の中の0以外の各カードについて、「そのカードを引いた次の操作に山札に入れたとしたときの操作数」を計算し、その最大値以上となる。ただし、少なくともn回の操作は必要なので、nとのmaxをとる必要がある。

感想

全てのケースを網羅することが難しく、コンテスト後のサンプルが分かる状態でも、
何度もWAを出してしまいました。

解答

Submission #55543591 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int n;
vector<int> a;
vector<int> b;

int lucky(){
	int idx = -1;
	for(int i = 0; i < n; i++){
		if(b[i] == 1){
			idx = i;
		}
	}

	if(idx == -1) return -1;

	for(int i = idx; i < n; i++){
		if(b[i] != i - idx + 1) return -1;
	}

	set<int> st;
	for(int i = 0; i < n; i++){
		st.insert(a[i]);
	}

	for(int i = 0;i < idx; i++){
		int t = n - idx + i + 1;
		auto itr = st.find(t);
		if(itr == st.end()){
			return -1;
		}
		st.insert(b[i]);
	}

	return idx;
}

int pileall0(){
	for(int i = 0; i < n; i++){
		if(b[i] > 0) return -1;
	}
	return n;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> n;
	a.resize(n);
	b.resize(n);

	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];

	int idx = lucky();
	if(idx != -1){
		cout << idx << endl;
		return 0;
	}

	idx = pileall0();
	if(idx != -1){
		cout << idx << endl;
		return 0;
	}
	int ans = n;
	for(int i = 0; i < n; i++){
		if(b[i] > 0){
			int t = (i + 1) + 1 + (n - b[i]);
			ans = max(ans, t);
		}
	}

	cout << ans << endl;
}