ARC119-Eを解いた.
問題
×
の赤青二色のグリッドが与えられる.
赤マスに対してそのマスを含む行又は列を全て白く塗れる.
白マスの数を最大化する操作を一つ構築せよ.
解法
赤であるマスについて、頂点
と頂点
の間に辺を張った二部グラフを考えると、完全に独立とはいかないが分けて考えられそうだ.
まずは全体が連結な場合を解く.
その連結成分内の行・列すべてを白くするのは明らかに不可能な操作. しかし、その中から一つ行又は列を選んでそれに操作をしないことにすると、それ以外の行・列について操作が行える.
操作しないことにした行・列上にあった赤マスに注目すると(このようなマスは一つ以上存在しないとおかしい)、そのマスの用途は一つに絞られる(選んだ行・列に操作しなくてもよくなったため).
このように考えれば、連鎖的に後ろから操作が決められる.
ここで、全体の白マスの数は操作した行の数を、操作した列の数を
とすると、
と表され、どのような
を選択すればよいか簡単に求まり、各連結成分について行列どちらを選べばいいか定められる.
考察
どんな行・列の集合なら操作可能か考えるとうまくいく.
最初に一つ行・列を操作しないことにするとうまくいくように思えたが、連結成分ごとに考えるのがなかなか見えなかった.
