体調が最悪。寝不足で頭が痛いし肌も荒れている。

---

今日解いた競プロの問題。

ARC143-B: 自力AC。ARCの水diffへの自信をつけたい。

問題文の条件を言い換えると「すべてのマスについて、そのマスは列内最大でない、もしくは行内最小でない」となる。否定をとると「あるマスがあって、そのマスは列内最大かつ行内最小である」となる。こっちの方が考えやすそうなので、それを数えて全体$N^2!$から引くことにする。

考察すると、列内最大かつ行内最小であるようなマスは1つしかありえないことが分かる。背理法で証明できる。

まず、そのようなマスが2つあるとしてそれぞれマスP,Qとする。定義より、マスP,Qは行も列も異なるはずである。次に、マスPと同じ行でマスQと同じ列のマス、マスPと同じ列でマスQと同じ行のマスをそれぞれマスA,Bとする。定義から、それぞれのマスに書いてある数字は$P<A<Q$かつ$Q<B<P$を満たすはずであるが、$P<Q$かつ$Q<P$は矛盾。よって列内最大かつ行内最小なるマスは高々1つである。

列内最大かつ行内最小であるようなマスの値は、N-1個のより大きい要素とN-1個のより小さい要素を必要とすることから$[N, N^2-N+1]$の範囲内である。以上の議論を踏まえると、列内最大かつ行内最小であるようなマスが存在するパターン数を$O(N^2)$で数え上げることができる。

マスの値を$x$とする。まずマスの位置が$N^2$通り。同じ列に入れる値の取り方&並べ方が$_{x-1}P_{n-1}$通り。同様に行は$_{n^2-x}P_{n-1}$通り。そして残りのマスの埋め方は$(N-1)^2!$通り。これを全てかけ合わせ、それを$N\leq x \leq N^2-N+1$について足し合わせればよい。

答えは$N^2! – \sum_{x=N}^{N^2-N+1} { _{x-1}P_{n-1}} \times {_{n^2-x}P_{n-1}} \times (N-1)^2$となる。