\(A_i=A_{i+1}\) をみたす \(i\) が存在するか否かで場合分けをします．

まず存在しない場合です． このときは，各部分列の長さが奇数という条件が出てきます． \(N \equiv K \mod 2\) ならば分割は明らかに可能であり，そうでなければ不可能です．

存在する場合を考えます． \(A_i=A_{i+1}\) なる \(A_i,A_{i+1}\) を残した上で，\(K=2\) のケースに帰着します． これは，適当に先頭と末尾から \(K-2\) 要素をとりだし，それを \(1\) 要素ずつ分割として採用すればよいです．

\(K=2\) の場合，\(A_i\) の直前，\(A_i\) と \(A_{i+1}\) の間，\(A_{i+1}\) の直後，のいずれかで数列を切ることで，条件を達成できます． これは \(\mod 3\) での値を考えればわかります．

上記の戦略をそのまま実装すれば，\(O(N)\) 時間の解法が得られます．

解答例(c++)