問題
https://atcoder.jp/contests/abc086/tasks/arc089_b
提出
https://atcoder.jp/contests/abc086/submissions/3878597
周期性
- 周期性から[0,2K), [0, 2K)の領域にW, Bが収まる
- WはBに変換できる
点の数を数える問題
- グリッドの塗り方は左下の点を[0,2K), [0, 2K)で動かすことで全パターンとなる
- 左下の点の位置毎に、黒領域に入った点を数えられればOK
- 速度的に2次元累積和を用いる
- 2次元imosというのもあるそう
数え方。4K x 4K
- 左下の点を右上に動かししていくとき、左下の点より下、左下の点より左の点もカウントしたい
- 2K x 2Kのカウント行列を4K x 4Kにコピーする
- メモリ使用量が定数倍増える欠点があるが、計算量のオーダーは変わらない
- (追記2020/10/19)コピーしてカウントするのね。バグりにくそうで良いね🤔
2次元累積和の求め方
- 横方向に累積を求めた後、縦方向に累積を求める
大きい領域はグローバル変数で確保せよ
// カウント ll C[4000][4000] = {};
- カウント用配列はmain関数内で動的に確保するとエラーになった
- グローバル変数で必要最大値で確保したら大丈夫