考察

塗られないマスの個数を最小化する問題に言い換えます。

ある行に注目すると、\(1\) 回の操作で塗られるマスは \(0\) 個か \(2\) 個です。 つまり、\(W\) が奇数の時、どの行も必ず \(1\) マスは塗られないマスが生じます。

列についても同様です。

解法

\(H,W\) の偶奇で場合分けを行います。

[1] \(H,W\) = 偶,偶

\(2 \times 2\) の正方形を敷き詰めるように塗ることで、全てのマスを塗ることができます。

[2] \(H,W\) = 偶,奇（奇,偶 も同様）

必ず \(H\) 個以上の塗られないマスが生じます。偶,偶と同様の塗り方をすることで、塗られないマスを \(H\) 個にすることができます。

[3] \(H,W\) = 奇,奇

\(H=W\) の場合

塗られないマスは \(H\) 個以上です。 また、塗られるマスの個数は \(4\) の倍数なので、塗られないマスの個数が \(H+3\) 個以下である塗り方を構成できれば最適です。

\(H=1,3\) の場合は自明です。 \(5 \le H\) の場合は、以下のような塗り方をすることで \(H\) が \(4\) 小さい問題に帰着できます。

maabbcc.m
.aabbccdd
ll?????dd
ll?????ee
kk?????ee
kk?????ff
jj?????ff
jjiihhgg.
m.iihhggm

\(H<W\) の場合（\(H>W\) の場合も同様）

右端 \(2\) 列を \(2 \times 2\) の正方形を敷き詰めるように塗ることで、\(W\) が \(2\) 小さい問題に帰着できます。

サンプル

\(H,W = 4,6\)

aabbcc
aabbcc
ddeeff
ddeeff

\(H,W = 5,6\)

aabbcc
aabbcc
ddeeff
ddeeff
......

\(H,W = 9,11\)

maabbcc.mww
.aabbccddww
llrnn.rddxx
ll.nnooeexx
kkqq.ooeeyy
kkqqpp.ffyy
jjr.pprffzz
jjiihhgg.zz
m.iihhggm..

\(H,W = 9,7\)

iaabb.i
.aabbcc
hhj.jcc
hh...dd
ggj.jdd
ggffee.
i.ffeei
xxyyzz.
xxyyzz.