ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

BAPC2018 E - Entirely Unsorted Sequences

動的計画法(DP) 包除原理 逆元 数え上げ

問題
提出コード

問題

N個の数字が与えられるので、その数字を使って作れる数列のうち、以下のような条件を満たす数列の個数を10^{9} + 9で割った値を求めてください。

  • 全ての数字について、その数字より左側に自分より大きいものが存在する、もしくは右側に小さいものが存在する

例えば、{1,4,3}という数列について考えた時、4の右側に3が存在しているので、4は条件を満たしていますが、1より小さい数字は1の右側に存在していないので、この数列は上の条件を満たしていません。逆に、{3,4,1}という数列は上の条件を満たしています。

1\leqq N \leqq 5000
0 \leqq a_{i} \leqq 10^{9}

解法

先輩＋解説の解法になります。自分はそれを実装しただけです。
まず、a_{i}の重複がない場合を考えます。上の条件を満たすものを考えるのは見通しが悪いので、満たさないものを考え、全体から引けばよいです。
上の条件が満たさないものとは、

  • 数列のうち少なくとも1つ、左側には全て自身以下の数字が、右側には全て自身以上の数字が並んでいる数字がある

ということです(最初の条件と区別するため、条件Xと呼ぶことにします)。
これを包除原理を用いて求めます。
例えば、i,j ( i \lt j)の二つが条件Xを満たすとします。
このとき、k \lt i , i \lt k \lt j , j \lt kの3種類の数字kの集合が存在しますが、それぞれの中でどのような順番に並び替えても、i,jは条件Xを満たします。
これを踏まえて、以下のようなDPを考えます。
dp[i][j] = i番目までの数列について、i番目の要素が条件Xを満たしかつ、全体でj個以上の要素が条件Xを満たすようなものの個数
このDPの遷移は、k \lt iを満たすkが条件Xを満たす際、k + 1からi-1番目の間の数字はどのような順番にしても、k,i番目の数字はどちらも条件Xを満たすことに注目すると、
\displaystyle dp[i][j] = \sum_{k=1}^{i-1}dp[k][j-1] \times (k+1からi-1番目までの数字の順列の通り数)
となります。
あとは、包除原理を利用して、

  • jが奇数ならば、dp[i][j] \times (i+1以降の順列の通り数) を足す。

  • jが偶数ならば、dp[i][j] \times (i+1以降の順列の通り数) を引く。

という操作を繰り返すと、求めたい”少なくとも1つの数字が条件Xを満たす”数列の個数を、重複なく求めることができます。
そして、上のDPはO(N^{3})ですが、jは偶数であるか奇数であるか、という情報さえあればよいので、2通りに絞ることができ、O(N^{2})に計算量を落とすことができます。
\displaystyle dp[i][j] = \sum_{k=1}^{i-1}dp[k][1-j] \times (k+1からi-1番目までの数字の順列の通り数)
となります( jは0か1です)。
そして、求めた”少なくとも1つの数字が条件Xを満たす”数列の個数を、(1からN番目までの数字の順列の通り数)から引けば、最終的な答えとなります。


さて、順列の部分では、あえて階乗の記号を使わずに記述しました。というのも、数字が重複している場合を考えなければならないからです。
先に全ての数字a_{i}をソートしておきます。
perm[i][j] = i番目からj番目の数字を使った順列の個数
とします。
すると、
perm[i][j] = \frac{perm[i][j-1] \times a_j}{(a_{j}の個数)}
となります。
これを前計算しておくことで、上のDPの際に、O(1)で計算ができます。
あとは、上のDPとこの前計算を実装すると、この問題を解くことができます。

感想

数えづらいものは全体から逆を引いて求める、高校数学でも時々見かけましたが、肝心なときに思いつきませんね…
今回はさらに、包除原理と重複ありのセットだったので、さらにごたごたしていました。
実装も、他の実装難問題に比べるとマシなはずなのですが、結構やらかした箇所が多かったので、全体的に悔しい結果となりました。