Codeforces Round #524 C. Masha and two friends
問題
https://codeforces.com/contest/1080/problem/C
市松模様の 行 列の表が与えられる。 で囲まれる長方形を中をまずすべて白で塗りつぶす。その後 で囲まれる長方形の中を黒で塗りつぶす。白マスと黒マスの数を求めよ。
制約
考え方
の表に含まれる黒と白のマスの数はすぐにわかる。奇数行目は白のマスが つ存在し、偶数行目は つ存在することがわかる。よって 行あるとき つ白マスがあることがわかる。黒マスは から白マスの数を除くことで求められる。
次に点 で囲まれる長方形に含まれる白マスの数と黒マスの数を求めたい。これを求めることができれば、題意で与えられている操作は
(1)黒マスから白マスになる数
(2)白マスから黒マスになる数
(3)重なる範囲についてもともと黒マスだったマスを黒くする数
の つの操作をすることで解を得ることができる。
点 で囲まれる長方形に含まれる黒マスと白マスはどのように求められるか。黒マスは白マスの結果から簡単に求められるので、白マスの数を求めることにする。これは 変数の包除みたいなイメージで
の長方形に含まれる白マスの数 - の長方形に含まれる白マスの数 - の長方形に含まれる白マスの数 + の長方形に含まれる白マスの数
として求めることができる!
これで (1), (2) を求めることができた。(3) について、 つの長方形が重なる長方形の範囲は として求めることができる。よってこの重なる長方形の範囲に含まれる黒マスの数を数えれば良い。
Submission #46187834 - Codeforces
どこに着目して考察するべきだったか
点 で囲まれる長方形に含まれる黒マスと白マスがどのように求められるか? 変数だとよくある の 以上 以下の個数は...?は で求めることができるので、これと同じ要領で考えればよかった。
何がバグっていたか
得た知見
変数の以上、以下に含まれる個数の求め方