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:
