ABC478C - Sort Subarrayを解いてみた

40代文系社内SEが、AtCoder Beginner Contest 478 C - Sort SubarrayをCommon Lispで解いてみました。

まず問題文を見ます。
数列の一部を昇順に並べ替えることで、数列全体が昇順になるか判定する問題です。
最初に思いついた方法としては、並べ替える範囲をずらしながら並べ替え、全体が昇順になっているか判定するという方法です。計算量が$O(N^2)$になるので、$N \le 10^4$までなら採用できます。

次に制約を見ます。
$N$の最大値が$2 \times 10^5$なので、上で書いた方法では間に合いません。残念。
さらに考察をすると、数列を3つの部分に分けられることに気が付きました。操作によって並べ替えられる部分と、その両側の並べ替えられない部分です。この並べ替えられない部分の要素数を$N$から引いた値が$K$以下であれば、問題文の条件を満たすことになります。

並べ替えられない部分の要素数を数えるには、$A$と全体を昇順でソートした$A$を比較し、値が変わっていない要素を数えれば求められます。計算量は$O(N)$です。

以上より、以下の手順で解きます。

1. $A$のコピーを作成し、昇順でソートする
2. 先頭から$A$とコピーを比較し、値が一致するものを数える
3. 末尾から$A$とコピーを比較し、値が一致するものを数える
4. $N$から上の2,3で数えた値を引いた値が$K$以下のとき、条件を満たすと判定する

(let* ((n (read))
       (k (read))
       (a (make-array n)))

  (loop for i from 0 below n
        do (setf (aref a i) (read)))

  (let ((copy-a (copy-seq a))
        (count-l 0)
        (count-r 0))
    ;; コピーしたAを昇順にソート
    (sort copy-a #'<)

    ;; ソート前後で値が変わらない要素を数列の先頭から数える
    (loop for i from 0 below n
          for ai = (aref a i)
          for copy-ai = (aref copy-a i)
          while (= ai copy-ai)
          do (incf count-l))

    ;; ソート前後で値が変わらない要素を数列の末尾から数える
    (loop for i from (1- n) downto 0
          for ai = (aref a i)
          for copy-ai = (aref copy-a i)
          while (= ai copy-ai)
          do (incf count-r))

    (format t "~:[No~;Yes~]~%" (<= (- n count-l count-r) k))))