ABC278 E - Grid Filling ～Aの値域を気にせず(?)mapで解く解法～

• 問題 https://atcoder.jp/contests/abc278/tasks/abc278_e
• 提出 https://atcoder.jp/contests/abc278/submissions/36654013 (AC 600ms)
• 方法
  • 種類数はmap.sizeで求める
  • 除去範囲を1ずつスライドさせてmapを更新する。この更新は差分のみ行い高速化する
• 計算量
  • 一番重いところは3重ループの箇所で、O(HWN log(N))
  • この解法、Aの値域がN以下のおかげで間に合っていますね。値域に制限がなければmapのサイズがHWになりうるので、300倍遅くなってTLEします

code

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll H,W,N,h,w;
    cin>>H>>W>>N>>h>>w;

    map<ll,ll> mp_all;
    VV A(H, VI(W));
    rep(i,H){
      rep(j,W){
        ll a;cin>>a;
        A[i][j]=a;
        mp_all[a]++;
      }
    }

    // kの行について解く
    rep(k,H-h+1){
      auto mp = mp_all;
      // 塗りつぶしの分を引く
      rep(i,h){
        rep(j,w){
          ll y = k+i;
          ll x = j;
          ll a = A[y][x];
          mp[a]--;
          if(mp[a]==0)mp.erase(a);
        }
      }
      VI Ans;
      Ans.push_back(mp.size());

      // 右にずらす
      FOR(dx,1,W-w+1){
        rep(i,h){
          // 黒塗りから外れる分
          ll a = A[k+i][dx-1];
          mp[a]++;

          // 黒塗りになる分
          a = A[k+i][dx+w-1];
          mp[a]--;
          if(mp[a]==0)mp.erase(a);
        }
        Ans.push_back(mp.size());
      }
      print_vector(Ans);
    }

    return 0;
}