JOISC20 Building4

문제

oj.uz/problem/view/JOI20_building4

문제 보기 - 건물 4 (JOI20_building4) :: oj.uz

길이 2N의 배열 A와 B가 주어진다. 각 i에 대해, A, B중 정확히 하나씩 골라 만든 길이 2N짜리 수열이 증가 수열이어야 한다. 또한, A를 정확히 N개, B를 정확히 N개 골라야 한다.

이와 같이 고르는 것이 가능한지, 가능하다면 그 예를 하나 보여야 한다.

$N<=5*10^5$

 

풀이

$O(N^2)$의 풀이는 다음과 같다.

$dp1(i, j)=$ i번째까지 선택했고, 마지막 선택은 A이며, 그 중 j개가 A이도록 선택하는 것이 가능한가?

$dp2(i, j)=$ i번째까지 선택했고, 마지막 선택은 B이며, 그 중 j개가 A이도록 선택하는 것이 가능한가?

 

상태 전이는 다음과 같다.

$dp1(i, j)= dp1(i-1, j-1) (A_{i-1}<=A_{i}) || dp2(i-1, j-1) (B_{i-1}<=A_{i})$ 

$dp2(i, j)= dp1(i-1, j) (A_{i-1}<=B_{i}) || dp2(i-1, j) (B_{i-1}<=B_{i})$ 

 

Boolean 값을 갖고 있는 DP이니, 정의를 변형하여 추가적인 정보를 담을 수 있도록 한다.

 

Observation 1 : $dp1(i), dp2(i)$ 중 켜져 있는 j는 연속한 구간을 이룬다.

귀납법을 이용하여 다음을 증명하자.

$dp1(i)$, $dp2(i)$는 각각 연속한 구간을 이루며, $dp1(i)$의 l과 $dp2(i)$의 r은 최대 한 칸, 즉 $l<=r+1$을 만족한다.

N=1일 때는 $dp1(1)=[1, 1]$, $dp2(1)=[0, 0]$으로 조건을 만족한다.

만약 위 전이 식의 조건을 모두 만족한다면, dp2(i)는 dp1(i-1), dp2(i-1)을 합집합한 것이고, dp1(i)는 이를 한칸 뒤로 민 것이니 성립한다.

이 조건이 깨지기 위해서는 합집합했을 때 (1)구간이 두개로 쪼개지던가, 아니면 (2)합집합한 후 dp1을 한칸 뒤로 밀었을 때 공백이 발생하는 경우이다.

(2)의 경우가 발생하려면, dp1, dp2가 모두 공집합이어야 하는데, 이는 애초에 답이 불가능이니 모순이다.

(1)의 경우가 발생할 수 있는 유일한 상황은 dp1(i)는 dp1(i-1)을 1칸 미루고, dp2(i)는 dp2(i-1)을 가질 때이다. 하지만 위 조건을 만족하는 전이가 발생하기 위한 부등식을 생각해보면 사이클이 생겨, 그러한 상황 자체가 불가능하다.

 

따라서, dp(i, j) 대신 dpl(i), dpr(i)를 관리하면 위와 똑같은 dp식을 $O(N)$안에 관리할 수 있다.

 

시간 복잡도 : $O(N)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e6;
 
int N, A[MAXN+10], B[MAXN+10];
int dpl[MAXN+10][2], dpr[MAXN+10][2];
 
int main()
{
	int i, j, k;
 
	scanf("%d", &N);
	for(i=1; i<=N*2; i++) scanf("%d", &A[i]);
	for(i=1; i<=N*2; i++) scanf("%d", &B[i]);
 
	dpl[1][0]=dpr[1][0]=1;
	dpl[1][1]=dpr[1][1]=0;
	for(i=2; i<=N*2; i++)
	{
		dpl[i][0]=dpl[i][1]=987654321;
		dpr[i][0]=dpr[i][1]=-1;
		if(A[i-1]<=A[i])
		{
			dpl[i][0]=min(dpl[i][0], dpl[i-1][0]+1);
			dpr[i][0]=max(dpr[i][0], dpr[i-1][0]+1);
		}
		if(B[i-1]<=A[i])
		{
			dpl[i][0]=min(dpl[i][0], dpl[i-1][1]+1);
			dpr[i][0]=max(dpr[i][0], dpr[i-1][1]+1);	
		}
		if(A[i-1]<=B[i])
		{
			dpl[i][1]=min(dpl[i][1], dpl[i-1][0]);
			dpr[i][1]=max(dpr[i][1], dpr[i-1][0]);
		}
		if(B[i-1]<=B[i])
		{
			dpl[i][1]=min(dpl[i][1], dpl[i-1][1]);
			dpr[i][1]=max(dpr[i][1], dpr[i-1][1]);	
		}
	}
 
	int p, q=N;
 
	if(dpl[2*N][0]<=N && N<=dpr[2*N][0]) p=0;
	else if(dpl[2*N][1]<=N && N<=dpr[2*N][1]) p=1;
	else return !printf("-1\n");
 
	vector<int> ans;
	for(i=2*N; i>=1; i--)
	{
		ans.push_back(p);
		if(p==0)
		{
			q--;
			if(A[i-1]<=A[i] && dpl[i-1][0]<=q && q<=dpr[i-1][0]) p=0;
			if(B[i-1]<=A[i] && dpl[i-1][1]<=q && q<=dpr[i-1][1]) p=1;
		}
		else
		{
			if(A[i-1]<=B[i] && dpl[i-1][0]<=q && q<=dpr[i-1][0]) p=0;
			if(B[i-1]<=B[i] && dpl[i-1][1]<=q && q<=dpr[i-1][1]) p=1;
		}
	}
	reverse(ans.begin(), ans.end());
	for(auto it : ans) printf("%c", it ? 'B' : 'A');
	printf("\n");
}