Beat LR

この解説上では、$N$ が本来の $\frac{N}{3}$ と等しいものとする。(例えば、本来 $N=6$ のケースは $N=2$ として扱う。)

まず、$P_{1}=1$ と固定し、求まった答えに $3N$ をかけるとする。

次の2つを満たすことが必要十分条件になる。

• 隣り合った要素がどちらも $N$ 以下であることはない。
• $N$ 以下の要素で $P$ を分割し、$N$ より大きい数のみからなる $N$ 個の数列にする。このとき、それらのどの数列に対しても次の条件が成り立つ。
  • 端以外の要素であって、隣のどちらの要素よりも小さいようなものが存在しない。(これを条件 $C$ とする。)

ここで、分割した後のそれぞれの数列の長さを前にあるものから順に $A_{1},A_{2},\dots A_{N}$ とする。このとき、条件を満たす数列の個数は次のようになる。

• $(N-1)!\times \frac{2N!}{\prod A_{i}!}\times \prod$「$\{1,\dots,A_{i}\}$ の順列であって、条件 $C$ が成り立つものの個数」

まず、「$\{1,\dots,A_{i}\}$ の順列であって、条件 $C$ が成り立つものの個数」は、次のように求まる。

• $A_{i}=1$ ならば、明らかに $1$ 個。
• $A_{i}>1$ ならば、$\{1,\dots,A_{i}-1\}$ の順列であって条件 $C$ が成り立つものの端 $2$ つのどちらかに $1$ を追加し、元々あった要素全てに $1$ を足してできる全ての数列のみが条件を満たす。よって、$2^{A_{i}-1}$ 個。

ここで、$A$ の総和は常に $2N$ である。よって、$\prod$「$\{1,\dots,A_{i}\}$ の順列であって、条件 $C$ が成り立つものの個数」は、常に $2^{N}$ と等しくなり、$A$ に依存しなくなる。

よって、本質的には次を求めればよい。

• 長さが $N$ であり総和が $2N$ であるようなあらゆる正の整数列 $A$ に対する $\frac{2N!}{\prod A_{i}!}$ の総和

ここで、$A$ を固定したとき、この値は次と一致する。

• $1$ 以上 $N$ 以下の整数からなる長さ $2N$ の数列であって、 $i$ が $A_i$ 個あるものの個数

任意の $A$ に対する総和を取るため、求めるべき値は次と等しくなる。

• $1$ 以上 $N$ 以下の整数からなる長さ $2N$ の数列であって、 $1$ 以上 $N$ 以下の整数が全て出現するものの個数

これは、出現しない整数の個数を決め打つ包除原理によって、次のように個数が求まる。

• $\sum_{k=0}^{N} (-1)^{k} \binom{N}{k} (N-k)^{2N}$

よって、最終的な答えは次の式によって求められる。これは時間計算量 $O(N\log N)$ や $O(N\log \log N)$ で計算することができるため、この問題を解くことができた。

• $3N\times (N-1)!\times 2^{N}\times \sum_{k=0}^{N} (-1)^{k} \binom{N}{k} (N-k)^{2N}$

(参考:twitter ありがとうございます)