コンテンツにスキップ

Blitz Round #25 D - Shifting Sort

サイト
Eolymp
コンテスト
Blitz Round #25
問題
D - Shifting Sort

長さ nn の正整数列 a1,…,ana_1, \ldots, a_n があります。次の操作を好きな回数行えます。

  • 添字 ii を選ぶ。操作を始める前の aia_i の最上位ビットの位置を kk として、aia_i の下位 k+1k + 1 ビットを左に 1 つ巡回シフトする

たとえば 4=(100)24 = (100)_2 は (100)2→(001)2→(010)2→(100)2→⋯(100)_2 \to (001)_2 \to (010)_2 \to (100)_2 \to \cdots と変化します。

数列を広義単調増加にするのに必要な操作回数の最小値を求め、不可能なら −1-1 を出力する問題です。

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5、1≤ai≤2⋅1051 \le a_i \le 2 \cdot 10^5、テストケースの nn の総和は 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

aia_i のビット長を wiw_i とすると、操作は aia_i を wiw_i ビット幅で回転させるだけなので、aia_i がとりうる値は

ai を r 回回転させた値(0≤r<wi)a_i \text{ を } r \text{ 回回転させた値} \quad (0 \le r < w_i)

の wiw_i 通りで、そのときの操作回数は rr です。途中で最上位ビットが 00 になっても、回転の幅は操作前のビット長のまま変わらないことに注意します。

各要素の候補は高々 wiw_i 個しかないので、前から順に

dpi[v]=ai を値 v にしたときの、a1,…,ai を広義単調増加にする最小操作回数\mathrm{dp}_i[v] = a_i \text{ を値 } v \text{ にしたときの、} a_1, \ldots, a_i \text{ を広義単調増加にする最小操作回数}

を候補ごとに持つ DP ができます。遷移は

dpi[v]=r+min⁡u≤vdpi−1[u]\mathrm{dp}_i[v] = r + \min_{u \le v} \mathrm{dp}_{i-1}[u]

です。前の要素の候補と今の要素の候補をそれぞれ値でソートしておけば、min⁡u≤v\min_{u \le v} は尺取りで前から最小値を更新していくだけで求まります。

答えは min⁡vdpn[v]\min_v \mathrm{dp}_n[v] で、これが ∞\infty なら −1-1 です。

L=⌊log⁡2max⁡ai⌋+1L = \lfloor \log_2 \max a_i \rfloor + 1 とすると、候補は各要素で高々 LL 個なので、計算量はソートを含めて O(nLlog⁡L)O(n L \log L) です。

Python(upsolve)
INF = float("inf")
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
dp = [(0, 0)]
for a in A:
w = a.bit_length()
cand = []
x = a
for r in range(w):
cand.append((x, r))
x = (x << 1 | x >> (w - 1)) & ((1 << w) - 1)
cand.sort()
ndp = []
best = INF
p = 0
for q, r in cand:
while p < len(dp) and dp[p][0] <= q:
best = min(best, dp[p][1])
p += 1
ndp.append((q, best + r))
dp = ndp
ans = min(y for _, y in dp)
if ans == INF:
print(-1)
else:
print(ans)

dp は (値, 最小操作回数) の組を値の昇順に並べたもので、best が「値が q 以下の前の候補のうちの最小操作回数」です。