Atcoder 문제 Brave CHAIN

 

https://atcoder.jp/contests/abc176/tasks/abc176_f

F - Brave CHAIN

 

대회 때 중요 로직들을 생각해냈지만 구현 실수 + 경우를 충분히 계산하지 못해서 맞왜틀만 외치다가 못 푼 문제입니다...

애초에 대회 때 16명 밖에 못 풀었어서 풀었으면 지금까지 앳코더 친 라운드 중에 최고점을 찍을 뻔 했지만.. 다음으로 기약을 하게되었습니다 크흑..

 

이 문제는 개인적으로 엄청 흥미로운 문제였고 제 기억에 남기고 싶어서 블로그에 쓰게 되었습니다.

 

문제는 간단합니다.

 

$ 1 $ ~ $ N $ 중에 하나가 적힌 카드가 $ 3*N $ 개가 있습니다. $ N <= 2000 $

일렬로 쭉 카드를 나열하였을 때 우리는 다음과 같은 행동을 합니다.

왼쪽에서부터 카드를 보는데 5개를 가져온 뒤 그 중에서 3개를 뽑습니다.

이 3개가 모두 같은 숫자이면 점수 1 점을 획득하고 아니면 획득하지 못합니다.

그리고 이 3개의 카드는 버려지게 되고 나머지 2개의 카드는 다시 왼쪽에 집어넣어줍니다.

이렇게 해서 마지막에 카드 3개가 남게되면 이 카드 3개도 똑같이 동일 유무를 판단한 뒤 점수를 얻고 끝나게됩니다.

이 때 얻을 수 있는 최고 점수를 구하시오가 이 문제입니다.

 

아이디어는 간단히 구할 수 있습니다.

$ dp $ 로 접근하는데 카드 두 개만 남기는 거에 초점을 둡시다.

왜 두 개만 남겼을까요? 개인적으로 이런 접근이 문제 푸는데 많이 도움이 되었습니다.

$ N $ 제한도 $ 2000 $ 이여서 뭔가 $ N^{2} $ 로 접근할 가능성이 보입니다..

 

그래서 $ dp $ 배열을 이렇게 정의합니다.

$ dp[x][y] $ 는 나머지 2개 카드를 x y 를 만들 수 있는 최고 점수입니다.

그리고 $ dp2[x] $ 는 나머지 2개 카드 중 한 개를 x 라고 했을 때 이 x 를 만들 수 있는 최고 점수입니다.

즉 $ dp2[x] $ 는 $ dp[x][y] ,$ $ all $ $ 1 <= y < =n $ 중에서 최대값이라고 할 수 있습니다.

 

그럼 여기서 문제가 생깁니다.

 

각 라운드가 $ N $ 이고 카드 종류가 $ N $ 이니 결과적으로 시간복잡도가 $ N^{3} $ 아닐까 하는 의문이죠

 

그래서 이번엔 여기에 초점을 둡니다. 왜 3개가 같아야지만 점수를 얻을 까?

 

그럼 뭔가가 보입니다.

 

 

 

첫 번째로 이번 라운드에서 무조건 점수를 낸다고 가정하겠습니다.

 

1.  각 라운드마다 3개의 카드를 새로 가져올텐데 이 카드 3개 중에 2개가 같을 때입니다.

이 때는 점수를 내기 위해서는 $ dp[x][y] $ 에서 한 값이 정해지게 됩니다.

그럼 여기서 시간복잡도는 $ O(N) $ 이 됩니다.

 

2. 3개의 카드 중에 하나와 나머지 카드 2개로 점수를 내는 경우 입니다.

이 때도 점수를 내기 위해서는 $ dp[x][x] $ 이고 x 는 당연히 3개의 카드 중 하나가 될 것입니다.

그럼 여기서 시간복잡도는 $ O(1) $ 이 됩니다.

 

3. 3개의 카드가 모두 같을 때 입니다.

이 때는 모든 $ dp[x][y] $ 값을 + 1 시켜줘야 됩니다.

그럼 이 때 $ O(N^{2}) $ 이 된다고 생각이 되지만 더 간단하게 할 수 있습니다.

지금 증가된 + 1 은 그 뒤에 진행되는 값에선 영향을 주지 않습니다.

즉 생각을 전환시켜서 지금 당장 증가시켜주는 것이 아니라 그 뒤에 진행되는 값에서 - 1를 시켜준 뒤

마지막에 최종적으로 총 증가량을 더해주는 것입니다.

직관적으로 생각했을 때 지금 더할 걸 나중에 더하는 데 이제 그렇게 되면 뒤에 영향을 받지 않는 값까지도 증가가 되니깐 뒤에 영향을 받지 않은 값들은 앞에 증가율 만큼을 빼주는 겁니다.

 

그럼 여기서 시간복잡도는 $ O(1) $ 이 됩니다.

 

 

 

두 번째로는 점수를 안내도되는 경우를 가정하겠습니다.

 

1. 3개의 카드가 모두 2개의 카드에 포함이 안되는 경우입니다.

 

이럴 경우는 그냥 아무런 작업을 하지 않아도 됩니다.

 

2. 3개의 카드 중 한 개의 카드가 2개의 카드에 포함되는 경우입니다.

 

3개의 카드 중 한 개의 값이 $ x $ 라고 할 때

이 때는 $ 1 <= i <= N $ 에서 $ dp2[i] $ 값을 $ dp[i][x] $ 와 비교하면 됩니다.

 

3. 3개의 카드 중 두 개의 카드가 2개의 카드 모두에 포함되는 경우입니다.

 

이 경우에는 3가지 경우에서 고려가 될텐데 이 때는 그 전 2개의 카드가 어떤 종류이던지 상관이 없습니다.

즉 지금까지 $ dp[x][y] $ 중에 최대값을 비교해주면 됩니다.

 

 

그리고 나머지 한 개의 카드는 $ x $ 라고 했을 때  $ dp[x][x] $ 값을 증가시켜주면 됩니다.

 

 

코드 입니다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
typedef vector<int> vit;
typedef vector<vit> vitt;
typedef vector<lld> vlt;
typedef vector<vlt> vltt;
typedef vector<pi> vpit;
typedef vector<vpit> vpitt;
typedef long double ld;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
	 if(0<=y&&y<n&&0<=x&&x<m) return true;
	 return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
const int MAX = 2020;
int dp[MAX][MAX],arr[MAX*3],dp2[MAX];
void upd(int f1,int f2,int x){
	dp[f1][f2] = max(dp[f1][f2],x);
	dp[f2][f1] = max(dp[f2][f1],x);
}
int main(void){
	for(int e=0;e<MAX;e++){
		for(int p=0;p<MAX;p++) dp[e][p] = -1e9;
		dp2[e] = -1e9;
	}
	int n;
	scanf("%d",&n);
	for(int e=0;e<3*n;e++) scanf("%d",&arr[e]);
	if(n==1){
		printf("1");
		return 0;
	}
	int tt = 0,mm = 0;
	for(int e=0;e<5;e++){
		for(int p=e+1;p<5;p++){
			int ll = -1,err = 0;
			for(int q=0;q<5;q++){
				if(e==q||p==q) continue;
				if(ll==-1) ll = arr[q];
				else{
					if(ll!=arr[q]) err = 1;
				}
			}
			if(err==0){
				upd(arr[e],arr[p],1);
				dp2[arr[e]] = 1;
				dp2[arr[p]] = 1;
				mm = 1;
			}else{
				upd(arr[e],arr[p],0);
				dp2[arr[e]] = max(dp2[arr[e]],0);
				dp2[arr[p]] = max(dp2[arr[p]],0);
			}
		}
	}
	for(int e=1;e<=n-2;e++){
		int lx = 5 + (e-1) * 3, rx = 5 + e * 3;
		
		// use 3 card 
		
		int ll = -1,err = 0;
		for(int q=lx;q<rx;q++){
			if(ll==-1) ll = arr[q];
			else{
				if(ll!=arr[q]) err = 1;
			}
		}
		int res = 0;
		if(err==0){
			tt++;
			res = 1;
		}
		vector<pair<pi,int> > v;
		
		// use 1 card
		
		for(int q=lx;q<rx;q++){
			if(dp[arr[q]][arr[q]]!=-1e9){
				// find 3 card
				
				int s1 = -1,s2 = -1;
				for(int r=lx;r<rx;r++){
					if(q==r) continue;
					if(s1==-1) s1 = arr[r];
					else s2 = arr[r];
				}
				v.push_back(mk(mk(s1,s2),dp[arr[q]][arr[q]] + 1 - res));
			}
			// no gain
				
			for(int r=1;r<=n;r++){
				if(dp2[r]!=-1e9){
					v.push_back(mk(mk(r,arr[q]),dp2[r] - res));
				}
			}
		}
		
		// use 2 card
		for(int q=lx;q<rx;q++){
			for(int r=q+1;r<rx;r++){
				if(arr[r]==arr[q]){
					int s1 = -1;
					for(int p=lx;p<rx;p++){
						if(p==q||r==p) continue;
						s1 = arr[p];
					}
					for(int p=1;p<=n;p++){
						if(dp[p][arr[q]]!=-1e9){
							v.push_back(mk(mk(p,s1),dp[p][arr[q]] + 1 - res));
						}
					}
				}
				v.push_back(mk(mk(arr[q],arr[r]),mm - res));
			}
		}
		for(int e=0;e<sz(v);e++){
			int f1 = v[e].x.x;
			int f2 = v[e].x.y;
			int wei = v[e].y;
			mm = max(mm,wei);
			dp2[f1] = max(dp2[f1],wei);
			dp2[f2] = max(dp2[f2],wei);
			upd(f1,f2,wei);
		}
	}
	int lastn = arr[3*n - 1];
	if(dp[lastn][lastn]!=-1e9) dp[lastn][lastn]++;
	int ans = 0;
	for(int e=1;e<=n;e++) for(int p=1;p<=n;p++) if(dp[e][p]!=-1e9){
		ans = max(ans,dp[e][p] + tt);
	}
	printf("%d",ans);
	return 0;
}