kmjp's blog

競技プログラミング参加記です

AtCoder ARC #126 : D - Pure Straight

Cと同じ配点なのに、割と苦戦。
https://atcoder.jp/contests/arc126/tasks/arc126_d

問題

N要素の整数列Aが与えられる。
Aの各値は1~Kのいずれかであり、1~Kはそれぞれ最低1個は含まれる。

Aのうち2要素のswapを繰り返し、Aの連続部分列に[1,2,...,K]が現れるようにしたい。
最小swap回数を求めよ。

解法

dp(n,mask,x) := A[x...(x+K-1)]=[1,2,....,K]としようとするとき、Aのうち先頭n要素まで考えたとき、maskに該当する値をターゲットの[1,2,...,K]に含めるときの最小swap回数
とする。nを進めながら、A[n]をA[x...(x+K-1)]に取り込むかどうかを2通り考えていく。
すでにmaskに含めた値とA[n]の値における転倒数を求めれば、A[n]をA[x+A[n]-1]に移動するのにかかる最小swap回数がわかる。

上記処理だと、(転倒数の算出を前処理で求めておいたとしても) O(N^2*2^K)かかりTLEする。
そこでdpの状態数を1つ減らすことを考える。
K要素を少ないswap回数で連続するように並べる際、先頭floor(K/2)要素は右に移動、末尾floor(K/2)要素は左に移動するのが良い。
もしKが奇数なら、中央の要素は、元の位置から動かさないのが良い。

中央の要素以外、(中央の要素の位置で決まる)先頭floor(K/2)要素の右への移動回数分と、末尾floor(K/2)要素の左への移動回数分は打ち消しあう。
そのため、中央の要素以外、dp(n,mask,x)を計算する場合x=0と固定して考えて、左右への移動回数を計算してよい。

int N,K;
int A[202];

ll dp[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
	}
	
	int mask;
	FOR(mask,1<<K) dp[mask]=1LL<<60;
	dp[0]=0;
	FOR(i,N) {
		j=A[i];
		FOR(mask,1<<K) if((mask&(1<<j))==0&&dp[mask]<1LL<<59) {
			x=__builtin_popcount(mask);
			int add=0;
			FOR(y,K) if(y>j&&(mask&(1<<y))) add++;
			
			if(x<(K-1)/2) add-=i-(x-(K-1)/2);
			if(x==(K-1)/2&&K%2==0) add-=i;
			if(x>(K-1)/2) add+=i-(x-(K-1)/2);
			dp[mask|(1<<j)]=min(dp[mask|(1<<j)],dp[mask]+add);
		}
	}
	cout<<dp[(1<<K)-1]<<endl;
	
}

まとめ

苦戦したとはいえ本番解き切れてよかった。