コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1954 (記事作成時点)
供養
解法
- $N$ 組のペアを作ったとき、各ペアは必ず偶数と奇数の組である
- 以降は $A_{i}, B_{i}$ の偶奇が異なることを前提に進める
- $u$ から始まる連続する $2n$ 人について $n$ 組のペアを作る手順の場合の数を $\mathit{DP}_{u, n}$ とする
- 任意の $u$ について $\mathit{DP}_{u, 0} = 1$ とする
- $n = 1, \dots, N$ について以下のようにDP表を更新する
- $u = 1, \dots, 2N - 2n + 1$ について、$u \lt v \le u + 2n$ かつ $(A_{i}, B_{i}) = (u, v)$ なる $i$ が存在するような $v$ とペアとなるような組み方と、$v + 1, \dots, u + 2n$ までの任意の組み方を考える
- $u, v$ をペアにするには $u + 1, \dots, v - 1$ を全てペアにしてから最後に $u, v$ をペアにするので、$k = \frac{v - u + 1}{2}$ として $\mathit{DP}_{u + 1, k - 1}$ 通り
- $u, \dots, v$ のペアの作り方と $v + 1, \dots, u + 2n$ のペアの作り方は独立なので、$_{n}\mathrm{C}_{k}$ 通り
- 上記より、$_{n}\mathrm{C}_{k} \times \mathit{DP}_{u + 1, k - 1} \times \mathit{DP}_{v + 1, n - k}$ 通りの作り方が存在する
- 上記を合計することで $\mathit{DP}_{u, n}$ を求めることができる
- $\mathit{DP}_{1, N}$ が答えとなる
実装
計算量は $O(NM)$
公式解説
躓いた点
