suisen のブログ

yukicoder No.1922 Separate and Attach

問題

https://yukicoder.me/problems/no/1922

解法

$Q = (1, 2, \ldots, N)$ として一般性を失いません。

$k$ 回の操作を行ったとして、値 $i$ が $j$ 回目の操作で $S$ に属したなら $b _ {i, j}=0$ 、 $T$ に属したなら $b _ {i,j}=1$ とします。

操作前の値 $i$ の位置を $x _ i$ 、 $k$ 回の操作後の値 $i$ の位置を $y _ i$ とします。

また、各 $i$ に対して、 $b _ {i, k} b _ {i, k-1} \cdots b _ {i, 1}$ を 2 進数として解釈した値を $v _ i$ とします。

このとき、任意の $i, j\ (i\neq j)$ に対して次が成り立ちます。

$v _ i \neq v_j$ ならば、 $v _i, v_j$ の大小関係と $y _ i, y _ j$ の大小関係は一致する
$v _ i = v_j$ ならば、 $x _i, x _ j$ の大小関係と $y _ i, y _ j$ の大小関係は一致する (i.e. 元の順番を保つ)

従って、 $i \lt j \Rightarrow y _ i \lt y _ j$ を満たす $y$ を与える $v$ であって、 $v _ n$ が最小であるようなものを構築すれば良いです。

これは次のような貪欲法により達成されます。

$v _ 1 \leftarrow 0$ とする。
各に対して、
- $x _ {i - 1} \lt x _ i$ ならば、 $v _ i \leftarrow v _ {i - 1}$ とする。
- $x _ {i - 1} \gt x _ i$ ならば、 $v _ i \leftarrow v _ {i - 1} + 1$ とする。

実装

https://yukicoder.me/submissions/831860

スマホコーディングなのでインデントがめちゃくちゃです。覚えてたら後で直します。

問題の一般化について

2 個の部分列を取り出して連結する操作ではなく $m$ 個の部分列を取り出して連結する操作である場合も、操作を $m$ 進数で解釈することで同様に解くことができます。