D - Pure Straight - AtCoder Regular Contest 126

詰め切るのが難しかった

D - Pure Straight

------------------------------------------------------------

問題

N項の整数列Aが与えれる、Aiは1...Kのいずれかである。

隣接する二項をswapする操作を何回でも行える時、ある区間が1...Kになるような最小の操作回数は何か。

--------------------------------------------------------

以下ではrainboyさんの実装を参考にしています。

解説

最終的に並び替える時に使うインデックス列

S1...Skを決め、まずそれらを隣接させることを考える。

上では小さい赤丸で囲ったのがS

全ての Sを中央(大きい四角で囲った所)に集めるように動かすと移動コストは最小になる。

（差分の合計の最小化は中央値）

次に並び替えのコストは転倒数である。

具体的な実装だが、bit dpで解く

dp[i][mask] := i個目まで見て、選んだ値の集合がmaskとした時に、maskの立っているビット数をkとして

maskをi-k+1 ~ i番目に並べたうえで昇順に並び替えるコストの最小値とすると

答えはdp[N][(2^K)-1]である。

iについてdpの遷移を考える。

iを選ばない時

今までに選んだmaskが半分以下なら、maskを全て右ずらし、半分以上選んでいる場合は残りのインデックスを全て左にずらすだけのコストがかかる。

雑な説明で申し訳ないが、上の様な図でK = 8とした時に

今までに選んだインデックスが赤丸で矢印の位置iについて考えているとする。

ここでiを選ばない場合、dpの定義的にdp[i+1][mask]に入る値は

左の3つを右端をi+1として右詰めする時のコストなので

dp[i+1][mask] = dp[i][mask] + 3になる

選んだ個数が半分以下の時は今までに選んだインデックスを右に（中央に）引っ張っていく必要があるが、半分以上選んでいるときは右の要素を左に（中央）引っ張る必要がある。

例えば今回右から引っ張ろうとすると

dp[i+1][mask] = dp[i][mask] + 5 となる

つまり毎回

dp[i+1][mask] = dp[i][mask] + min(pop_count(mask), K - pop_count(mask));

とすればいい。

iを選ぶ時は今までに選んだmaskについて、iを選ぶ事で発生する転倒数を加算すればいい

以下、自分用のメモ

void solve() {
    din(N, K);
    nad(A, N);
    vi cous(bit(K));
    rep(i, 1, bit(K)) {
        cous[i] = cous[i & (i - 1)] + 1;
    }
    vvi(dp, N + 1, bit(K), linf);
    dp[0][0] = 0;
    fora(i, a, A) {
        //今使わない
        rep(mas, bit(K)) {
            dp[i + 1][mas] = dp[i][mas] + min(cous[mas], K - cous[mas]);
        }
        //使う
        rep(mas, bit(K)) {
            if (bget(mas, a))continue;
            chmi(dp[i + 1][mas | bit(a)], dp[i][mas] + cous[mas & ~mask(a)]);
        }
    }
    out(dp[N][mask(K)]);
}