AtCoder Regular Contest 145 C問題 Split and Maximize

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$(1,2, \dots, 2N)$ の順列 $P$ に対して, スコア $\operatorname{Score}(P)$ を次のように定める.

$P$ を順序を保ったまま, 2つの部分列 $A=(A_i), B=(B_i)$ への分割を全て考えたときの $\displaystyle \sum_{i=1}^N A_i B_i$ の最大値

$(2N)!$ の順列全てに対するスコアの最大値を $M$ とする. このとき, $\operatorname{Score}(P)=M$ を満たす $(1,2, \dots, 2N)$ を満たす順列 $P$ の個数を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$

解法1 ( $M$ の決定)

まず, $M$ がどのような値になるかを特定する.

$P=(1,2, \dots, 2N)$ のとき, $A=(1,3,5, \dots, 2N-1), B=(2,4,6, \dots, 2N)$ とすると, $\displaystyle \sum_{i=1}^N A_i B_i=\sum_{i=1}^N (2i-1) \cdot 2i$ である.
整数 $a,b,c,d$ に対して, $a \lt b \lt c \lt d$ のとき, $ad+bc \lt ac+bd \lt ad+bc$ である. このことから, 任意の分割について, $\sum_{i=1}^N A_i B_i \leq \sum_{i=1}^N (2i-1) \cdot 2i$ であり, 等号成立は総和の各項が $(2i-1) \cdot 2i$ のどれか (積の順番は考慮しない) に一致していることである.

よって, $\displaystyle M:=\sum_{i=1}^N (2i-1) \cdot 2i$ であることがわかった.

解法2

そして, 問題は次のように帰着することができた.

$(1,2, \dots, 2N)$ の順列 $P$ のうち, 以下を満たすのはいくつあるか? ただし, $E_k=\{2k-1,2k\}$ とする.

を順序を保ったままの2つの部分列のうち, 以下を満たすものが存在する.
- 任意の $i=1,2,\dots, N$ に対して, $\{A_i, B_i\}=E_{k_i}$ となる $k_i$ が存在する.

条件を満たすような順列 $P$ に対して, その条件を満たす順序を保ったままの2つの部分列 $A,B$ は一意である. このことから, さらに分割 $A,B$ を固定して場合にそのような分割が存在する順列の個数を求めれば良い.

ここで, 対称性から, ある $A,B$ の場合を考え, それに分割 $A,B$ として可能な場合の数をかければよい.

可能な分割 $A,B$ の場合の数は各ペアがどの場所に対応させるかで $N!$ 通り, それぞれに対して, 各ペアのうちどちらを $A$ , どちらを $B$ に対応させるかで $2^N$ 通りである. よって, $2^N \times N!$ 通りである.

特定の $A, B$ に分割できる順列の数を考える. これは次の問題を考えることになる.

$2N$ 個のボールがある. 色 $1,2, \dots, N$ のボールが $2$ 個ずつあり, そのうち一方は印がついている. $2N$ 個のボールを横一列に並べる方法で, 以下を全て満たすのは何通りか?

印がついていない $N$ 個のボールに着目すると, 左から色 $1$ , 色 $2,\dots$ , 色 $N$ の順に並んでいる.
印がついている $N$ 個のボールに着目すると, 左から色 $1$ , 色 $2,\dots$ , 色 $N$ の順に並んでいる.
印がついているそれぞれのボールについて, そのボールより左 (自分自身含む) にある印がついていないボールの数は印がついているボールの数以上である.

この問題は印がついていない色 $i$ ボールを $i$ 番目の ${\tt (}$ , 印がついている色 $i$ ボールを $i$ 番目の ${\tt )}$ に対応させることにより, 長さ $2N$ の正しい括弧列の個数と一致することがわかる. 従って, 答えは $n$ 番目のカタラン数を $\operatorname{Catalan}(n)$ とすると, $\displaystyle \operatorname{Catalan}(N)=\dfrac{1}{N+1} \dbinom{2N}{N}$ である.