AGC043 D - Merge Triplets - ツバサの備忘録

解法

いろいろな数列を試していると、4つ以上の連続する区間が単調減少することはありません。
この原因を考えてみると、長さ3の数列 $A_{i}$ を作成しているため、4つ単調減少させようとすると、1つの長さ3の数列 + どこか1か所別の値が選ばれる必要があります。
長さ3の数列の先頭と、のこりの1つの要素のどちらが小さい場合でも、これらを単調減少させつつPの末尾に追加することは不可能です。
単調減少の先頭に注目、というのを少し拡大し、Pの完成形としてありうる数列に対し、

今までの要素の最大値が出てきたときに、その最大値と、その前の要素で区切る

という操作を繰り返すと、長さ3以下のブロックのようなものがたくさん出来上がります。これらのブロックを組み合わせて、その順番でPに追加できるような $A_{i}$ が作成できれば、答えにカウントできます。
これまたいろいろ手元で試すと、

長さ3のブロックの個数 + 長さ2のブロックの個数が $N$ 以下

であれば、 $A_{i}$ が作成可能であることがわかります。
長さ3はそのまま $A_{i}$ にすればよく、長さ2のブロックに対しては、適当に長さ1のブロックと組み合わせ、それぞれの先頭の要素の小さい方を $A_{i}$ の先頭にすればよいです。残った長さ1のブロックは、適当に昇順に並べます。
これにより、長さ3以下のブロック集合の作成方法が、そのまま答えになることがわかりました。
長さ2のブロックは、先頭 > 末尾となっていればよいです。
長さ3のブロックは、 $A \lt B \lt C$ に対し、 $CAB,CBA$ の2通りが考えられます。
長さ3のブロックを $i$ 個作成する、とした時、
$\frac{\prod_{j = 0}^{i-1} \left(_{n-3j}C_{3} \times 2 \right) }{i!}$
通りの組み合わせが考えられます。
そして、残った数の中から長さ2のブロックを $k$ 個作成する時、
$\frac{\prod_{j = 0}^{k-1}\ _{\left(n-3i - 2j\right)}C_{2} }{j!}$
通りの組み合わせが考えられるので、これを全ての $(i,j)$ のペアについて考えればよいです。

感想

昔解けなかった数え上げシリーズが解けていくのは楽しいです！(前も言った気がします)