ABC406C - ~
問題リンク : https://atcoder.jp/contests/abc406/tasks/abc406_c
解法メモ
問題で与えられる整数列Pに対し、その連続部分列Bを考える。
試しに色々書き出してみると、B（長さn）がチルダ型とは次を満たすことと同値であるとわかる。
\begin{aligned}
& B\text{がチルダ型}のとき、 次を満たすk_1, k_2, k_3 \geq 1 \text{ が存在する.} \\
&\quad
\begin{cases}
B_1, A_2, \dots, B_{1 + k_1} \text{ は増加列} \\
B_{1 + k_1}, B_{1 + k_1 + 1}, \dots, B_{1 + k_1 + k_2} \text{ は減少列} \\
B_{1 + k_1 + k_2}, B_{1 + k_1 + k_2 + 1}, \dots, B_{1 + k_1 + k_2 + k_3} = B_n \text{ は増加列}
\end{cases}
\end{aligned}
要は増加列(長さ2以上)→減少列(長さ2以上)→増加列(長さ2以上)となればいい。あとはこれを効率的にカウントする。
カウントには次の事実を使う。
\begin{aligned}
B\text{がチルダ型のとき}、B\text{の連続部分列でチルダ型であるものの数は}k_1k_3
\end{aligned}
これは最初の増加列と最後の増加列の長さが短くできるため成り立つ。
詳細はコード参照 : https://atcoder.jp/contests/abc406/submissions/66189291
Discussion