ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC086 D - Checker

問題
提出コード

解法

散らばっている情報を、まずはK×Kマスの中に押し込みます。
例えば、(x,y)がWという希望は、(x+K,y)、もしくは(x,y+K)がBという希望と同じであり、また(x+K,y+K)がWであるという希望とも同じです。
これを利用すると、白を0、黒を1と表現したときに、色の情報をcとして、(x,y)がcであるという希望は、
座標(x%K,y%K)が色(x/K + y/K + c)%2である、というものにすべて置き換えることができ、こうすることで、座標を0~K-1の中にすべておさめることができます。
まずはこの手法を用いて希望をすべてカウントしていきます。
これが終わったら、累積和を利用して、(0,0)から(i,j)マスまでの希望の合計をO(1)でとりだせるようにします。
あとは、マス目の取り方が2×K^{2}通りあるので、全てについて全探索して、累積和を利用することでそのときの希望を満たす個数を調べ、最大値を求めます。
f:id:emtubasa:20180913005328p:plain
図のように、交点の座標を全探索し、白と黒の4つの部分に分けて、希望を満たしている個数を足していきます。
これを、i,jについてと、白黒の2種類についてすべて全探索します。 あとは、最大値を求めれば完了です。