Official

C - Sort Subarray Editorial by MMNMM Editorial for printing


\(A _ 1,A _ 2,\ldots,A _ N\) を昇順に並べた列を \(X=(X _ 1,X _ 2,\ldots,X _ N)\) とします。

ある \(i\) を選んで操作を行ったあとに \(A\) が昇順になっている(\(X\) と一致している)とします。 \(A _ 1,A _ 2,\ldots,A _ {i-1}\) および \(A _ {i+K},A _ {i+K+1},\ldots,A _ N\) の値は操作の前後で変化しないため、これらに対しては操作を行う前から \(X\) と一致している必要があります。

逆に、ある \(i\) に対して \(A _ 1=X _ 1,A _ 2=X _ 2,\ldots,A _ {i-1}=X _ {i-1}\) および \(A _ {i+K}=X _ {i+K},A _ {i+K+1}=X _ {i+K+1},\ldots,A _ N=X _ N\) が成り立っているとき、このような \(i\) に対して操作を行うことで \(A\) を \(X\) と一致させることができます。

よって、例えば次のような方法で判定を行うことができます。

  • \(A _ i\ne X _ i\) となる最小の \(i\) と最大の \(i\) を求め、それらの差が \(K\) 未満かどうか判定する。
  • \(A _ i\ne X _ i\) となる最小の \(i\) に対する操作を行い、\(A=X\) となるか確認する。

\(X\) を直接求めるとソートが必要になり \(O(N\log N)\) 時間となります。 これでも十分高速ですが、\(A _ i\ne X _ i\) となる最小の \(i\) などをうまく言い換えることで \(O(N)\) 時間でこの問題を解くこともできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;
    vector<unsigned> A(N);
    for (auto&& a : A) cin >> a;

    // A[i] != X[i] となる最大の i は、j < i かつ A[j] > A[i] なる j が存在する最大の j
    unsigned prefix_max{}, max_i{};
    for (const auto& [i, a] : A | views::enumerate) {
        prefix_max = max(a, prefix_max);
        if (prefix_max > a) max_i = i;
    }

    // A[i] != X[i] となる最小の i は、i < j かつ A[i] > A[j] なる j が存在する最小の j
    unsigned suffix_min{N}, min_i{N};
    for (const auto& [i, a] : A | views::enumerate | views::reverse) {
        suffix_min = min(a, suffix_min);
        if (suffix_min < a) min_i = i;
    }

    cout << (K + min_i > max_i ? "Yes" : "No") << endl;
    return 0;
}

posted:
last update: