ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Grand Contest 043 D - Merge Triplets

AtCoder プログラミング競技プログラミング

D - Merge Triplets

解法

操作の説明で登場する長さ $3$ の数列たちを「ミニ数列」と呼ぶことにします。

結果的にできる順列にどのような特徴があるかを考える上で、まず一番大きな値に注目すると良いと思います。

最大値 $3N$ は、 $3N$ が存在しているミニ数列以外の要素全部と、 $3N$ と同じミニ数列にあって $3N$ より手前にある要素が全て出た後でないと手をつけられません。そして $3N$ が取り出された後は、そのミニ数列に残っている通りの順番で取り出され、操作が完了します。

f:id:betrue12:20200322004240p:plain

ではその手前はどうなるかと言うと、やはり残っている要素のうち最大のものについて同じことが言えます。

f:id:betrue12:20200322004557p:plain

つまり最終的にできる順列は、

残っている要素のうち最大の要素と、その後ろにくっ付く任意の0～2個の要素を1グループとして、後ろから順番に並べる。

という操作を繰り返すことによってできることが分かります。ただしこれは必要条件です。

実際にはこの条件に加えて、このグループたちが長さ $3$ のミニ数列 $N$ 個に収まっている必要があります。収める上で邪魔になるのは長さ $2$ のグループで、具体的には長さ $1$ のグループ数が長さ $2$ のグループ数以上であることが必要です。

逆にこのときは各グループを要素数が合計 $3$ 個ずつになるようにミニ数列に分配し、各ミニ数列では先頭の要素が小さいグループが前になるようにそれぞれ並べることで、作りたい順列を実際に作れることが分かります。

これで必要十分条件が洗い出せたので、次のようなDPを組むことができます。

$dp\lbrack i \rbrack\lbrack j \rbrack=$ 後ろから $i$ 個の要素を既に決めていて、長さ1のグループ数から長さ2のグループ数を引いた値が $j$ であるような場合の数

遷移を考えると、以下のようになります。

次に長さ $1$ のグループを作る：残っている最大の要素だけを使うので、係数 $1$ で $dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ に遷移します。
次に長さ $2$ のグループを作る：残っている最大の要素の他に $1$ 個自由な要素を選ぶので、係数 $3N-i-1$ で $dp\lbrack i+2 \rbrack\lbrack j-1 \rbrack$ に遷移します。
次に長さ $3$ のグループを作る：残っている最大の要素の他に $2$ 個自由な要素とその順番を選ぶので、係数 $(3N-i-1)(3N-i-2)$ で $dp\lbrack i+3 \rbrack\lbrack j \rbrack$ に遷移します。

これを計算して、 $j \ge 0$ であるような $dp\lbrack 3N \rbrack\lbrack j \rbrack$ の総和が答えになります。

ACコード

Submission #11056101 - AtCoder Grand Contest 043

このコードでは残っている要素数をDPテーブルの添え字にしていますが、やっていることは同じです。 $j$ が負になり得ることについては適切にオフセットを付ける等の対応をしましょう。