今度こそ*1 今年最後の記事。
問題
カンガルーたちは、以下の条件を満たす限り、カンガルーが他のポケットに入るという操作を繰り返す。
- $A_{i} < B_{j}$ を満たすカンガルーの組である
- カンガルー $i$ が他のカンガルーのポケットに入っていない
- カンガルー $j$ のポケットにカンガルーがいない
最終的なカンガルーたちの状態は何通りあるだろうか。
- $1 \leq N \leq 300 $
- $1 \leq B_{i} < A_{i} \leq 10^9 $
観察
体の大きさとポケットの大きさの列をそれぞれソートして、以下の図を考える。
上図において、カンガルーがポケットに入ることを上から下に線を引いて表現する。 カンガルーのポケットの入り方の状態を数えることは、上図での線の引き方を数えることと同等である。 線を引く時の条件は、以下の3つ。
- カンガルーの体よりポケットのほうが大きい
- 各カンガルーからポケットに伸びる線は高々一つである
- 各ポケットには高々一つの線が入る
なお、制約からカンガルーの体は自身のポケットより大きいので、自分自身のポケットに入ってしまう心配はない。
だが、上に挙げた条件だけでは「最終状態か？」どうかの判別はできない。
「図でまだ線が引ける」ならば最終状態ではないのだが、残念ながらその条件が見えてこないので
、$A = \{2, 4, 6, 8\}$、$B =\{1, 3, 5, 7\}$ の最終状態と、そうでない例をいくつか列挙してみる。
【最終状態】
【最終状態ではない】
図をよく見ると、「下段の線が引かれていない数の最大値*2」が、「上段の線が引かれていない数の最小値*3」を上回る場合、最終状態ではないと分かる。 これは、「カンガルーが入っていないポケットの大きさの最大値」が、「どのポケットにも入っていないカンガルーの大きさの最小値」を上回ることなので、当然そのペアはまだポケットに入ることができるためである。
では、最終状態を「上段の線が引かれていない位置」の左端インデックス（以降、$P$ とおく）で場合分けをすることを考えよう。当然、$P$ が異なれば、最終状態は異なる。*4逆に、各最終状態において、どのポケットにも入っていないカンガルーは必ず一つ存在するので、その最も右のインデックスを $P$ と置くことができる。したがって、$P$ の位置を全て試して、それぞれの場合を数えて合計すれば答えが出せる。
解法
$P$ を固定したとき、$ A_{P} ＜ B_{q} $ を満たす $q$ の最小値を $Q$ とおく。線の引き方は
- 条件1: $Q \leq q$ の各ポケットに、$P$ 以外からの線が引かれている（線が引かれていないポケットが少なくとも１つあると、$P$ から線が引けるので最終状態ではない）
- 条件2: $p < P$ の各カンガルーは、どこかのポケットに入っている（Pの条件から）
を満たせばよい。ここで、数え上げを下図のように分割する。
- 赤い部分：$p ＜ P$、$q ＜ Q$ を満たすペア $(p, q)$ における、線の引き方の数え上げ
- 青い部分：$P ＜ p$、$Q \leq q$ を満たすペア $(p, q)$ における、線の引き方の数え上げ
赤い部分の $p ＜ P$ で、ポケットに入った数を $x$ とした場合の数を $ DPL_{x} $、 青い部分の $Q \leq q$ で、カンガルーが入った数を $x$ とした場合の数を $ DPR_{x} $ とおく。
ここで、条件を満たすためには、赤い部分で余ったカンガルーの数と、青い部分で余ったポケットの数が等しい必要がある。*5 数が等しければ、それぞれの余り同士では必ず線を引くことができ、それは余った数を y として $ y! $ である。結果、場合の数は各 $y$ について、$ DPL_{P-y} \times DPR_{N-Q-y} \times y! } ] を合計した値となる。これを各 [tex: {P$ について合計すれば最終的な答えになる。
解答コード
C++です。*6
