Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 232 F 問題 Simple Operations on Sequence

AtCoder ABC ABC232 F問題 500 pts

問題

提出解答

問題の概要

2つの整数列 $A=(A_i)_{i=1}^N, B=(B_i)_{i=1}^N$ が与えられる. 列 $A$ に対して, 以下の操作を任意回できる.

$X$ 円払い, $i=1,2, \dots, N$ を選び, $A_i$ の値を $1$ 増やすか, $1$ 減らす.
$Y$ 円払い, $i=1,2, \dots, N-1$ を選び, $A_i, A_{i+1}$ を入れ替える.

この操作によって, $A$ を $B$ に一致させるために, かかる合計費用の最小値を求めよ.

制約

$2 \leq N \leq 18$
$1 \leq X \leq 10^8$
$1 \leq Y \leq 10^{16}$
$1 \leq A_i, B_i \leq 10^8$

解法

$A$ を $B$ に一致させるためには実は左 (または右) から順番に一致させなくてはいけない *1.

よって, 左から一致させていく. つまり, 第 $i$ 項を一致させる場合, $A$ の第 $j (\gt i)$ 項を第 $i$ 項に移動させ, 値を変更させることになる. そして, この方法で第 $i$ 項が決定させる場合, 第 $1,2, \dots, i-1$ 項は全く関係ない.

このとき, 以下のような動的計画法で解くことができる: $[\![N]\!]$ で $N$ 以下の正の整数全体の集合としたとき, $S \subset [\![N]\!]$ に対して,

${\rm DP}(S):=\text{左から} |S| \text{項を最初の第} s \in S \text{項で担った場合, そこから更にかかる費用の最小値}$

とする.

$S \subset [\![N]\!]$ を固定する. $r:=|S|$ とし, $S^c=\{j_1, \dots, j_r\}$ で, $j_1 \lt j_2 \dots \lt j_{N-r}$ とする. 第 $(r+1)$ 項を最初の第 $j_k$ 項とする. この場合, 左に $k-1$ 回移動させることになり, 値を変更させることになる. よって,

$\displaystyle {\rm DP}(S)=\min_{1 \leq k \leq N-r} ({\rm DP}(S \cup \{j_k\} ) + (k-1)Y+ |A_{j_k}-B_r|X)$

である.

自明なケース ${\rm DP}([\![N]\!])=0$ であることに注意して, ${\rm DP}(\emptyset)$ が求めるべき答えになる.

計算量について, $S \subset [\![N]\!]$ となる $S$ の個数は $2^N$ 個, $\# S \leq N$ であることから, $O(N2^N)$ になる.

このように順列の問題において, 左から決定させていく場合, 上で説明した bit-DP という手法が有用である.

*1:そうでない一致のさせ方の場合でも, 左からまたは右からとみなすことができる