今回扱うのはyukicoder contest YNUCPC Contest 2 L問題 No.3430 Flip the Gridです。公式解説が間違っていると思うので、その解説をしてみます。

問題の概要

正確な問題文はこちらです。

各マスに$01$が書かれた$H \times W$のマス目が与えられます。好きな回数だけ隣接$2 \times 2$マスの$01$を反転させた時の$1$の個数の最小値を求めてください。

前置き

奇数個の$1$が書かれた行・列の個数をそれぞれ $R, C$と置きます。公式解説に書かれているように、答えは$\max(R,C)$です。

しかしながら、公式解説には２点の誤りがあります。

まず軽微な誤植として、公式解説で言及されている「下限」は恐らく全部「下界」の誤植です。というのも「このことから、全体の和の個数の下限は$\max(R,C)$であることがわかり、答えの下限が定まります」という文章が個数の下からの評価のみをした後に書かれているので、下限であることが一切議論されていないからです。そもそも下限であることが本当にこの時点で従っているのであれば、非空有限性から最小性も従ってしまい「下限の実現可能性」の章が不要になります。

そして本題として、$\max(R,C)$は結果的に下限にもなっているのですが、残念ながら公式解説の「下限の実現可能性」の議論を踏まえても下限が実現可能である（つまり最小値である）ことの証明は書かれておらず、その意味で議論が間違っています。何故ならば「下限の実現可能性」の議論で証明されているのは「初期配置と$(R,C)$が等しい任意の$01$配置は操作で移り合う」という全称命題だけで、実際に下限であることを証明するためには追加で「初期配置と$(R,C)$が等しい$01$配置であって$1$の個数が$\max(R,C)$と一致するものが存在する」という存在命題を示す必要があるからです。

解説

上述した存在命題を証明すれば良いです。命題の成否は転置で不変なため、必要ならば転置することで$R \leq C$を仮定します。

$R \bmod 2$と$C \bmod 2$は初期配置における$1$の個数を$2$で割った余りにほかならないので、一致します。すなわち$R \equiv C \pmod{2}$が成立します。

ここで各マスに$0$が書かれた$H \times W$のマス目を用意します。ますその対角マスのうち左上から$R$個の数値を$1$に変更します。

次に$R$が偶数ならば、$R+1$行目の$R+1$列目から$C$列目のマスの数値を$1$に変更します。

そして$R$が奇数ならば、$R$行目の$R+1$列目から$C$列目のマスの数値を$1$に変更します。

これにて$R + (C - (R+1) + 1) = C = \max(R,C)$個の$1$が記載されました。

定義から、$1$の個数が奇数個である列の個数は$C$個です。

$R$が偶数ならば、$R+1$行目に記載された$1$の個数は$C-(R+1)+1$個であり、$R \equiv C \pmod{2}$よりこれは偶数です。従ってこの場合は$1$の個数が奇数個である行の個数は$R$個です。

$R$が奇数ならば、$R$行目に記載された$1$の個数は$C-R+1$個であり、$R \equiv C \pmod{2}$よりこれは奇数です。従ってこの場合も$1$の個数が奇数個である行の個数は$R$個です。

これにて望ましい$01$配置の存在が示せました。

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。