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; }
まとめ
苦戦したとはいえ本番解き切れてよかった。