D - ぬいぐるみの整理 (Plush Toys) 第１６回日本情報オリンピック 予選

D - ぬいぐるみの整理 (Plush Toys)

問題概略

N個のぬいぐるみが一列に並んでいる。

ぬいぐるみは全部でM種類あり、同じ種類のぬいぐるみは全て連続させたい。

いくつかのぬいぐるみを選び、それらの場所を自由に入れ替えられる。

取り出す最小のぬいぐるみの個数を選べ。

制約

$N,$$M(1\leqq N\leqq 100000,1\leqq M\leqq 20)$

解法

素で実装するとM!になる。階乗問題はbitDPに出来ることがあり、今回はそれ。

bitDPが使えるのは、今までに選択したものを順不同でセットして考えられる時とか。

制約的に、bitDPで解くならMについてやるしかない。

今回の場合は選んだ種類のものを左から並べることにする。

11122

22111

と書いてみると、選んだ順番は関係なく同じ種類のものを選んでいたらそれらでまとめられると気づく。

ぬいぐるみの種類別の個数、全区間内の種類別の個数が分かれば解ける。

累積和をつかおう

問題の芯

bitDPは階乗問題を2^bの形にする。

つまりすでに選んだものを順不同でで考えられるとき解ける。

public class Main
{
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 12345678;
 
    static int N, M, K;
    static int[] A;
    static int[] dp; //状態iへの最小取替数
    static int[][] inc; //左からj個野中に含まれるiの合計　開区間
    static int[] len; //状態iのぬいぐるみの合計
 
    public static void main(String[] args)
    {
        N = sc.nextInt();
        M = sc.nextInt();
        A = sc.nextIntArrayDec(N);//-1して読み込んでる
        dp = new int[1 << M];
        len = new int[1 << M];
        inc = new int[M][N + 1];
 
        int[] tlen = new int[N];
        for (int i = 0; i < N; i++)
            tlen[A[i]]++;
        for (int s = 0; s < (1 << M); s++)
        {
            for (int j = 0; j < M; j++)
            {
                if ((s & (1 << j)) == 0) continue;
                len[s] += tlen[j];
            }
        }
 
        for (int i = 0; i < M; i++)
        {
            for (int j = 1; j < N + 1; j++)
            {
                inc[i][j] = inc[i][j - 1] + (A[j - 1] == i ? 1 : 0);
            }
        }
        Arrays.fill(dp, INF);
        dp[0] = 0;
 
        //sの次を見る
        for (int state = 0; state < (1 << M); state++)
        {
            for (int i = 0; i < M; i++)
            {
                if ((state & (1 << i)) != 0) continue;
                int next = state | (1 << i);
                //左からlen[state]個配置できている。
                //次に配置するのはiで、個数はlen[next] - len[state]
                //すでに配置されている個数を引く
                int score = dp[state] + (len[next] - len[state]) - (inc[i][len[next]] - inc[i][len[state]]);
                dp[next] = Math.min(dp[next], score);
            }
        }
        System.out.println(dp[(1 << M) - 1]);
    }