Codeforces #612 Div1 A. Garland

あんまりよい出来ではなかったのに割と順位いいの、難しい回だったのかな。
https://codeforces.com/contest/1286/problem/A

問題

1～NのPermutationが与えられる。
なお、一部の要素は未定である。

未定の場所を、全体がPermutationとなるように埋めたとき、隣接要素同士が異なるパリティを持つ組を最小化したい。
最小いくつになるか。

解法

Nが小さいので、場所を決めていない偶数と奇数の要素数を覚えつつ、先頭からDPしていけばよい。

int N;
int P[101];
int C[2];

int dp[105][105][105][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==1) return _P("0\n");
	
	C[0]=N/2;
	C[1]=N-C[0];
	
	FOR(i,102) FOR(x,101) FOR(y,101) dp[i][x][y][0]=dp[i][x][y][1]=1010;

	FOR(i,N) {
		cin>>P[i];
		
		if(i==0) {
			if(P[i]==0 || P[i]%2==0) dp[i+1][N/2-1][N-N/2][0]=0;
			if(P[i]==0 || P[i]%2==1) dp[i+1][N/2][N-N/2-1][1]=0;
		}
		else {
			FOR(j,2) FOR(x,101) FOR(y,101) if(dp[i][x][y][j]<1000) {
				if(x&&((P[i]==0)||(P[i]%2==0))) {
					dp[i+1][x-1][y][0]=min(dp[i+1][x-1][y][0],dp[i][x][y][j]+(j==1));
				}
				if(y&&((P[i]==0)||(P[i]%2==1))) {
					dp[i+1][x][y-1][1]=min(dp[i+1][x][y-1][1],dp[i][x][y][j]+(j==0));
				}
			}
		}
	}
	
	cout<<min(dp[N][0][0][0],dp[N][0][0][1])<<endl;
	
	
	
	
}

まとめ

Div1Aとはいえなんの面白みも工夫もない問題に感じたけど、これなんだったんだ。