JOI2021 本選 C - 集合写真

• 問題
• AC

以下、すべて0-basedに直して考えている。

最終形は$2 1 0 |4 3|8 7 6 5$のように、$0, 1, ..., N-1$をいくつかの連続部分列に区切って各区間を反転させたものになっている。

$\operatorname{dp}[x] =$ 先頭から$x$個の階段に$0, 1, ..., x-1$を有効な順番で並べる場合の最小交換数

としてDPができそう。

DPの遷移を考える。位置$0, 1, ..., x-1$に人$0, 1, ..., x-1$を配置済みとして、位置$x$から$x, x+1, ..., y-1$を逆順に並べる場合のコストを$f[x][y]$とすると、$\operatorname{dp}[y] \leftarrow \max(\operatorname{dp[y]}, \operatorname{dp}[x] + f[x][y])$のように配るDPが${O}(N^2)$でできる。

次に$f$の求め方を考える。与えられた列の中に散らばっている数$x, x+1, ..., y-1$を位置$x, x+1, ..., y-1$に逆順で整列させる時、$c[i][j] :=$ 数$i$の左にある$j$以上の数の総数として、だいたい$c[x][x] + c[x+1][x] + ... + c[y-1][x]$回の交換をして$x, x+1, ..., y-1$を前のほうに持ってくることになるが、この際、与えられた列上での$x, x+1, ..., y-1$の順番を考えた時に、既に転倒が起きているぶんの交換はしなくてよい。そこで、$\operatorname{inv}[x][y] :=$ 与えられた列から$x, x+1, ..., y-1$を抜き出した部分列の転倒数、とすると

$$f[x][y] = c[x][x] + ... + c[y-1][x] - \operatorname{inv}[x][y]$$

と求まる。$c$は累積和と同じように構成できて、さらにその累積和$C[x][y] := c[0][y] + ... + c[x-1][y]$を取っておけば

$$f[x][y] = C[y][x] - C[x][x] - \operatorname{inv}[x][y]$$

と求まる。

最後に$\operatorname{inv}$の作り方を考える。ここでは$\operatorname{inv}[x][y-1]$と$\operatorname{inv}[x][y]$の差分、つまり、与えられた列上の$x, x+1, ..., y-2$に対応する部分列に（与えられた順番通りに）$y-1$を挿入した時の転倒数の増分を考える。この増分は与えられた列上で$y-1$の後ろにあって$[x, y-1)$に含まれる数の総数に等しい。$y-1$の後ろよりも前にある数のほうが（$c$を使って）表しやすいので、さらにこれを$(y-1-x) -$($y-1$の前にあって$[x, y-1)$に含まれる数の総数)と言い換える。この増分は上で求めた$c$を使って表せて、結局

$$\operatorname{inv}[x][y] \leftarrow \operatorname{inv}[x][y-1] + (y-1-x) - (c[y-1][x] - c[y-1][y])$$

と遷移できる。

これで、全体として${O}(N^2)$で計算できたことになる。