ABC238 F - Two Exams
コンテスト本番、初の黄 diff AC。
でも E を諦めてるのでパフォはそれほどでもなかった……
問題概要
$ N人が$ 2回の試験を受けて、人$ iの順位はそれぞれ$ P_i, Q_iだった。
ただし、同点はなく、従って$ P, Qは$ 1, 2, \ldots, Nの順列になった。
今から$ N人のうち$ K人を選ぶ。ただし、選ばれた人$ xと選ばれなかった人$ yの組であって、$ P_x > P_yかつ$ Q_x > Q_yであるようなものが存在してはならない。
そのような$ K人の選び方は何通りあるかを$ \bmod \space 998244353で求めよ。
制約
$ 1 \leq N \leq 300
$ 1 \leq K \leq N
$ P, Qは$ (1, 2, \ldots, N)の順列
考察ステップ
まず、制約エスパーで$ Ο(N^3)という予想が出来る。
$ 300だと$ \logも付かない場合が多い。
そして、数が非常に多い数え上げなので、DPだろうと予想できる。
だが、シンプルに DP を
$ \mathrm{DP}_{i,j,k,l}=$ i人目まで見ていて、$ j人選んだ時の、選ばれなかった人の$ Pの最小値$ = kであり、同様に$ Qの最小値$ = l
とすると、時間、空間計算量が$ Ο(N^4)になって間に合わない。
こうなる原因は明らかで、順列が$ 2個あるのがめんどくさい。しかも大小条件がそれに伴って$ 2個ある。
ところが、これは例えば$ Pを規準にソートすることで$ Q_x > Q_yだけ気にしていればよくなるので、ソートしておくのが正解だろうと考えられる。
それだけで時間も空間も計算量が$ Ο(N^3)まで落とせる。具体的には
$ \mathrm{DP}_{i,j,k}=$ i人目まで見ていて、$ j人選んだ時の、選ばれなかった人の$ Qの最小値$ = k
として、DPをする前に人の情報を$ Pの昇順にソートしておけば良い。こうすると、人$ iを選ぼうとするときに、今まで選ばれたか選ばれなかったかに関係なく、少なくとも人$ iを選ぶならば
$ P_i > P_x (x < i)
が成立するのだ。よってこの後は追加で
$ Q_i > Q_x (x < i)
であるならば、出場させられないことだけを場合分けで処理すればよくなる。
日本語的な言い方をすれば、$ Pについてより順位が良い人から選ぶかどうかを決めている。そうすれば、今まで計算した結果に対して次にある人を選ぶかどうかを考えるとき、$ Pについては今まで選んだ人より順位が良い場合が存在しなくなる。
すると、$ Qについて今まで選ばなかった人の最もいい順位をだけ保持しておけば、今から選ぶかどうか決める人について、その人を選ぶことが題意に反するかどうかが分かる。
以上、DP は$ Ο(N^3)で更新することが出来て、この問題を解くことが出来た。
※冒頭の長いコメントはコンテスト本番中に書いていて、おかしいことになっています。読まないでください