AtCoder Beginner Contest 232 F 問題 Simple Operations on Sequence
問題
提出解答
問題の概要
2つの整数列 が与えられる. 列
に対して, 以下の操作を任意回できる.
円払い,
を選び,
の値を
増やすか,
減らす.
円払い,
を選び,
を入れ替える.
この操作によって, を
に一致させるために, かかる合計費用の最小値を求めよ.
制約
解法
を
に一致させるためには実は左 (または右) から順番に一致させなくてはいけない *1.
よって, 左から一致させていく. つまり, 第 項を一致させる場合,
の第
項を第
項に移動させ, 値を変更させることになる. そして, この方法で第
項が決定させる場合, 第
項は全く関係ない.
このとき, 以下のような動的計画法で解くことができる: で
以下の正の整数全体の集合としたとき,
に対して,
とする.
を固定する.
とし,
で,
とする. 第
項を最初の第
項とする. この場合, 左に
回移動させることになり, 値を変更させることになる. よって,
である.
自明なケース であることに注意して,
が求めるべき答えになる.
計算量について, となる
の個数は
個,
であることから,
になる.
このように順列の問題において, 左から決定させていく場合, 上で説明した bit-DP という手法が有用である.
*1:そうでない一致のさせ方の場合でも, 左からまたは右からとみなすことができる