AtCoder ARC #097 : E - Sorted and Sorted

この回は不参加でした。
https://beta.atcoder.jp/contests/arc097/tasks/arc097_c

問題

2N個のボールが並んでいる。
N個は白く1～Nの数値が１つずつ書かれており、残りN個は黒く1～Nの数値が１つずつ書かれている。
隣接したボールをswapし、同色のボールは左側から数値が昇順となるようにしたい。
最小何回swapすればよいか。

解法

dp(i,j) := 白ボールを1～i、黒ボールを1～jまで左端にそれぞれ昇順に並べる場合のswap回数
とする。求めるのはdp(N,N)である。
dp(i,j)の状態から、次に(i+1)番の白ボールと(j+1)番の黒ボールを並べる際のswap回数を考えていけばよい。
事前に両ボールを左端に寄せるswap回数を求めておけば、このDPは全体O(N^2)で行える。

int N;
int pos[2][2020];
int L[2][2020][2020];
int dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>s>>x;
		pos[s=="W"][x-1]=i;
	}
	
	FOR(i,2) {
		FOR(x,N) {
			for(y=x+1;y<N;y++) if(pos[i][y]<pos[i][x]) L[i][x][N]++;
			for(y=N-1;y>=0;y--) L[i][x][y]=L[i][x][y+1]+(pos[i^1][y]<pos[i][x]);
		}
	}
	
	FOR(x,N+2) FOR(y,N+2) dp[x][y]=1<<25;
	dp[0][0]=0;
	FOR(x,N+1) FOR(y,N+1) {
		if(x<N) dp[x+1][y]=min(dp[x+1][y],dp[x][y]+L[0][x][y]);
		if(y<N) dp[x][y+1]=min(dp[x][y+1],dp[x][y]+L[1][y][x]);
	}
	
	cout<<dp[N][N]<<endl;
}

まとめ

Eとはいえ600ptなのでそこまで難しくない。