Codeforces #585 Div2 E. Marbles

本番これはさっくり思いついてた。
https://codeforces.com/contest/1215/problem/E

問題

N個の石が並んでおり、それぞれ色が与えられている。
隣接する石を並べ替える、ということを繰り返し、同じ色の石同士が連続するようにしたい。
並べ替えは最小何回行えばよいか。

解法

色が最大20色ということで、BitDPに持ち込めそうなことはわかる。
まず、前処理として色Aの石の前に色Bの石が計何個あるかを列挙しておく。

ここからBitDPで前から順に石の並び順を考えていく。
今、bitmaskに対応する色の石が左から順に同色が連続するように並んでいたとする。
次にbitmaskにない色cの石を並べようとするとき、swapの回数は、もともと色cの左にあった、bitmask外の色の石の数に等しい。
これは色数をCとするとO(C^2*2^C)で数え上げることができる。

int N;
int A[404040];
ll C[21][21];
ll num[21];
ll dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		FOR(j,20) if(j!=A[i]) C[A[i]][j]+=num[j];
		num[A[i]]++;
	}
	
	FOR(i,1<<20) dp[i]=1LL<<60;
	dp[0]=0;
	int mask;
	FOR(mask,1<<20) {
		FOR(i,20) if((mask&(1<<i))==0) {
			ll t=dp[mask];
			FOR(j,20) if(mask&(1<<j)) t+=C[i][j];
			dp[mask|(1<<i)]=min(dp[mask|(1<<i)],t);
		}
	}
	cout<<dp[(1<<20)-1]<<endl;
}

まとめ

Div2とはいえDぐらいでいいんでは。