ABC478 C - Sort Subarray
- サイト
- AtCoder
- コンテスト
- ABC478
- 問題
- C - Sort Subarray
- 難易度
- 426
長さ の整数列 の、長さ の連続部分列をちょうど 1 回だけ選んで昇順にソートします。その結果 全体を昇順にできるかを判定する問題です()。
を昇順にソートした列を とします。区間 をソートして 全体が になるのは
- 区間より前が と一致している(, )
- 区間より後ろが と一致している(, )
のときです。このとき、区間の中の値の集まりも の対応する部分と一致するので、区間をソートすれば になります。逆に、区間の外は操作で変わらないので、この 2 つは必要です。
そこで
- = 先頭から 個がすべて と一致しているか
- = 位置 以降がすべて と一致しているか
を前と後ろから求めておき、 かつ となる があるかを調べます。計算量はソートの です。
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)≠⍆. で とソートした列を比べ、ずれている位置を にした列を作ります。⟜\+ で前からの累積和、⍜⇌\+ で後ろからの累積和を取って × で掛けると、「前にも後ろにもずれがある位置」、つまりずれている最初の位置から最後の位置までが正になります。/+>0 でその長さを数え、⊣ で取り出した と > で比べて、 を超えていれば "No"、そうでなければ "Yes" を ⨬ で選んで出力しています。