phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ARC097 E. Sorted and Sorted

問題

1からNまでの番号が書かれた白いボールと黒いボールが合わせて2*N個ランダムに一列に並んでいる。
隣り合う2つのボールを交換する操作を行い、以下を達成したい。

  • i < jな(i,j)の組に対して、iと書かれた白いボールは、jと書かれた白いボールより左にある
  • i < jな(i,j)の組に対して、iと書かれた黒いボールは、jと書かれた黒いボールより左にある

これを達成するために必要な最小操作回数を求めよ。

制約

  • 1 <= N <= 2,000

解法

最終状態がどんな形になるか考えてみると、一番左は何色かの1番のボールが置かれることになる。
例えば、一番左が「白1」だったら、その隣は「白2」か「黒1」があり得る。
このように左から順に埋めていくことを考える。


dp[i][w][b] := i番目までで、白はw番まで、黒はb番まで使った場合のswap回数
を考える。
dp[i][w][b]のとき、(i+1)番目に来うるのは白の(w+1)番か、黒の(b+1)番になる。
wとbまで使った状態で、白の(w+1)番が最終状態で(i+1)番目になる操作回数cがわかれば、
dp[i+1][w+1][b] = min(dp[i+1][w+1][b], dp[i][w][b] + c)
で更新できる。黒の方も同様。
だが、このままだとO(N^3)になっている。
これは状態が冗長で、bはiとwから一意に決まるので、dp[i][w]だけを考えればよい。


操作回数cを考える。
以下のような場合で、w=2、b=1まで使った場合、w3を次に持ってくる場合を考える。

b1 w2 b3 w1 w3 b2

w3は5番目にあり、w=2、b=1まで使っている場合、1、2、4番目はすでに左側に操作で移動しているので、3番目のb3が残っており、それより左に操作で持ってこないといけない。
したがって、「p番目より左側で、w以下、b以下の個数」がわかれば操作に必要な回数が求められる。
そこで、「p番目より左側で、w以下の個数」をcntW[p][w]として求めることを考えると、これは累積和を使ってO(N^2)で前計算しておける。黒についても同様。


したがって、cntW[p][w]とcntB[p][b]を前計算でO(N^2)で求めておいて、dp[i][w]をO(N^2)で求められる。

反省

  • mapの参照は対数時間かかるので、ループ回数が多い(10^7近く)ときは無視できない