原案: blackyuki

門松的である数列の例は以下の通りです。

1 3 2
4 6 5 3 8 2 7 1
2 7 6 1 3 4 8 5
4 9 3 7 6 8 1 5 2
2 7 3 9 1 8 5 6 4
1 6 2 3 5 4
1 4 3 2
4 6 3 2 5 1
2 7 3 1 6 5 4
1 9 7 5 2 8 4 6 3

ここから、門松的であるための条件を求めることはできるでしょうか？

入力される数列は順列なので、 \(a_i=a_{i+1}\) のように隣接項が等しいケースは考えなくてよいです。また、問題条件より隣接項の大小関係しか考慮しなくてよいので、その関係が認識しやすい形に置き換えて考察を進めましょう。

\(a_i < a_{i+1}\) という状況を < 、 \(a_i > a_{i+1}\) なる状況を > と書くことにします。
すると、隣接項の関係を < と > からなる文字列として書くことができ、 \(x\) は <> なる連続部分列の個数、 \(y\) は >< なる連続部分文字列の個数に対応します。

先程の例を文字列に置き換えると

<>
<>><><>
<>><<<>
<><><><>
<><><><>
<><<>
<>>
<>><>
<>><>>
<>>><><>

となります。

ここから、門松的であるための条件を求めることはできるでしょうか？

以降の解説は後半に続けます。