ABC478 C - Sort Subarray

部分列ソート

考え方

数式で言っていることは、こういうことである。
連続する $K$ 要素を選んで、その範囲内だけソートする。
これだけで全体がソートされている状態にすることができるか？

さて、選んだ区間の左、区間内、区間の右、とわけて考えてみよう。
区間の左右は、部分列ソートをしたとしても、何も変わらない。
よって、左右が本来のソート結果と不一致であれば、失敗である。
逆に、左右が一致してさえいれば、それで成功することは明らかである。

つまり、本来のソート順と不一致なものが入っている範囲の長さが $K$ 以内に収まるかを考えればよい。
これは、数列をコピーして全体ソートしたものを用意して、愚直に調べれば十分間に合う。

計算量は、普通に sort() した場合にはここが支配的で $O(N\log N)$ である。

バケツソートを用いれば計算量を $O(N)$ にもできるが、実装が複雑になる。
$2$ 秒に間に合いさえすれば速度での優劣がないため、その解法を選ぶのは悪手。

入力を受け取る。

n: 9
k: 6
a: {1, 4, 1, 4, 2, 1, 3, 5, 6}

数列をコピーして全体をソートすると、次のようになる。

元の数列:       {1, 4, 1, 4, 2, 1, 3, 5, 6}
全体ソート後:   {1, 1, 1, 2, 3, 4, 4, 5, 6}

0-indexed で見ると、両者が最初に不一致になるのは位置 $1$、最後に不一致になるのは位置 $6$ である。

したがって、不一致なものが入っている範囲の長さは $6-1+1=6$ となる。

これは $K=6$ 以内に収まる。

実際、位置 $1$ から位置 $6$ までをソートすると、数列全体が {1, 1, 1, 2, 3, 4, 4, 5, 6} となる。

したがって、答えは Yes である。

最初から全体がソート済みの場合も Yes である。
どの長さ $K$ の連続部分列をソートしても、全体がソート済みのまま変わらない。
解法によってはコーナーケースになりうるため注意すること。

特になし。