yukicoder 1369 交換門松列・竹

愚直に実装すると$ O(N^3)となるのでこれを改善したい.

まず, 門松列かどうかの判定部分はスワップされた部分の周辺部分を見て差分更新すればよいので$ O(1)に改善できる.

そしてスワップ部分だが, 問題文の条件より少なくとも一つ門松列でない連続する3つの要素が存在し, その部分は必ずスワップしなければならないので, その部分と全体の要素のスワップのみを考えることにより$ O(N)に改善できる.

以上の工夫より, $ O(N)でこの問題が解けた. 類題としてJOI 14本選 A JOI紋章(難易度6)などがある.