AtCoder Grand Contest 021 C 「Tiling」

問題文

C - Tiling

 

パズルゲー。判定だけでなく具体例を作らないといけないのでめんどうだった。

 

明らかにA+B≦floor((N・M)/2)かつA≦N・floor(M/2)かつB≦M・floor(N/2)を満たしていなければならないのでチェックしておく。

まずグリッドを2×2の正方形に分割する。例えば5×5のグリッドの場合、以下のように分割する。

 

f:id:Div9851P:20181229003605j:plain

Mが奇数の場合は右端にあまりが出来るので、そこは縦長タイルで埋めておく。同様に、Nが奇数のときは下にあまりが出来るので、そこは横長タイルで埋めておく。

そうしたら、2×2の正方形を見ていって、横長タイルがA枚未満なら、その正方形を横長タイル2枚で埋める。もし、横長タイルの枚数がA枚以上になったら、あとの正方形は縦長タイル2枚で埋める。

これが終わると、横長タイルは絶対にA枚以上になっている。このとき縦長タイルもB枚以上になっていればこれで無事完了。

そうでない場合、横長タイルが無駄に1個あって、縦長タイルが1個足りないという状況になっている。このとき、もしN,Mが3以上の奇数であれば、右下に以下のような置き方をしてからのこりを埋めることで縦長タイルを1枚増やすことが出来る。

f:id:Div9851P:20181229005117j:plain

ちなみにNまたはMが偶数のとき、縦長タイルを1枚増やせないことは以下のように示せる。

(証明)

Nが偶数だとする。

奇数行目を黒、偶数行目を白で塗る。このとき縦長タイルを置くと黒マスを奇数個、横長タイルを置くと黒マスを偶数個覆うことになる。ここから縦長タイルの枚数の偶奇とグリッド全体の黒マスの数の偶奇は一致しなければならないことがわかる。よって縦長タイルの枚数の偶奇をかえることは出来ないので1枚増やすことは出来ない。

Mが偶数のときも同様に示せる。