keyence2019 D - Double Landscape

数え上げ何も分からん

解説

まず $ A,Bに同じ要素が含まれているのはありえないので答えは 0 通りになる。ここからはこれを除いた場合を考える。

重要な性質として、各行、列を swap しても条件を満たすような書き込み方の総数は変わらないことが挙げられる。

なので、$ A,Bをそれぞれソートしても問題ない。

もう一つ重要な典型として制約の小さいものから考えることがある。

仮に$ A,Bをソートして以下のようになったとする(解説放送の例と一緒)。

https://gyazo.com/60073a8decbc94ae0f26a7415fa71aa1

この場合 1 の入る場所から考えると、入る場所が多くて大変だが、 9 の入る場所から考えると、入る場所が少ないので楽(というか 1 通りしかない)。なので、9 の入る場所、 8 の入る場所、 7 の入る場所…という風に数え上げると、答えはその積になる。

ある整数$ x \ (1 \leq x \leq NM)が入る場所の数え上げ方は、以下の 3 通りの場合に分けられる。

$ xが$ A,Bどちらにも含まれている場合

これは 1 通りしかない(上の$ x = 9,8の場合を考えると分かる)

$ xが$ A,Bのどちらか片方に含まれている場合

今回は$ Aに含まれている場合を考える。$ Bに含まれている場合も同様に考えることができる。

上の例でいうと$ x = 6の場合で、この時は絶対に上から 3 行目に入ってないといけない。また、6 は左から 3 列に入れることができないので、左から 2 列目までのどれかに入ってないといけない。

一般の場合に拡張すると、$ xは下の赤い部分に入りうる。また、$ x + 1以上の整数は赤い部分に入ることは無い(最大値が$ xなので)ので、$ xが入る場所の個数は下の赤い部分の個数になる。

https://gyazo.com/1ed7b9db6a09be4129cffb4254695419

$ xが$ A,Bのどちらにも含まれていない場合

$ xは下の赤い部分に入りうる。しかし、この赤い部分には$ x + 1以上の整数も全部入っている。なので、$ xが入る場所の個数は下の赤い部分の個数から $ x + 1以上$ NM以下の整数の個数を引いたものになる。

https://gyazo.com/686551d337fe1657230892f701f4b9e4

これらの数え上げ方は、$ A,Bを昇順にソートしてからstd::lower_boundやstd::upper_boundを使うと楽に実装できる。