yukicoder 1370 置換門松列
まず, 自明な-1の判定について考える. 門松列を作る3つの要素はすべて異なっていなければならないので, 連続する3つの要素が異なるかどうか判定すればよい(実際は各$ iについて$ A_i = A_{i+2}かどうか判定するのみでよい).
次に門松列の性質に注目すると, $ x_{a_1} < x_{a_2} > x_{a_3} < x_{a_4} ...もしくは$ x_{a_1} > x_{a_2} < x_{a_3} > x_{a_4} ...という構造が条件を満たすことがわかる. 後者は前者を-1倍して適当な数を加えることによって実現可能なので, このうち前者のみ考えればよいことがわかる.
隣接する2頂点を辺とする有向グラフを考える. 辺を構成する2頂点には優先順位があるので, その通りに張り, トポロジカルソートをすると答えが求まる.
計算量は$ O(N + M)となる.