AtCoder Beginner Contest 134 F - Permutation Oddness

F - Permutation Oddness

※問題文で与えられている $n, k$ は小文字ですが、 $k$ を添え字として使いたいので本記事では $N, K$ と表記します。

解法

順列のDP

順列の場合の数を求める問題です。何か条件を満たす数列の個数を求める問題として「左からDP」というのはメジャーな解法ですが、順列の場合は各数字をちょうど1回しか使えないという性質のためDPがやりにくいです。例えば

$dp\lbrack i \rbrack\lbrack S \rbrack\lbrack k \rbrack =$ 左から $i$ 番目の場所まで決めて、既に使った整数の集合が $S$ で、それまでの奇妙さの合計が $k$ である場合の数

みたいなのを考えてDPすることは一応できるのですが、これは結局bit DPなので $N$ が大きいと状態数が爆発してしまいます。

なので順列の数え上げについては、

そもそもDPしない、数学などでがんばる
使った整数の集合を具体的に覚えておかなくていいDPを組む

などの工夫が必要になります。後者として例えば挿入DPがあり、これはDPで持つ情報を「数の集合」ではなく「ある条件を満たす場所の個数」として持つようなDPです。このように何かの「個数」で状態を持つことができれば状態数を抑えることができます。

今回の問題も、そのような方針でDPを組むことができます。

箱根駅伝DP

この問題に由来して、俗に「箱根駅伝DP」と呼ばれているテクニックです。

整数 $1, ..., N$ までの各整数について、以下のように「箱」と「ボール」を考えます。最初にそれぞれの箱に、仮で同じ番号のボールを入れておきます。

f:id:betrue12:20190721134037p:plain

この箱とボールの組を左から見ていきながら、箱にボールを入れたり入れなかったりします。まず最初の箱1＋ボール1については、

箱1にボール1を入れる。
箱1にボール1を入れない。ボール1が「保留ボール」として残り、箱1も「保留箱」として残る。

の2パターンがあります。

次の箱2＋ボール2について。もし箱1にボール1を入れていた場合は全く同じ2パターンを考えれば良いですが、保留があった場合には事情が異なります。つまり上の2パターンに加えて、

箱2に保留ボール1を入れて、ボール2を保留にする。
箱2に保留ボール1を入れて、保留箱1にボール2を入れる。
箱2を保留にして、ボール2を保留箱1に入れる。

の3つ、合計5パターンがあります。

この遷移をDPで扱っていきます。このとき保留にしているボールや箱を集合で持つとやっぱり状態数が爆発しますが、これを「個数」だけで上手く扱います。保留しているボールと箱の個数は等しいので、

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack =$ 左から $i$ 番目の場所（箱＋ボール）まで見終わって、保留しているボールと箱の個数がともに $j$ 個で、それまでの（？）奇妙さの合計が $k$ である場合の数

というDPを考えることができます。順列が完成しているときにはもちろん保留がゼロなので、答えは $dp\lbrack N \rbrack\lbrack 0 \rbrack\lbrack K \rbrack$ として求められるでしょう。

先ほどの5パターンについて、遷移にかかる係数と $j$ の増減はそのまま求めることができます。保留箱や保留ボールを選ぶたびに場合の数には $j$ 倍の係数が掛かり、パターンによって遷移後の $j$ が $j-1, j, j+1$ のいずれかになります。以下の図で列挙します。

f:id:betrue12:20190724013018p:plain

ただ1つ困ったことがあり、それは図中でも?と記載している $k$ の更新です。箱にボールを入れた時に奇妙さを直接足そうとすると、箱とボールの具体的な数字が分からないと求められません。その扱いを詰められればゴールです。

奇妙さ $k$ の更新

$k$ の更新ですが、イメージは $i$ を1個進めるたびに奇妙さを「積み立てておく」感じです。具体的に説明します。

保留ボールとしてボール $x$ 、保留箱として箱 $y$ があったとします。そしてDPにおいて、 $i$ 番目の場所を見ているものとします。ここで $x \lt i$ かつ $y \lt i$ です。

ここでもし箱 $i$ に保留ボール $x$ を入れれば奇妙さは $i-x$ 増えます。また、保留箱 $y$ にボール $i$ を入れれば奇妙さは $i-y$ 増えます。これらは「今入れたときに増えるはずの奇妙さ」です。

しかしここでどちらも入れなかったとしましょう。そして見ている場所を $i+1$ 番目にずらすと、さきほどの「今入れたときに増えるはずの奇妙さ」はそれぞれ1ずつ増えることになります。

このように、箱やボールが保留されている状態で見ている場所をずらすたびに奇妙さを1ずつ足していくのが「積み立て」の考え方です。つまり保留箱と保留ボールがともに $j$ 個の状態で見ている場所 $i$ を1つずらすときに、奇妙さ $k$ に $2j$ を加算してしまうことで、奇妙さの合計を正しく管理することが出来るのです。

場所 $i$ を見ているときにボール $i$ や箱 $i$ を保留にしても、その時点では「今入れたときに増えるはずの奇妙さ」は0なので特に足す必要はありません。つまり先ほどの図で?と記していた遷移先の奇妙さの値は、全て $k+2j$ とすることができます。先ほどの図に合わせて言えば、見る場所を $i-1\to i$ とずらしたときに増える分ということになります。