ABC 086 Checker

問題

D - Checker

解法

まず愚直な解法について考察します.
この問題の1辺が大きさK市松模様について, まずどこかの黒い正方形の左下に座標(0,0)を置きます.
市松模様は無限に続いているので, この黒い正方形について右に1から2K-1, 上に1から2K-1ずらしていけば, すべての場合を取りつくせることになります. このずらしを行ったときに, N個の要望が満たされている数を調べ, 最大値をとると答えが出ます. しかし, 計算量はO(NK^2)となり, 制約から間に合いません.

入力の x_i , y_i , c_i について, あるマス(x_i , y_i)が白だとしたら, (x_i , y_i + K)は必ず黒になります. これを利用すると, 白の希望をすべて黒の希望に変換でき,  c_iを死にパラメータにすることができます.
また, 同じ性質より x_i , y_i について 2Kの周期があるため, それぞれ
 x_i := x_i \space mod \space 2K
 y_i := y_i \space mod \space 2K
としてよいことがわかります. よって, 2K * 2Kのマスのみを考えればよいこともわかります.

マスをずらしていったときに高速で希望と一致しているマスを数える方法を考えます.
そこで, 二次元の累積和を考えます.
二次元の累積和によって(0,0) から (i,j)までの正方形領域に含まれる希望の数を 2K*2K個計算します. これは, まず それぞれの希望について,  sum[x_i][y_i]++としたあと,
 sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]
とすることで計算できます.
あとはこの累積和をこねくりまわすと, 各ずらしについてO(1)で要望の数を求めることができます. (計算式がちょっとめんどうです).

また, 実は2K*2K回ずらして計算する必要はなく, 縦横それぞれK回ずらしてかなわなかった要望の数も最大値として更新するようにすると, K^2回で済みます. 全体の白黒を反転すれば, 対応する市松模様があるからです.

感想

難しい.