ABC 086 Checker
問題
解法
まず愚直な解法について考察します.
この問題の1辺が大きさの市松模様について, まずどこかの黒い正方形の左下に座標を置きます.
市松模様は無限に続いているので, この黒い正方形について右に1から2K-1, 上に1から2K-1ずらしていけば, すべての場合を取りつくせることになります. このずらしを行ったときに, 個の要望が満たされている数を調べ, 最大値をとると答えが出ます. しかし, 計算量はとなり, 制約から間に合いません.
入力のについて, あるマスが白だとしたら, は必ず黒になります. これを利用すると, 白の希望をすべて黒の希望に変換でき, を死にパラメータにすることができます.
また, 同じ性質よりについての周期があるため, それぞれ
としてよいことがわかります. よって, のマスのみを考えればよいこともわかります.
マスをずらしていったときに高速で希望と一致しているマスを数える方法を考えます.
そこで, 二次元の累積和を考えます.
二次元の累積和によってまでの正方形領域に含まれる希望の数を個計算します. これは, まず それぞれの希望について, としたあと,
とすることで計算できます.
あとはこの累積和をこねくりまわすと, 各ずらしについてで要望の数を求めることができます. (計算式がちょっとめんどうです).
また, 実は回ずらして計算する必要はなく, 縦横それぞれ回ずらしてかなわなかった要望の数も最大値として更新するようにすると, 回で済みます. 全体の白黒を反転すれば, 対応する市松模様があるからです.
感想
難しい.