コンテンツにスキップ

DOJ Starter Contest 1 G - 수열 정렬하기 4

サイト
DOJ
コンテスト
DOJ Starter Contest 1
問題
G - 수열 정렬하기 4

長さ NN の整数列 AA に対し、ある要素に 11 を加え、それ以外のすべての要素から 11 を引く操作を行えます。数列を広義単調増加にするための最小操作回数を求める問題です(N≤105N\le10^5、0≤Ai≤1090\le A_i\le10^9)。

この操作は「全要素から 11 を引いて、選んだ要素に 22 を加える」と言い換えられます。全要素に同じ値を足し引きしても大小関係は変わらないので、整列の可否だけを考えるなら、選んだ要素に 22 を加える操作として扱えます。

そこで、左から順に、直前の要素以上になるまで必要な回数だけ 22 を加えます。先頭には加える必要がありません。各要素を必要以上に大きくすると後続の要素の条件が厳しくなるので、必要最小限だけ加えるのが最適です。

より具体的には、要素 ii の操作回数を tit_i とすると、条件は

Ai+2ti≤Ai+1+2ti+1A_i+2t_i\le A_{i+1}+2t_{i+1}

です。t1=0t_1=0 とし、直前の tit_i が決まったらこの不等式を満たす最小の非負整数 ti+1t_{i+1} を選びます。他の実現可能な操作回数列と比べても、帰納的に各 tit_i が最小になるので、その総和も最小です。

コードでは、隣接差分 d[i] = A[i + 1] - A[i] を管理しています(0 始まり)。すべての差分が 00 以上になれば整列済みです。

d[i] が負なら、右側の要素 A[i + 1] に 22 を加える操作を

t=⌈−d[i]2⌉t=\left\lceil\frac{-d[i]}{2}\right\rceil

回行います。負の d[i] に対して、これは (1 - d[i]) // 2 で求められます。

この操作で d[i] は 2t2t 増えます。また、次の差分 d[i + 1] は 2t2t 減ります。それ以外の差分は変わりません。左からこの更新を繰り返すと、すでに直した差分を壊さずに処理できます。

差分を 11 回走査するだけなので、計算量・空間計算量はともに O(N)O(N) です。

Python
N = int(input())
A = list(map(int, input().split()))
d = [A[i] - A[i - 1] for i in range(1, N)]
ans = 0
for i in range(len(d)):
if d[i] < 0:
t = (1 - d[i]) // 2
ans += t
d[i] += 2 * t
if i < len(d) - 1:
d[i + 1] -= 2 * t
print(ans)