TopCoderOpen 2019 Round1B Hard EllysPearls

1ミスしたので出てなくてよかったかも。
(URL未確定)https://community.topcoder.com/stat?c=problem_statement&pm=15437

問題

N要素の整数列Pが与えられる。
Pの各要素は1～Mのいずれかである。

要素を1回動かすとは、任意の要素を数列から取り除き、その値を任意の場所にまた入れることを意味する。
P中の同じ値が連続するようにするには、上記処理を最小回数行えばよいか。

解法

以下のように状態を取るとbitdpできる。
dp(pos, col, mask) := pos要素目まで処理したとき、colと同じ値なら残す。maskにbitmaskで示す要素は、以後colとして選択できない
すなわり、あるM色の並び順と一致するならそのまま残し、一致しないならコスト1で動かす、としたときにうまく並び順を選び(colおよびmaskを選択し)コストの最小値を求める問題にする。

int dp[51][16][1<<15];

class EllysPearls {
	public:
	int getMin(int N, int M, vector <int> P) {
		int i,j,mask,x,y;
		FORR(p,P) p--;
		
		memset(dp,0x3c,sizeof(dp));
		FOR(i,M) dp[0][i][1<<i]=0;
		FOR(i,N) {
			FOR(j,M) FOR(mask,1<<M) if(dp[i][j][mask]<1<<20) {
				FOR(x,M) {
					if(j!=x && (mask&(1<<x))) continue;
					dp[i+1][x][mask|(1<<x)]=min(dp[i+1][x][mask|(1<<x)],dp[i][j][mask]+(P[i]!=x));
				}
			}
		}
		
		int mi=1<<20;
		FOR(j,M) FOR(mask,1<<M) mi=min(mi,dp[N][j][mask]);
		return mi;
		
		
		
	}
}

まとめ

最初もう少し重い解法でTLEしてしまった。
本番出てたら危なかったな。