Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 236 D 問題 Dance

AtCoder ABC ABC236 D問題 400 pts

問題

提出解答

問題の概要

二重添字整数列 $A=(A_{i,j})_{1 \leq i,j \leq N}$ が与えられる. ただし, $A_{i,i}=0, A_{i,j}=A_{j,i}$ である.

$(1,2, \dots, 2N)$ の並び替え全体の集合を $\mathfrak{S}_{2N}$ とするとき,

$\displaystyle \max_{(P_{1,1}, P_{1,2}, \dots, P_{N,1}, \dots, P_{N,2}) \in \mathfrak{S}_{2N}} \bigoplus_{i=1}^N A_{P_{i,1}, P_{i,2}}$

を求めよ.

制約

$1 \leq N \leq 8$
$0 \leq A_{i,,j} \lt 2^{30}$
$A_{i,i}=0$ *1

解法1 (計算量の見積もり)

$1,2, \dots, 2N$ のペアの作り方を考える. すると, 作り方の場合の数は

$\displaystyle \begin{align} &\phantom{=}\dfrac{1}{N!} \dbinom{2N}{2} \dbinom{2N-2}{4} \dots \dbinom{2}{2} \\ &=\dfrac{2N(2N-1)}{2N} \cdot \dfrac{(2N-2)(2N-3)}{2N-2} \cdot \cdots \cdot \dfrac{2 \cdot 1}{2} \\ &=(2N-1)(2N-3) \cdots 1 \\ &=(2N-1)!! \end{align}$

であり, $N=8$ とすると, $15!!=2027025$ である. よって, 全てのペアリングの方法を効率よく生成できれば, 計算量 $O(N \cdot (2N-1)!!)$ で求めることができる.

全てのペアリングの方法を効率よく生成する方法を考える.

解法2 (ペアリングの生成)

闇雲にペアを作ろうとすると, ペアの名付け方だけ違うペアリングの方法が複数発生してしまい, 無駄になってしまう. しかし, 次のペアに着目することにより, 重複なくペアリングの方法を生成することができる.

まだペアができていない人のうち, 番号が最も小さい人と誰かでペアを組む.

よって, ペアを生成する際に上のようにしてペアを組むことにより, 全てのペアを無駄なく生成できる.

*1:実際には $A_{i,i}$ の値は与えられていない.