キーエンスプログラミングコンテスト 2020 F - Monochromization

解説放送を観て解いたので、その方針をベースに書きます。

解法

まずは判定問題

まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。

ある最終状態の盤面から操作を逆回しして考えます。盤面においてもしマスの色が全て同じ行や列がある場合、そこを操作することにすると、それらのマスは「操作前は何色でも良い」という扱いになります。この処理によって行や列を取り除き、新たにマスの色が全て同じ行や列ができた場合、それらも取り除くことができます。「ヨッシーのクッキー」みたいなイメージです。

f:id:betrue12:20200119163802p:plain

この操作をやれるだけ繰り返して残ったマスは、初期盤面からずっとこのままでないといけません。つまりこれらのマスが全て初期盤面と一致していることが、この盤面を作れる必要十分条件になります。

数え上げの軸を決める

上記の判定方法から、数え上げの方針を立てます。上記判定方法では最終盤面から取り除ける行と列を考えていきましたが、数え上げでは逆に、取り除く行と列の組み合わせパターンを全探索して、そのような取り除き方に対応する盤面を数えることにします。行と列で $2^{H+W}$ 通りのパターンが考えられます。

このとき重複カウントを防ぐためには、初期盤面から指定した行・列を取り除いた後の盤面において、これ以上列や行を取り除くことができないようになっている必要があります。もしまだ取り除ける行や列がある場合は、それを取り除く扱いにしたほうのパターンで数えるからです。

f:id:betrue12:20200119164533p:plain

また全てのマスを取り除くようなパターンは、「全ての行と列を取り除く」という1通りだけ数えるようにします。

このようにすると初期盤面から作れる盤面が重複なく数えられるようになります。あとは各パターンについて、取り除いた、つまり「操作した部分」の色の塗られ方を数えれば良いです。この塗られ方は、行をいくつ、列をいくつ操作することにしたかという数だけに依存します。これを計算しましょう。

ヤング図形への帰着

操作した行数を $x$ 、列数を $y$ とします。操作した行と列を適切に端に寄せると、操作した部分の形は以下のようになります。

f:id:betrue12:20200119164911p:plain

まずは簡単な方、長方形になる $x=H$ かつ $y=W$ の場合から考えましょう。

実はこの長方形の塗り方は、この中の行や列を並び替えることで、以下のような「ヤング図形」になることが分かります。

f:id:betrue12:20200119165112p:plain

このようなヤング図形は、先ほどの「ヨッシーのクッキー」操作によって必ず全てのマスを取り除けます。逆に全てのマスを取り除けるような盤面を、その取り除く順番に基づいて

白で塗る行は上から、黒で塗る行は下から、取り除いた順序（つまり、塗る順序の逆順）で並べる。
同様に、白で塗る列は左から、黒で塗る列は右から並べる。

という規則で並び替えると、その盤面はヤング図形になります。

よって数えるべき値は、このような $x$ 行 $y$ 列の盤面にできるヤング図形から、行・列の並び替えを行ったものと等しいです。ただし境界線のどちら側が白でどちら側が黒かは片方に決めておきます。上図では境界線の右または下が黒と決めています。

あるヤング図形から行・列の並び替えを行ってできる盤面数は、まず全ての並び替え $x!y!$ 通りを考えて、「同じ行または列が $k$ 個ある」というグループそれぞれについて $(k!)^{-1}$ を掛ければ良いです。これを全てのヤング図形について足します。

白黒の境界をグリッド上の経路とみなすと、これは経路を数え上げるDPで計算できます。この経路において同じ方向に $k$ ステップ連続で進むたびに同じ行または列 $k$ 個のグループができるので、これに対応して $(k!)^{-1}$ を掛けて遷移するようにすれば良いです。

これで長方形領域を全て塗る場合の塗られ方の数が計算できるようになりました。

L字領域の数え上げ

最後に $x \lt H$ かつ $y \lt W$ 、つまり塗る領域がL字になる時の塗られ方の数を数えます。

行・列のはみ出ている部分の塗られ方は、行・列それぞれの塗り方だけに依存します。そのためまずは行のうち白く塗る本数 $x_{1}$ と列のうち白く塗る本数 $y_{1}$ を全探索します。それぞれの黒く塗る本数を $x_{2} = x - x_{1}$ 、 $y_{2} = y - y_{1}$ と表記します。

まず行・列それぞれの中での白と黒の並べ方で $_{x}C_{x_{1}}\times _{y}C_{y_{1}}$ 通りの場合があり、これらそれぞれの場合についてはみ出ている領域の塗られ方は異なるので、これらは全て区別されます。

そして行・列をそれぞれ白と黒を固めるように並び替えると、操作する行と列が交わる長方形領域は以下のようになります。

f:id:betrue12:20200119170355p:plain

つまりサイズ $x_{1}y_{1}$ の必ず白になる領域、サイズ $x_{2}y_{2}$ の必ず黒になる領域、そして白と黒が交わる領域がサイズ $x_{1}\times y_{2}$ とサイズ $x_{2}\times y_{1}$ の2つあります。

そして白と黒が交わる領域の塗られ方は、またしても行・列を適切に並び替えることで先ほどのヤング図形になります。つまり、この部分は先ほどと同じDP計算の結果が使えます。

まとめ

解法をまとめると以下のようになります。

前計算パート

$x \le H, y \le W$ なる $x, y$ について、 $x$ 行 $y$ 列の長方形領域を全て塗る場合の塗られ方の数、つまり入れ替えを考慮したヤング図形の個数を先ほど説明したDPで計算する。これを $Y\lbrack x\rbrack\lbrack y\rbrack$ と書くことにする。

$x \lt H, y \lt W$ なる $x, y$ について、 $x$ 行 $y$ 列を塗ったL字領域を全て塗る場合の塗られ方の数を計算する。これは $0 \le x_{1} \le x, 0 \le y_{1} \le y$ となる $x_{1}, y_{1}$ 全てについて $_{x}C_{x_{1}}{}_{y}C_{y_{1}} Y\lbrack x_{1}\rbrack\lbrack y-y_{1}\rbrack Y\lbrack x-x_{1}\rbrack\lbrack y_{1}\rbrack$ を全て合計したものである。この値を $L\lbrack x \rbrack\lbrack y \rbrack$ と書くことにする。

答え計算パート

操作する行、列のパターン $2^{H+W}$ 通りを全探索する。ここで全てのマスを操作するようなもの、初期盤面において指定した行・列を取り除いたあとにまだ取り除ける行・列が存在するようなものは無視する。操作する行数を $x$ 、操作する列数を $y$ として $L\lbrack x \rbrack\lbrack y \rbrack$ を答えに足す。

最後に「全ての行・列を操作する場合」として $Y\lbrack H\rbrack\lbrack W\rbrack$ を答えに足す。