周期性と2次元累積和 arc089_b

問題

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関数内で動的に確保するとエラーになった
• グローバル変数で必要最大値で確保したら大丈夫

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～