ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Grand Contest 046 B - Extension

B - Extension

解法

まず以下のようなDPを考えてみましょう。

 dp\lbrack i \rbrack\lbrack j \rbrack = 本問題の操作によって、縦  i 行、横  j 列になるまで操作してできる盤面の数

このDPで「上側に行を足し、その1つを黒く塗る」遷移と「右側に列を足し、その1つを黒く塗る」遷移をすれば良さそうですが、数えるものは最終的な盤面の数なので、途中の操作列が違っても盤面として同じものは重複しないように気をつける必要があります。

操作列が異なるのに結果が同じになるような操作は、具体的には以下のようなものです。

f:id:betrue12:20200621003842p:plain

このように、 i \times j の盤面で

  • 右上隅が黒くない
  • 最上行、最右列ともに黒マスが1つ
  • 初期状態から行、列がともに1つ以上追加されている

の全ての条件を満たすものは、 (i-1) \times (j-1) の盤面から2通りの操作で到達します。

より一般的には、黒マスがちょうど1つの行が上から  x 個・列が右から  y 個あり、それらが交差する場所に黒マスが存在しない場合、 (i-x) \times (j-y) の盤面から行・列を追加する順番が  _{x+y}C_{x} 通りあります。

※逆に重複パターンがこのようなものしかないことは、これ以外の盤面に対しては逆操作(黒マスがちょうど1つある最上行または最右列を取り除く)を考えた時に、操作できてかつ次も詰まないような操作が高々1通りしかないことから分かります。

よって、このような操作列のうち特定の1つしか遷移として採用しないというルールでDPをします。例えば「上に行を全て足した後、右に列を全て足す」ものしか採用しないことにしましょう。このときは右に列を追加する遷移のときに

  • その列の上端(右上隅)以外を塗る
  • 遷移前の最上行の黒マスが1つ
  • 初期状態から行が1つ以上追加されている

の全てを満たす場合、それは別の操作列で数えている盤面なので遷移をキャンセルするようにすれば良いです。

これを判定できるようにするためには、DPテーブルを拡張して

 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack a \rbrack\lbrack b \rbrack = 本問題の操作によって、縦  i 行、横  j 列になるまで操作してできる盤面で、最上行の黒マスが  a 個、最右列の黒マスが  b 個であるようなものの数

とすれば良いです(実際には  a, b のどちらかで良いです)。ここで判定に使うのは「黒マスがちょうど1つかどうか」なので、 a, b としては「0」「1」「2以上」の3通りを区別しておけば良いです。

遷移を「上側に行を足し、その右端/右端以外を黒く塗る」遷移と「右側に列を足し、その上端/上端以外を黒く塗る」遷移の計4通りに分けることで、遷移先の  a, b の計算とキャンセルすべきかどうかの判定をすることができます。右端以外/上端以外の遷移には、それぞれ候補となるマス数を係数として掛ける必要があります。

 dp\lbrack C \rbrack\lbrack D \rbrack\lbrack a \rbrack\lbrack b \rbrack a, b について合計したものが答えです。

ACコード

Submission #14500984 - AtCoder Grand Contest 046