Codeforces #712 Div1 : D. Flip the Cards

本番はてこずったけど何とか通してるな。
https://codeforces.com/contest/1503/problem/D

問題

N枚のカードがあり、表裏それぞれ整数が書かれている。
計2N個の面に、1～2Nの値が1枚ずつ書かれている。

カードを任意の順で並べ、かつ任意枚数裏返すことを考える。
カードを並べた順に、表面の値が昇順で、かつ裏面の値が降順に並ぶようにしたい。
可能なら、最小何枚裏返す必要があるか求めよ。

解法

まず前提として、表面と裏面どちらかがN以下でどちらかが(N+1)以上でなければならない。
これは、カード列を見ると途中まで表面の値が小さく、途中から表面の値の方が大きくなることを考える。
いずれも小さい方の値に着目すると、それらはN以下でなければいけないことがわかる。

カードを外側から置いていくことを考える。
仮に残ったカードのうち最小値のものを表向きにして左側に置いた場合、自動的に何枚か左右に置くべきカードが確定する場合がある。
これら全体を、左右逆にする場合、表裏を逆にしておくことになるので、裏返す枚数が少なくなる方を選ぼう。

あとは上記処理を丁寧に行っていくだけ。

int N;
int A[202020],B[202020];
int rev[404040],op[404040];
set<int> H,L;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		x=(A[i]<=N)+(B[i]<=N);
		if(x!=1) return _P("-1\n");
		A[i]--,B[i]--;
		rev[A[i]]=i;
		rev[B[i]]=i+N;
		op[A[i]]=B[i];
		op[B[i]]=A[i];
		H.insert(i+N);
		L.insert(i);
	}
	
	pair<int,int> X,Y;
	X={-1,2*N+1};
	Y={-1,2*N+1};
	int ret=0;
	while(L.size()) {
		x=*L.begin();
		y=*H.rbegin();
		if(op[x]==y) {
			L.erase(x);
			H.erase(y);
			
			if(x<X.first||x>Y.second) return _P("-1\n");
			if(y>X.second||y<Y.first) return _P("-1\n");
			X=Y={x,y};
			
			continue;
		}
		
		if(x<X.first||op[y]<Y.first) return _P("-1\n");
		if(op[y]>X.second||y>Y.second) return _P("-1\n");
		
		
		int same=0,flip=0;
		L.erase(x);
		L.erase(op[y]);
		H.erase(y);
		H.erase(op[x]);
		X={x,op[x]};
		Y={op[y],y};
		if(rev[x]>=N) flip++;
		else same++;
		if(rev[y]>=N) flip++;
		else same++;
		int up=1;
		
		while(up&&L.size()) {
			up=0;
			x=*L.begin();
			y=*H.rbegin();
			if(x<X.first&&x<Y.first) return _P("-1\n");
			if(x>X.first&&x<Y.first) {
				if(op[x]>X.second) return _P("-1\n");
				L.erase(x);
				H.erase(op[x]);
				X={x,op[x]};
				if(rev[x]>=N) flip++;
				else same++;
				up=1;
				continue;
			}
			if(x<X.first&&x>Y.first) {
				if(op[x]>Y.second) return _P("-1\n");
				L.erase(x);
				H.erase(op[x]);
				Y={x,op[x]};
				if(rev[x]<N) flip++;
				else same++;
				up=1;
				continue;
			}
			
			if(y>X.second&&y>Y.second) return _P("-1\n");
			if(y<X.second&&y>Y.second) {
				if(op[y]<X.first) return _P("-1\n");
				L.erase(op[y]);
				H.erase(y);
				X={op[y],y};
				if(rev[y]<N) flip++;
				else same++;
				up=1;
				continue;
			}
			if(y>X.second&&y<Y.second) {
				if(op[y]<Y.first) return _P("-1\n");
				L.erase(op[y]);
				H.erase(y);
				Y={op[y],y};
				if(rev[y]>=N) flip++;
				else same++;
				up=1;
				continue;
			}
		}
		ret+=min(flip,same);
	}
	
	cout<<ret<<endl;
	
}

まとめ

方針は定まっても細かいところで苦労。