ARMERIA

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

早稲田大学プログラミングコンテスト2019 E - Artist

早稲田大学プログラミングコンテスト2019 - AtCoder

解法

まず気付くべき点は、行の区切り位置と列の区切り位置を独立に考えられることです。行・列ともに、それぞれの区切り位置を境として黒いマスの個数が反転します。

そのためまずは行(列も同様)ごとの黒いマスの個数を数えて数列を作ります。そしてその数列を2つに区切る位置であって、2つに区切られた数列が両方とも回文になるようなものを数えればよいです。

f:id:betrue12:20190310215431p:plain

ただしたくさんの区切り位置についてこの回文判定を毎回計算していると時間が足りません。このように数列や文字列の色々な連続部分列について回文かどうかを効率的に判定したいときに、「Manacherのアルゴリズム」というものが使えます。

これは数列の全ての要素について、「その要素を中心とする連続した部分を見た時に、最大どれだけの長さが回文になるか?」を計算するものです。一般には回文判定(中心要素から端要素までの長さ)を求めるようにしていることが多いようです。計算量は数列の長さを  N として  O(N) であり、1回計算すればその結果を使って全ての連続部分列についての判定ができるので今回の用途にぴったりです。

注意点としてManacherは「その要素を中心とした」回文を考えるため、必然的に奇数長になります。そのため要素の間にダミーの値を挟んだ長さ  2N-1 の数列を用意し、それに対してアルゴリズムを適用することで偶数長の回文も求められるようにします。

ということで、ダミーを挟んだ状態の数列にManacherを適用し、元の数列の  i 番目の要素までで区切った時にそれぞれが回文になるための条件を考えましょう。これを求めるのは実験してみるのが良くて、0-indexedで書くと

  • 左側:中心は  i で、必要な回文半径は  i+1
  • 右側:中心は  N+i で、必要な回文半径は  N-i-1

です。ここで  N と表記しているものは行または列の個数(問題文中の  M, N )です。以下は具体例です。

f:id:betrue12:20190310221522p:plain

この方法で行・列ごとに条件を満たす区切り位置の個数を求めて、それを掛け算したものが答えです。

ACコード

Submission #4537644 - 早稲田大学プログラミングコンテスト2019

 N, M をそのまま使うと間違えそうだったので、コードでは  R, C にしています。