日々drdrする人のメモ

今日も明日もdrdr

AtCoder Grand Contest 032 - D問題: Rotation Sort

コンテスト中に悩んで解けなかった。想定解法のメモ。
atcoder.jp

問題概要

 {1, ..., N}の順列 {p = (p_1, ..., p_N)}が与えられる。

この順列に対し、以下の操作を行える。

  • ある {l, r (1 \le l < r \le N)}を選び、 {(p_l, ..., p_r)}を一つ左にシフトする
    • コストは {A}かかる
  • ある {l, r (1 \le l < r \le N)}を選び、 {(p_l, ..., p_r)}を一つ右にシフトする
    • コストは {B}かかる

 {p}を昇順に並べるために必要な最小のコスト操作を求めよ。

制約

  •  {1 \le N \le 5000}
  •  {1 \le A, B \le 10^9}

解法

まず、2つの操作を以下のように言い換える。

  • ある要素 {p_i}今より右に移動し、特定の2つの要素間に追加する
    • コストは {A}かかる
  • ある要素 {p_i}今より左に移動し、特定の2つの要素間に追加する
    • コストは {B}かかる

f:id:smijake3:20190328232804p:plain

また、各要素 {p_i}は高々1回動かすだけでよいことも分かる。


ここから、うまく最小のコスト総和を求めれる方法を考えられればよかったけど、区間dpで解けそうと考えてたら、区間の最小値・最大値とか、区間のマージ等の計算が難しくて積んだ。


正しくは以下のようなdpを考えることで解ける。(位置 {x}は要素 {p_x} {p_{x+1}}の間とする)
 {dp[k][x] = } 昇順に  {1, 2, ..., k} を並べ終わった時、位置 {x}を見ている時の最小のコスト総和


元々あった要素の間に、必要に応じて要素を持ってくることで、要素を昇順に並べるイメージ。

f:id:smijake3:20190329012921p:plain
dpのイメージ図

例えば、問題の入力例3であれば、以下のような移動をするイメージになる。

f:id:smijake3:20190329010010p:plain
計算例 (問題の入力例3より)

そして  {dp[0][0] = 0} から始め、以下のように値を伝搬させて各  {dp[k][x]} の最小値を計算する。

  •  {dp[k+1][x] \leftarrow dp[k][x] + C}
    • 位置  {x} に(昇順に)要素  {k+1} を配置する
    • かかるコスト {C} は要素  {k+1} が位置  {x} より左にあれば  {A}、右にあれば  {B}
  •  {dp[k][x+1] \leftarrow dp[k][x]}
    • 位置  {x} を見終わって次に位置  {x+1} を見る
    • 何も動かさないのでコスト0
  • ( {p_{x+1} = k+1} ならば)  {dp[k+1][x+1] \leftarrow dp[k][x]}
    • 位置  {x} {x+1} の間に要素  {k+1} があるので、移動させなくても要素  {k+1} までを昇順に並べられる
    • コストは0

最終的に  {dp[N][N]} を解とすればよい。
このdpの計算量は  {O(N^2)}になる。

実装

提出コード(PyPy3): Submission #4734154 - AtCoder Grand Contest 032

import sys
readline = sys.stdin.readline
 
N, A, B = map(int, readline().split())
*P, = map(int, readline().split())

# 各要素の位置を計算
Q = [0]*N
for i, p in enumerate(P):
    Q[p-1] = i
 
INF = 10**18
dp = [[INF]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    qi = Q[i]
    for j in range(N):
        v = dp[i][j]
        # 位置j に 要素(i+1) を配置する
        dp[i+1][j] = min(dp[i+1][j], v + (A if qi < j else B))
        # 位置j を見終わって 位置(j+1) を見る
        dp[i][j+1] = min(dp[i][j+1], v)
        # 要素(i+1) は移動しなくても昇順に並べられる
        if Q[i] == j:
            dp[i+1][j+1] = min(dp[i+1][j+1], v)
for i in range(N):
    dp[i+1][N] = min(dp[i+1][N], dp[i][N] + A)
for j in range(N):
    dp[N][j+1] = min(dp[N][j+1], dp[N][j])
sys.stdout.write("%d\n" % dp[N][N])