kurarrr's memooo

主に競プロ備忘録

ARC 097 E - Sorted and Sorted

AtCoder 競プロ

問題概要

1~Nの数字が書かれた白のボールと黒のボールがN個ずつ,合計2N個ある. 白と黒それぞれに注目した時,どちらも順番通りに並んでいるようにするには最低何回のswapが必要か.
1 <= N <= 2*103

解法

考察段階から箇条書き

  • 最終状態が決まるとそのswap回数は求められそうな気がする
  • 最終状態は愚直に全探索すると(2N)!個
  • 条件を満たすような最終状態を考える.
    • N=2とすると, W1W2B1B2 W1B1W2B2 W1B1B2W2 B1B2W1W2 B1W1B2W2 B1W1W2B2 の6個
    • 最初はW1かB1で,W(i),B(j)の後にはW(i+1)かB(j+1)しか来ない.
    • と言うことは状態数はO(22N)であることがわかる
    • O(2N)はDPできそう
  • 上の考察から dp[i][j] := (W(i),B(j)まで並べた時のswap回数) と言うDPは自然に立つ.
  • するとW(i), B(j) まで並べた時, W(i+1)を持ってくるためのswap回数が必要になる(Bも同様)
  • このコスト,costw[i][j] を考える
    • (先頭i+j個 .. W(i),B(j)までの数) (それ以外で元々W(i+1)より左にあった数) W(i+1) (それ以外)
    • それ以外と言うのはW(i+2),B(j+1)以上の数のことである.
    • つまり,W(i+2),B(j+1)以上でW(i+1)より左にある数を数えれば良い
    • posw(k) := (W(i+1)以上でk番目にある数の個数), posbも同様に置いて,sum(kはw(i+1)より右)(posw(k)) + sum(kはW(i+1)より右)(posb(k)) が高速に求めたい.
    • これはBinaryIndexTreeを使って,後ろからW(N),W(N-1),..と位置を追加していけば一回あたりO(logN)で可能 c.f.反転数の求め方
    • よってcostw, costbはO(N2 logN)で埋められる
  • DP
    • 遷移 dp[i][j] = max(dp[i-1][j] + costw[i-1][j] , dp[i][j-1] + costb[i][j-1] ) (i-1<0またはj-1<0の時はその項はなし)
    • 初期化 dp[0][0] = 0
    • 答えは dp[N][N]

メモ

考察段階から丁寧に追っていくと割と自然は発想が多いし,勉強になった.
できなかったことは,最終状態から考えていくとこと,小さい数から考察していくこと

コード