Blitz Round #25 D - Shifting Sort
- サイト
- Eolymp
- コンテスト
- Blitz Round #25
- 問題
- D - Shifting Sort
長さ の正整数列 があります。次の操作を好きな回数行えます。
- 添字 を選ぶ。操作を始める前の の最上位ビットの位置を として、 の下位 ビットを左に 1 つ巡回シフトする
たとえば は と変化します。
数列を広義単調増加にするのに必要な操作回数の最小値を求め、不可能なら を出力する問題です。
- 、、テストケースの の総和は 以下
正確な問題文は元の問題ページを見てください。
のビット長を とすると、操作は を ビット幅で回転させるだけなので、 がとりうる値は
の 通りで、そのときの操作回数は です。途中で最上位ビットが になっても、回転の幅は操作前のビット長のまま変わらないことに注意します。
各要素の候補は高々 個しかないので、前から順に
を候補ごとに持つ DP ができます。遷移は
です。前の要素の候補と今の要素の候補をそれぞれ値でソートしておけば、 は尺取りで前から最小値を更新していくだけで求まります。
答えは で、これが なら です。
とすると、候補は各要素で高々 個なので、計算量はソートを含めて です。
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 以下の前の候補のうちの最小操作回数」です。