ARC097 E - Sorted and Sorted

AtCoder Regular Contest
問題

1〜nが重複なく書かれた白/黒のボールが各n個ずつ計2n個一列に並べられている
「隣り合う2つのボールをswapする」という操作を繰り返して、「任意のペアi,j (i＜j)について、iと書かれた黒/白のボールがjと書かれた同色のボールより左にある」という状態にするためには、最低何回操作が必要か

解法

目的の状態は黒/白単体で見ると単調増加になってるものが入り混じった状態
一番左から順に決めていくことを考えると、
「黒ボールをi番目、白ボールをj番目まで、左に寄せて単調増加になるように並べた状態」
は全部ひとまとめにできることがわかる
(その状態に辿り着くまでにどうswapしたかとか、黒ボールと白ボールの順序とかはどうでもよく、このi+j個の列の右端に黒ボールのi+1番目を追加するための最小swap回数はそれらに依存しない)
→dpを使えばいい🤠

実装

dp[i][j]: 黒をi番目、白をj番目まで左から並べるのに必要な最小操作回数
b[i][j]: 黒をi番目、白をj番目まで並べた状態の一番右に、黒のi+1番目を追加するのに必要な最小操作回数
∴ 初期状態で黒のi+1番目より左側にある、黒のi+1以上のボールと白のj+1以上のボールの個数
w[i][j]: 白のj+1番目を追加するのに必要な〜

(↓はbを埋めていく部分の話で、wのときはiとjが逆になる)
各iについて、最初にj=nのときを考える
このとき白のボールは考える必要がないから、黒のi+1以上のボールのうちiより左にあるものの個数だけカウント
でj=n-1のときは、白のn-1が黒のi+1より左にあれば更に1回swapする必要があるからb[i][j+1]+1
こうやって後ろから埋めていけばO(N^2)でいける

b,wを埋める部分がちょっと複雑で考えるのに時間がかかった
実装ミスったかも
b,wを1個にまとめて、dpで白玉を動かす遷移のときだけi,jを逆にして使えばよかった
状態が2通りしかない問題でしょっちゅうこういうしょうもない実装してる気がするから反省

int n, t, p[2][2020], b[2020][2020], w[2020][2020], dp[2020][2020];
char c;

int main() {
	cin >> n;
	rep(i,n*2) {
		cin >> c >> t;
		p[c=='W'][t-1] = i;
	}
	
	rep(i,n) {
		reps(j,i+1,n) if (p[0][j]<p[0][i]) b[i][n]++;
		for (int j=n-1; j>=0; --j) b[i][j] = b[i][j+1] + (p[1][j]<p[0][i]);
	}
	rep(i,n) {
		reps(j,i+1,n) if (p[1][j]<p[1][i]) w[n][i]++;
		for (int j=n-1; j>=0; --j) w[j][i] = w[j+1][i] + (p[0][j]<p[1][i]);
	}
	
	rep(i,2020) rep(j,2020) dp[i][j] = inf;
	dp[0][0] = 0;
	rep(i,n+1) rep(j,n+1) chmin(dp[i+1][j], dp[i][j]+b[i][j]), chmin(dp[i][j+1], dp[i][j]+w[i][j]);
	cout << dp[n][n];
}