今日解いた競プロの問題。

ARC145-C: なんとか自力AC。かなり厳しかった。

まず、スコアの最大値Mが実際どうなるのかを考えてみる。2つの長さNの数列A,Bがあり、1～2Nまでの値が1つずつ含まれている。数列や集合の類に対して定義される値の最大値・最小値について考えるとき、だいたい有用な考え方は「交換して損をしないか」だ。調べてみると、スコアが最大値をとるには$A_i>A_j$ならば$B_i>B_j$でなければならないことが分かる。これは計算してみればすぐにわかる。

この問題ではそれに加え、A,Bの値には1～2Nまでの値が1つずつ含まれているという強力な縛りがあるので、これらを踏まえるとA,Bは以下のような値、ないしその並べ替えしかありえないことが分かる。

$A=(1,3,5,7,…2N-1)$

$B=(2,4,6,8,…2N)$

ということで部分列としてこれを構成できるような順列Pの数を数えればよい。

次に、条件を満たす順列Pに対して数列A,Bの分け方は1通りに定まることを(ゆるく)証明する。まず順列Pの左端の数字をXとする。これに対応せらるべき数字は一意に定まる。(X=1ならば2、X=5ならば6など。)左端から数字を1つ取り去ってAに加える。Xに対応する数字はPに含まれているはずなのでこれも抜き取ってBに加える。これを繰り返すとスコアMをとるA,Bが構成される。部分列の定義を考えると、これ以外の方法ではスコアMをとるようなA,Bは構成できない。

次に並べ替えのパターン数を計算する。A,Bの値は上に示したようなものしかありえない訳だが、(1,2)と(3,4)の順番を並べ替えたり(1,2)を(2,1)にする自由度がある。これはすぐわかる通り$N!2^N$通りである。

最後、上に示したようなアルゴリズムで上に示したようなA,B部分列を構成できるような順列のパターン数を考える。これを求めた後で$N!2^N$を乗ずればそれが答えだ。

まず$N=1$のとき、これは$P=(1,2)$しかありえない。次$N=2$のとき、3,4をどこに挿入できるか考える。4は2の右隣にしか配置できないので4を置く。3は1の右隣から4の左隣までのどの位置にも挿入できる。

以下同様に考えていく。(2i-1,2i)を挿入するとき、2iは最右にしか置けない。2i-1は2i-3の右隣から2i-2の左隣までの任意の位置に挿入できる。これを元にすると時間計算量$O(N^3)$のDPが出来る。

これを超がんばって式変形を続けた結果、これカタラン数じゃんということに気付いてWikiから数式をコピペして終了した。これはひどい。

カタラン数はどうやら高度な組み合わせ問題と格闘するには必須の道具らしい。何度も遭遇すれば見えるようになってくるのだろうか。