日本語につき問題文は略。
公式解説 とは着眼点が異なる別解を紹介する。
長方形の条件
任意の行と列を反転させることで黒で塗りつぶせる、マス目のパターンの集合を とおく。
が満たすべき条件を考察する。まず、行と列の反転は同じ箇所に対して高々1度しか行う必要がなく、どの順番で行っても同じ結果が得られることに留意しておく。また、最終状態から考えると
は真っ黒に塗りつぶされた状態のマス目から、反転操作を行ってたどり着けるマス目のパターンの集合に等しい。（∵ 操作を逆回しにすれば黒に塗りつぶせるため）
操作はどのような順番で行っても良いので、とりあえず行をいくつか選んで反転させてから、列を反転させる。
こうしてできたマス目のパターンを列ごとに見ると、あるパターンと、それを反転させたパターン の高々2種類しか存在しないことが分かる。この あるパターン とは、始めに選んだ行の集合にほかならない。 *1
したがって、与えられたマス目のある部分長方形が に含まれるかどうかは、列ごとに考えてパターンが高々2種類のみか？を判定すれば良いことになった。
差分を取る
しかし、長さ2000もの0-1パターンの種別を判定するのはビットベクトル等を用いたとしても厳しい。そこで列同士の差分(XOR)を考えてみることにする。差分を考える理由は、 に含まれる長方形の列同士の関係は「等しい」か「反転」のどちらかであるため。本来長方形ごとに探したい列のパターンは異なるのだが、それらを全て
000...0 か 111...1 を探す問題に変換できる。
最大長方形の問題に
長方形の上端を固定して、行ごとに問題を解く。それぞれの列において、1行目と等しい連続する部分を下に最大限伸ばす。すると、高さの列が得られる。この高さの範囲内で、最も大きな長方形を求めればよい。これは蟻本でも紹介されている Largest Rectangle in a Histogram である。 *2
最大長方形問題の計算量は 、これを
回行う。高さを求める部分も全体で
なので、
でこの問題が解けた。
まとめ
公式解説で紹介されている、長方形の条件の便利な事実に気づかなくても問題を解くことができた。この解法のほうがステップが多く遠回りだが、一つ一つの発想のギャップは比較的狭く、多くの人が思いつきやすい解なのではと思う。*3
