TCO2019 Round1B Hard EllysPearls - ちゃっくのメモ帳

解説ACしたので解法をメモっとく。やはりDPの遷移を考えるのが苦手すぎる。
地頭不足を感じてしまう....

問題概要

長さNの配列pが与えられる。配列の各要素は1~Mのいずれかである。
次の操作を繰り返すことで同じ値の要素同士は隣り合うように並び替える。
(例えば[1,2,3,3,1]を[2,2,1,1,3,3]のように並べ替える)

操作: 配列の要素を1つ選択し、任意の場所に移動させる

この時最低で何回操作を繰り返せば配列が同じ値の要素同士が隣り合うように並べられるか?

解説

bitDPをする(制約を見るとそれくらいしかできることがない)。
次のようなdpを考える。
dp[i][j][stae] := p[0,i)に対して考える。状態state(bit)に対応する値が確定しており、最後に確定した値がjのときの最低操作回数。(ここで状態stateが0011ならば0,1が確定していると考える)

例えば、サンプル1を考えるN=11,M=4,p={2, 4, 1, 1, 1, 3, 2, 1, 4, 2, 2}. pを0-originにして{1,3,0,0,0,2,1,0,3,1,1}とする。
dp[3][0][1011]は{1,3,0}に対して最後が0になっているような操作回数なので0。

もう1つ例を考える。N=5,M=2,p={0,1,1,0,0}とする。
例えばdp[0][*][*]は初期状態として0である。(操作0回で実現可能)

dp[0][*][*]からp[0]=0を観測して次の状態に遷移する
- dp[1][0][b01] = 0 (0の位置確定)
- dp[1][0][b11] = 0 (0,1の位置確定。最後が0なので1...10...0という並びは確定する)
- dp[1][1][b10] = 1 (1の位置確定。0は以降の0の出現で場所が確定し、p[0]はその位置への移動が発生する)
- dp[1][1][b11] = 1 (0,1の位置確定。最後が1なので0...01...1という並びになることが確定する)

状態遷移は次のように考えられる。
以降、表記として{0,1,2}は0,1,2の位置が確定したことする。また{0,1,2}<2>が0,1,2の位置が確定し、最後が2が確定したとする。更に、{{0,0,1,2,2}}は位置が確定した部分の配列を示すとする。

観測した状態p[i]の位置が確定している場合
- もしp[i]が最後に確定した値ならば操作をしなくて良い
  - 例えば {0,1,2}<2>の状態でp[i]=2を観測したらそのまま結合すれば操作0回でよい。つまり、{{0,0,1,1,2,2}}→{{0,0,1,1,2,2,2}}とすればよい
- もしp[i]が最後に確定した値で無い場合、操作1回を行って確定位置に移動する必要がある
  - 例えば {0,1,2}<2>の状態でp[i]=1を観測するとする。つまり{{0,0,1,1,2,2}},p[i]=1 となってたらp[i]=1を移動して{{0,0,1,1,p[i]=1,2,2}}とする

観測した状態p[i]の位置が確定していない場合
- p[i]の位置を確定する
  - 例えば{0,1,2}<2>でp[i]=3を観測したとする。この時{{0,0,1,1,2,2}}→{{0,0,1,1,2,2,p[i]=3}}とすればよい。この時、操作は不要である。
- p[i]は移動することだけ決定して、以降のp[i]と同じ値のときに確定する。
  - 例えば{0,1,2}<2>でp[i]=3を観測したとする。この時{{0,0,1,1,2,2}}だったとするとまだp[i]=3を付け加えずに、iの状態でp[j]=3を観測したときに{0,1,2,4,5,3}<3>とするか、更に先延ばしにするかを決定する。ただし、この時p[i]=3は必ず後ろに移動することになるので1回は操作を行う必要がある。

以上の遷移を行うとdp[N][*][*]の最小値が求める値となる。

constexpr int INF = numeric_limits<int>::max() / 3;
int dp[51][16][(1<<15)];

class EllysPearls{
    public:
        int getMin(int N, int M, vector <int> p){
            rep(i,N) p[i]--;

            rep(i,N+1) rep(j,M) rep(k,(1<<M)) dp[i][j][k] = INF;
            rep(i,M) rep(j,(1<<M)) dp[0][i][j] = 0;

            rep(i,N){
                rep(j,M){
                    rep(mask,(1<<M)){
                        if(!(mask & (1<<j))) continue;
                        if(dp[i][j][mask] == INF) continue;

                        if(mask & (1<<p[i])){
                            if(p[i] == j){
                                chmin(dp[i+1][j][mask],dp[i][j][mask]);
                            }else{
                                chmin(dp[i+1][j][mask],dp[i][j][mask]+1);
                            }
                        }else{
                            assert(p[i] != j);
                            chmin(dp[i+1][j][mask],dp[i][j][mask]+1);
                            chmin(dp[i+1][p[i]][mask | (1<<p[i])],dp[i][j][mask]);
                        }
                    }
                }
            }

            int ans = INF;
            rep(i,M) rep(j,(1<<M)){
                chmin(ans,dp[N][i][j]);
            }
            return ans;
        }
};

感想

bitDPだと思いつくのは、制約を見ると明らか。
状態の持ち方も「最後に○○した値」を状態に持つのも典型的なDPだと思う。

遷移も気づけば割と自明だったと思うが思いつかなかった。
こういう遷移が構築できなくてDPがめちゃくちゃ苦手。
今回だと、「p[i]が確定していないときに位置確定をあとに回す」というような遷移が思いつかなかった。