Codeforces Global Round 1 : D. Jongmah

この回はHighest更新できてよかったね。次回同じ量だけ落ちたけど。
https://codeforces.com/contest/1110/problem/D

問題

N個の麻雀牌が与えられる。
順子・刻子が合計で最大何個作れるか。

解法

各数値の牌を順に順子・刻子どちらに回すかを考えていこう。
同じ順子が３組作れるなら、それは３連刻でも代替できる。
よって、今見ている数値の牌を以後の順子に備えて残すとしても、高々２個残せばよい。

そこで、最後に見た数字と、その前に見た数字をそれぞれ0～2個残した状態で順子・刻子何個作れるかDPしていけばよい。

int N,M;
int A[1010101];

int dp[1010101][3][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N) {
		scanf("%d",&x);
		A[x+3]++;
	}
	
	FOR(i,1010000) {
		FOR(x,3) FOR(y,3) dp[i][x][y]=-1<<25;
	}
	dp[0][0][0]=0;
	FOR(i,1010000) FOR(x,3) FOR(y,3) if(dp[i][x][y]>=0) {
		int a,b,c;
		FOR(a,x+1) FOR(b,y+1) FOR(c,3) {
			int lef=A[i]-(a+b+c);
			if(lef<0) continue;
			dp[i+1][b][c]=max(dp[i+1][b][c],dp[i][x][y]+a+lef/3);
		}
	}
	
	
	cout<<dp[1005000][0][0]<<endl;
	
	
}

まとめ

麻雀の役判定のコード、面倒臭いよね。