キーエンス プログラミング コンテスト 2020 : D - Swap and Flip

久々にパフォーマンス3200出てよかった。
https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

問題

N枚のカードが左右一列に並んでいる。
各カードは両面に数値が書いてある。
2枚の隣接するカードを選び、位置を入れ替えると同時に表裏を反転するものとする。

各カードで表の値が左から昇順になるようにするとき、必要な最小操作回数を求めよ。

解法

一見カードの裏表がややこしく見えるが、初期位置から奇数個動いた位置にいると裏になる、という点に気づけば簡単。
あとはBitDPの要領で左端から順に、これまで並べたカードとその末尾に置いたカードを状態として持ち、その状態に至る最小操作回数を覚えておこう。
末尾に置いたカードとその位置が分かれば、そのカードの面と数値が分かるので、次にどのカードが置けるか容易に判定できる。

int N;
int A[2][20];

int dp[1<<18][18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) cin>>A[0][i];
	FOR(i,N) cin>>A[1][i];
	FOR(i,1<<18) FOR(x,18) dp[i][x]=1010100;
	
	FOR(i,N) dp[1<<i][i]=i;
	int mask;
	FOR(mask,(1<<N)-1) {
		FOR(i,N) if((mask&(1<<i)) && dp[mask][i]<1000000) {
			int b=__builtin_popcount(mask);
			int cur=A[abs(i-b-1)%2][i];
			FOR(x,N) if((mask&(1<<x))==0) {
				int nex=A[abs(x-b)%2][x];
				int num=__builtin_popcount((mask^(0xfffff))&((1<<x)-1));
				if(nex>=cur) {
					dp[mask|(1<<x)][x]=min(dp[mask|(1<<x)][x],dp[mask][i]+num);
				}
			}
		}
	}
	
	
	int mi=1010100;
	FOR(i,N) mi=min(mi,dp[(1<<N)-1][i]);
	
	if(mi>=1000000) {
		cout<<-1<<endl;
	}
	else {
		cout<<mi<<endl;
	}
}

まとめ

さてFぼちぼち解かないとな。