AtCoder Regular Contest 097: E - Sorted and Sorted

https://beta.atcoder.jp/contests/arc097/tasks/arc097_c

問題概要

1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たときその色のボールが番号の小さい順に左から並んでいる状態にしたい。この状態を達成するための最小操作回数を求めよ。

解法

左から順番にボールを確定させていくことを考える。まず一番左に置けるのは黒1か白1のどちらかである。ここで仮に黒1を置いた場合、その次に置けるのは黒2か白1である。このように次に使えるボールは常に「黒・白それぞれの使ってないボールの中で最も若い番号のもの」ということになる。よって以下のような状態数N*NのDPが立つ。

dp(b, w): 黒のボールを番号b, 白のボールを番号wまで置いたときの最小操作回数

このDPの遷移は上で述べた通り2通り(次にb+1を置くかw+1を置くか)しかない。よってあとはこの遷移のための最小操作回数が高速にわかればこの問題が解けることになる。ここでその最小操作回数は「これから置くボールより初期位置が左にあって、かつまだ使われていないボールの数」に等しい。これは実は前計算しておくとO(1)で求まる。具体的には(b, w)の状態から次に黒(b+1)を置くとき、まだ使われていないボールというのは黒の(b+2)以上か白の(w+1)以上のボールである。これを満たすボールが自分より左に何個あるかがわかればよく、これは色ごとに累積和を取っておけばO(1)で参照することができる。

dp2(c, i, j): 色がcで番号がi以上のボールが、左からj番目までに何個出現するか

これはO(N2)で求められる。あとはO(N2)でDPを回しつつ遷移の際にこの累積和テーブルを参照して更新を行っていくと答えが求まる。

感想

こういうDPを本番に通せるようになってきてうれしいですね

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;
 
void main() {
    immutable int INF = 1 << 29;
 
    auto N = readln.chomp.to!int;
    auto A = new int[](2*N);
    auto C = new bool[](2*N);
    foreach (i; 0..2*N) {
        auto s = readln.split;
        A[i] = s[1].to!int;
        C[i] = s[0] == "B";
    }
 
    auto BR = new int[](N+1);
    auto WR = new int[](N+1);
    foreach (i; 0..2*N) {
        if (C[i]) BR[A[i]] = i;
        else      WR[A[i]] = i;
    }
 
    auto dpB = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいBの数
    auto dpW = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいWの数
 
    foreach (i; 0..N+1) foreach (j; 0..2*N) dpB[i][j+1] = dpB[i][j] + (C[j] && A[j] > i);
    foreach (i; 0..N+1) foreach (j; 0..2*N) dpW[i][j+1] = dpW[i][j] + (!C[j] && A[j] > i);
 
    auto dp = new int[][](N+1, N+1);
    foreach (i; 0..N+1) dp[i].fill(INF);
    dp[0][0] = 0;
 
    foreach (n; 1..2*N+1) {
        foreach (b; 0..n+1) {
            int w = n - b;
            if (b > N || w > N) {
                continue;
            }
            if (b > 0) {
                dp[b][w] = min(dp[b][w], dp[b-1][w] + dpB[b][BR[b]+1] + dpW[w][BR[b]+1]);
            }
            if (w > 0) {
                dp[b][w] = min(dp[b][w], dp[b][w-1] + dpW[w][WR[w]+1] + dpB[b][WR[w]+1]);
            }
        }
    }
 
    dp[N][N].writeln;
}