問題解決の宝石箱

競技プログラミング/数学ネタ置き場

JOI春合宿 2012年 Day3-B カンガルー

今度こそ*1 今年最後の記事。

問題

JOI春合宿 2012年 Day3(PDF)

【JOI春合宿 2012年 Day3-B : カンガルー】
 {N} 匹のカンガルーがいる。それぞれの体の大きさは { A_{i} }、ポケットの大きさは  {B_{i}} である。
カンガルーたちは、以下の条件を満たす限り、カンガルーが他のポケットに入るという操作を繰り返す。

-  {A_{i} < B_{j}} を満たすカンガルーの組である
- カンガルー  {i} が他のカンガルーのポケットに入っていない
- カンガルー  {j} のポケットにカンガルーがいない

最終的なカンガルーたちの状態は何通りあるだろうか。

  •  {1 \leq N \leq 300 }
  •  {1 \leq B_{i} < A_{i} \leq 10^9 }

観察

体の大きさとポケットの大きさの列をそれぞれソートして、以下の図を考える。

f:id:hama_DU:20161231101152p:plain

上図において、カンガルーがポケットに入ることを上から下に線を引いて表現する。 カンガルーのポケットの入り方の状態を数えることは、上図での線の引き方を数えることと同等である。 線を引く時の条件は、以下の3つ。

  • カンガルーの体よりポケットのほうが大きい
  • 各カンガルーからポケットに伸びる線は高々一つである
  • 各ポケットには高々一つの線が入る

なお、制約からカンガルーの体は自身のポケットより大きいので、自分自身のポケットに入ってしまう心配はない。

だが、上に挙げた条件だけでは「最終状態か?」どうかの判別はできない。 「図でまだ線が引ける」ならば最終状態ではないのだが、残念ながらその条件が見えてこないので {N = 4} {A = \{2, 4, 6, 8\}} {B =\{1, 3, 5, 7\}} の最終状態と、そうでない例をいくつか列挙してみる。

【最終状態】

f:id:hama_DU:20161231103943p:plain

【最終状態ではない】

f:id:hama_DU:20161231104331p:plain

図をよく見ると、「下段の線が引かれていない数の最大値*2」が、「上段の線が引かれていない数の最小値*3」を上回る場合、最終状態ではないと分かる。 これは、「カンガルーが入っていないポケットの大きさの最大値」が、「どのポケットにも入っていないカンガルーの大きさの最小値」を上回ることなので、当然そのペアはまだポケットに入ることができるためである。

では、最終状態を「上段の線が引かれていない位置」の左端インデックス(以降、 {P} とおく)で場合分けをすることを考えよう。当然、 {P} が異なれば、最終状態は異なる。*4逆に、各最終状態において、どのポケットにも入っていないカンガルーは必ず一つ存在するので、その最も右のインデックスを  {P} と置くことができる。したがって、 {P} の位置を全て試して、それぞれの場合を数えて合計すれば答えが出せる。

解法

 {P} を固定したとき、 { A_{P} < B_{q} } を満たす  {q} の最小値を  {Q} とおく。線の引き方は

  • 条件1:  {Q \leq q} の各ポケットに、 {P} 以外からの線が引かれている(線が引かれていないポケットが少なくとも1つあると、 {P} から線が引けるので最終状態ではない)
  • 条件2:  {p < P} の各カンガルーは、どこかのポケットに入っている(Pの条件から)

を満たせばよい。ここで、数え上げを下図のように分割する。

f:id:hama_DU:20161231102735p:plain

  • 赤い部分: {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!  } を合計した値となる。これを各  {P} について合計すれば最終的な答えになる。

解答コード

C++です。*6

kangaroo.cpp

*1:http://hama-du-competitive.hatenablog.com/entry/2016/12/25/171803

*2:図の赤い四角に書かれた数値

*3:図の青い四角に書かれた数値

*4:確かめよう。

*5:赤が多いと条件2が、青が多いと条件1が満たせなくなる。確認しよう。

*6:JOI春合宿ではCかC++しか使えないため