AtCoder ABC #176 : F - Brave CHAIN

Braveとは。
https://atcoder.jp/contests/abc176/tasks/abc176_f

問題

3N個のカードが並んでいる。
それぞれ1～Nのいずれかの数字が書かれている。
カードが5枚以上ある間、以下を繰り返す。

• 左から5枚のうち、3枚を選び取り除き、隙間を詰める。
• その際、取り除いた3枚が同じ数字なら1ポイントを得る。

また、最後に残ったカード3枚が同じ数字なら、追加で1ポイントを得る。
最適なカードの選択を行う場合、最高で何ポイント得られるか。

解法

dp(i,x,y) := i回処理を繰り返したとき、左2枚のカードの数字がx,yの場合の最高スコア
とし、このテーブルを埋めて行くことを考える。
ただ、これは愚直に行うとテーブルがO(N^3)の大きさを持つのでTLE/MLEする。

ただ、dp(i,*,*)とdp(i+1,*,*)でほとんど同じ値となるため、差分だけ更新していくことを考えよう。
この際、テーブルのうち各行または列内の最大値を持っておくと処理がスムーズにいく。
実際処理1回で更新されるのはO(N)箇所なので、全体でO(N^2)で処理を終えられる。

処理を行うたびに、左端の2枚(a,b)に、次の3枚(x,y,z)を加えてそこから3枚取り除くことになる。

• x,y,zが同じ数字なら、それを取り除く。dpテーブルは全体的にインクリメントすべきだが、そうするとTLEするのでテーブルはいじらず最後に解に1を加えることにする。
• 加えた3枚中2枚が同じ数字の場合、左端2枚に同じ数字があれば、合わせて3枚セットにして捨ててポイントを得よう。
• それ以外はポイントが得られない。
  • 元の2枚(x,y)を残す: DPテーブルは変化しない。
  • 元の2枚から1枚、新規3枚から1枚残すことを考える。例えばa,xを残すならdp(i+1,a,x)=max(dp(i,a,*))となる。
  • 新規3枚から2枚(a,b)を残すことを考える。このときdp(i+1,a,b)はmax(dp(i,*,*))となる。

上記処理は、あらかじめテーブルの行・列の最大値を取っておけば参照・更新いずれもO(N)で済む。

int N;
int A[6060];
int dp[2060][2020];
int ma[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,3*N) {
		cin>>A[i];
		A[i]--;
	}
	
	int ret=0;
	FOR(x,N) {
		FOR(y,N) dp[x][y]=-1<<20;
		ma[x]=-1<<20;
	}
	dp[A[0]][A[1]]=0;
	ma[A[0]]=ma[A[1]]=0;
	
	for(i=2;i+2<3*N;i+=3) {
		sort(A+i,A+i+3);
		if(A[i]==A[i+2]) {
			ret++;
			continue;
		}
		vector<vector<int>> cand;
		if(A[i]==A[i+1]) {
			FOR(x,N) cand.push_back({A[i+2],x,max(dp[A[i+1]][x],dp[x][A[i+1]])+1});
		}
		if(A[i+1]==A[i+2]) {
			FOR(x,N) cand.push_back({A[i+0],x,max(dp[A[i+1]][x],dp[x][A[i+1]])+1});
		}
		for(j=i;j<i+3;j++) {
			FOR(x,N) cand.push_back({x,A[j],ma[x]});
		}
		
		
		cand.push_back({A[i+0],A[i+1],dp[A[i+2]][A[i+2]]+1});
		cand.push_back({A[i+0],A[i+2],dp[A[i+1]][A[i+1]]+1});
		cand.push_back({A[i+1],A[i+2],dp[A[i+0]][A[i+0]]+1});
		
		int tmp=-1;
		FOR(x,N) tmp=max(ma[x],tmp);
		cand.push_back({A[i+0],A[i+1],tmp});
		cand.push_back({A[i+0],A[i+2],tmp});
		cand.push_back({A[i+1],A[i+2],tmp});
		
		FORR(c,cand) {
			dp[c[0]][c[1]]=max(dp[c[0]][c[1]],c[2]);
			ma[c[0]]=max(ma[c[0]],c[2]);
			ma[c[1]]=max(ma[c[1]],c[2]);
		}
	}
	
	int ma2=0;
	FOR(x,N) ma2=max(ma2,ma[x]);
	ma2=max(ma2,dp[A[3*N-1]][A[3*N-1]]+1);
	
	cout<<ma2+ret<<endl;
}

まとめ

AGCのBかCぐらいで出てもよさそう。