コンテンツにスキップ

ABC478 C - Sort Subarray

サイト
AtCoder
コンテスト
ABC478
問題
C - Sort Subarray
難易度
426

長さ NN の整数列 AA の、長さ KK の連続部分列をちょうど 1 回だけ選んで昇順にソートします。その結果 AA 全体を昇順にできるかを判定する問題です(1≤K<N≤2×1051 \le K < N \le 2 \times 10^5)。

AA を昇順にソートした列を SS とします。区間 [i,i+K)[i, i + K) をソートして AA 全体が SS になるのは

  • 区間より前が SS と一致している(Aj=SjA_j = S_j, j<ij < i)
  • 区間より後ろが SS と一致している(Aj=SjA_j = S_j, j≥i+Kj \ge i + K)

のときです。このとき、区間の中の値の集まりも SS の対応する部分と一致するので、区間をソートすれば SS になります。逆に、区間の外は操作で変わらないので、この 2 つは必要です。

そこで

  • LiL_i = 先頭から ii 個がすべて SS と一致しているか
  • RiR_i = 位置 ii 以降がすべて SS と一致しているか

を前と後ろから求めておき、LiL_i かつ Ri+KR_{i+K} となる ii があるかを調べます。計算量はソートの O(Nlog⁡N)O(N \log N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = sorted(A)
l = [True]
for i in range(N):
l.append(l[-1] and A[i] == s[i])
r = [True]
for i in reversed(range(N)):
r.append(r[-1] and A[i] == s[i])
r.reverse()
if any(l[i] and r[i + K] for i in range(N - K + 1)):
print("Yes")
else:
print("No")
Uiua
&p⨬"Yes""No">⊣:/+>0×⍜⇌\+⟜\+≠⍆.∩(⊜⋕⊸≠@ &sc)

≠⍆. で AA とソートした列を比べ、ずれている位置を 11 にした列を作ります。⟜\+ で前からの累積和、⍜⇌\+ で後ろからの累積和を取って × で掛けると、「前にも後ろにもずれがある位置」、つまりずれている最初の位置から最後の位置までが正になります。/+>0 でその長さを数え、⊣ で取り出した KK と > で比べて、KK を超えていれば "No"、そうでなければ "Yes" を ⨬ で選んで出力しています。