【本記事の想定する読者】
本問題が解けなくてつらくなっている過去の私
【問題概要】
座標(xi,yi)をBまたはWに塗りたいという要望がN個与えられる。無限に広がる2次元グリッドを1辺の長さがKである市松模様で塗る時、最大でいくつの要望を叶えられるか。
【制約】
1 ≦ N ≦ 100,000
1 ≦ K ≦ 1,000
0 ≦ xi, yi ≦ 1,000,000,000
i ≠ j ならば (xi, yi) ≠ (xj, yj)
【最終的な方針】
2次元版のいもす法を用いる。いもす法についてはこちら
いもす法 - いもす研 (imos laboratory)
つまり、各希望(xi, yi, B(W))についてそれを叶えてくれるような市松模様を2次元の配列に記録していき、最後に配列全体を見て最大値を答えとする。
【最終的な方針へ辿り着くまでの道筋】
市松模様の塗り方はそこまで多くなさそうなので、これを全部見るのはどうか。つまりある塗り方を1つ固定したら、その塗り方で叶えられるような希望が何個あるかわかるので、その中の最大値を答えとすればよい。
市松模様の種類については、黒く塗られた部分の左下のグリッド(x, y)が必ず[0,2K)×[0,2K)にあり、さらにこの範囲からどの2つをとって、それを黒い部分の左下にするような市松模様にしても違う塗り方なので、{市松模様の塗り方}と{(x, y)|(x,y)∈[0,2K)×[0,2K)}に全単射が作れる。つまり、市松模様の塗り方は2K×2K通りある。
各塗り方に対してN個すべての座標について、その塗り方で希望を叶えられるか判定する必要があるので、この方針の計算量はO(N×K2)となり、時間内に収まりそうにない。長々と書いてきたのに残念だが、この方針は却下する。
それでは次は、固定するものを市松模様ではなく希望にしてはどうだろうか。（こういった固定するものを変えるというのは競プロに限らず典型テクニックなような気がしますが、どうなんでしょうか）つまり、各希望(xi, yi, B(W))について、(xi, yi)をB(W)に塗ることができるような市松模様の塗り方はどこだろうかと考える。先の議論を思いだすと、市松模様は[0,2K)×[0,2K)の範囲の座標を黒い部分の左下の座標として考えてよいので、例えば市松模様(i,j)（黒い部分の左下が(i,j)になるような塗り方）によって(x, y)をB(W)に塗ることができるなら2次元配列imos[i][j]の値を1増やすという操作をする 。・・・（※）
これをすべての希望について操作するとimos[i][j]には市松模様(i,j)で叶えることのできる希望の数が格納されていることになる。あとはこの配列の値をすべて見て、一番大きい値が答えといった算段である。
この方針でもそのまま素直にやると計算量は先ほどと同じになってうまくないが、実は（※）の操作について、例えば座標(x, y)を黒で塗れるような市松模様（を黒い部分の左下の座標で表したもの）の集合は座標上に図示すると正方形となる。正確には無限に続く市松模様なのだが、必要な部分だけ取り出すと高々数個の正方形になる。この正方形の各マスに全て+1する作業はいもす法を使うことによって高速化できる。下の画像は、K=3の時に、(4,2)が黒で塗られるような市松模様の集合を黒で塗りつぶしたものである。ピンクも含まれる。注意したいのが、この集合自体も市松模様となっているがそれはあまり関係なく、黒で塗られたグリット一つ一つが、そのグリッドを黒の部分の左下とした市松模様を表しているということである。
この正方形（場合によっては長方形）の部分をすべて+1する部分はいもす法を適用するだけなので、上述のリンクを参照してほしい。ここの実装方法はいろいろあろうが、一応私のやり方を記しておく。とはいえあまり上手い方法に思えないので参考にしないでほしい。また本家の解説にもある通り、(x,y)を白にしてほしいという希望と(x+k,y)を黒にしてほしいという希望は同値であり、(x,y)を黒にしてほしいという希望と(x+2K,y)を黒にしてほしいという希望は同値である（yについても同様）のであらかじめ入力を(x,y)∈[0,2K)×[0,2K)を黒にしてほしいという風に変形しておく。これを踏まえて(x,y)∈[0,2K)×[0,2K)を黒に塗ることができるような市松模様の黒い部分の左下の座標（これも[0,2K)×[0,2K)）をカウントすること考えると、高々7個の正方形について見ればよいことがわかる。このときにimosの配列外を参照してしまわないように注意する必要がある。
ここまで来れば、あとはimos配列を横と縦に累積和を取った後に、すべての範囲を参照して一番大きい値を答えとして出力すればよい。
【提出コード】
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for(int i=(l); i<(r); ++i) typedef long long ll; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } // (x,y)∈[x-k+1, x]*[y-k+1, y]の範囲でimos[i][j]+=1と累積されるように値をセットする void set_square(int x, int y, int k, vector<vector<int>> &imos){ if(x<0 || y<0 || x>=3*k-1 || y>=3*k-1) return; imos[ max(0, x-k+1) ][ max(0, y-k+1) ] += 1; imos[ max(0, x-k+1) ][ min(y+1, 2*k) ] -= 1; imos[ min(x+1, 2*k) ][ max(0, y-k+1) ] -= 1; imos[ min(x+1, 2*k) ][ min(y+1, 2*k) ] += 1; } void set_imos(int x, int y, int k, vector<vector<int>> &imos){ set_square(x, y, k, imos); set_square(x+2*k, y, k, imos); set_square(x+k, y-k, k, imos); set_square(x-k, y-k, k, imos); set_square(x+k, y+k, k, imos); set_square(x-k, y+k, k, imos); set_square(x, y+2*k, k, imos); } int main(){ int n, k; cin >> n >> k; // 入力を受け取り、扱いやすいように希望を同値変形して座標を圧縮する // 具体的には全ての希望を、「(x,y)∈[0,2k)*[0,2k)を黒に塗りたいな」という希望に同値変形する vector<int> x(n), y(n); rep(i, 0, n){ cin >> x[i] >> y[i]; char c; cin >> c; if(c=='W') x[i] += k; x[i]%=2*k; y[i]%=2*k; } // 市松模様は[0,2k)*[0,2k)のどこを黒い部分の左下にするかという情報で一意に定まる（全単射）ので、そのように表す // imos[i][j] := (i,j)が黒い部分の左下になるような市松模様を塗った時に叶えられる希望の数 vector<vector<int>> imos(2*k+5, vector<int>(2*k+5, 0)); rep(i, 0, n){ // (x[i],y[i])を黒に塗れるような市松模様(X, Y)について、最後に累積した時に imos[X][Y]+=1 になるように重みを加算する set_imos(x[i], y[i], k, imos); } // 左→右へ累積 rep(i, 0, 2*k) rep(j, 1, 2*k) imos[i][j] += imos[i][j-1]; // （問題文の画像で）下→上へ累積 rep(j, 0, 2*k) rep(i, 1, 2*k) imos[i][j] += imos[i-1][j]; // 最大値の検索 int ans=0; rep(i, 0, 2*k) rep(j, 0, 2*k) chmax(ans, imos[i][j]); cout << ans << '\n'; return 0; }
