AtCoder Grand Contest 032 - D問題: Rotation Sort
コンテスト中に悩んで解けなかった。想定解法のメモ。
atcoder.jp
問題概要
の順列が与えられる。
この順列に対し、以下の操作を行える。
- あるを選び、を一つ左にシフトする
- コストはかかる
- あるを選び、を一つ右にシフトする
- コストはかかる
を昇順に並べるために必要な最小のコスト操作を求めよ。
制約
解法
まず、2つの操作を以下のように言い換える。
- ある要素を今より右に移動し、特定の2つの要素間に追加する
- コストはかかる
- ある要素を今より左に移動し、特定の2つの要素間に追加する
- コストはかかる
また、各要素は高々1回動かすだけでよいことも分かる。
ここから、うまく最小のコスト総和を求めれる方法を考えられればよかったけど、区間dpで解けそうと考えてたら、区間の最小値・最大値とか、区間のマージ等の計算が難しくて積んだ。
正しくは以下のようなdpを考えることで解ける。(位置は要素との間とする)
昇順に を並べ終わった時、位置を見ている時の最小のコスト総和
元々あった要素の間に、必要に応じて要素を持ってくることで、要素を昇順に並べるイメージ。
例えば、問題の入力例3であれば、以下のような移動をするイメージになる。
そして から始め、以下のように値を伝搬させて各 の最小値を計算する。
-
- 位置 に(昇順に)要素 を配置する
- かかるコスト は要素 が位置 より左にあれば 、右にあれば
-
- 位置 を見終わって次に位置 を見る
- 何も動かさないのでコスト0
- ( ならば)
- 位置 と の間に要素 があるので、移動させなくても要素 までを昇順に並べられる
- コストは0
最終的に を解とすればよい。
このdpの計算量は になる。
実装
提出コード(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])