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してしまった。
本番出てたら危なかったな。