第二回全国統一プログラミング王決定戦本戦C Largest N(600)

atcoder.jp

問題

のマス目が与えられます。各マスは黒か白で塗られています。このマス目に含まれる'N'の大きさの最大値を求めてください。ここで'N'とは、正方形状のマス目であって、両端の列のマス目と、左上から右下にかけての対角線上のマス目が黒で塗られているもののこととします。

制約

考察

まずは全探索を考えます。グリッドに含まれるすべての正方形について、条件を満たしているか判定すればよいです。各マスについて、下と右斜め下にいくつの黒マスが連続しているかを前計算しておけば、で判定できます。しかし、正方形は個くらいあるのでこのままでは間に合いません。

次に高速化について考えます。正方形の右下を固定したときに、左上が満たすべき条件について考えます。 右下の座標をとします。まず、左側のたて棒として使うものは、図の赤い線を超えていなければならないということが分かります。また、左側のたて棒は、図の緑の範囲に収まっていなければなりません。この2つの条件を満たしていれば、そのたて棒を使って'N'を作ることができます。

を右下とする最大の'N'は、この2つの条件を満たすたて棒のうち、最もインデックスが小さいものを使ったものです。 このような縦棒は、赤い線を超えている縦棒のインデックスの集合をsetで持っておけば、二分探索で対数時間で求めることができます。この集合は、priority_queueに縦棒がどこまで伸びているかとインデックスのペアを持たせておくことで管理できます。

#include<bits/stdc++.h>
using namespace std;
 
int cntD[3010][3010];
int cntU[3010][3010];
 
int main()
{
   int H,W,K; cin>>H>>W>>K;
   vector<vector<int>> a(H,vector<int>(W,1));
   for(int i=0;i<K;i++){
      int r,c; cin>>r>>c;
      r--; c--;
      a[r][c]=0;
   }
 
   for(int j=0;j<W;j++){
      // 上にいくつ続いているか
      for(int i=0;i<H;i++){
         if(a[i][j]==0) cntU[i][j]=0;
         else cntU[i][j]=(i-1>=0? cntU[i-1][j]:0)+1;
      }
      // 下にいくつ続いているか
      for(int i=H-1;i>=0;i--){
         if(a[i][j]==0) cntD[i][j]=0;
         else cntD[i][j]=(i+1<H? cntD[i+1][j]:0)+1;
      }
   }
 
   auto solve=[&](int i,int j)
   {
      using P=pair<int,int>;
      using PriorityQueue=priority_queue<P,vector<P>,greater<P>>;
      set<int> S;
      PriorityQueue Q;
 
      int res=0;
      for(;i<H and j<W;i++,j++){
         if(a[i][j]==0){
            // 白マスがあればもう使えないので空にする
            S.clear();
            PriorityQueue().swap(Q);
            continue;
         }
 
         Q.push({i+cntD[i][j]-1,j});
         S.insert(j);
         // 'N'が作れるもののうち、インデックスが最小のものを取ってくる
         auto itr=S.lower_bound(j-cntU[i][j]+1);
         assert(itr!=S.end());
         res=max(res,j-*itr+1);
         // もう使えないものを消去
         while(!Q.empty() and Q.top().first<=i){
            S.erase(Q.top().second);
            Q.pop();
         }
      }
      return res;
   };
 
   int ans=0;
   // 正方形の対角線を全探索
   for(int j=0;j<W;j++) ans=max(ans,solve(0,j));
   for(int i=0;i<H;i++) ans=max(ans,solve(i,0));
   cout<<ans<<endl;
   return 0;
}

実は、最初の愚直な全探索に「すでに見つけた解以下のものは探索しない」という枝狩りをいれるとかなり速くなるみたいで、通ります(上のものより速いです)。なんでここまで速くなるかはよく分かってないです。

#include<bits/stdc++.h>
using namespace std;
 
int cntD[3010][3010];
int cntRD[3010][3010];
 
int main()
{
   int H,W,K; cin>>H>>W>>K;
   vector<vector<int>> a(H,vector<int>(W,1));
   for(int i=0;i<K;i++){
      int r,c; cin>>r>>c;
      r--; c--;
      a[r][c]=0;
   }
 
   for(int i=H-1;i>=0;i--){
      for(int j=0;j<W;j++){
         cntD[i][j]=(a[i][j]==0? 0:cntD[i+1][j]+1);
         cntRD[i][j]=(a[i][j]==0? 0:cntRD[i+1][j+1]+1);
      }
   }
 
   int ans=0;
   for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(a[i][j]){
      for(int k=ans+1;k<=min(cntD[i][j],cntRD[i][j]);k++){
         if(cntD[i][j+k-1]>=k) ans=max(ans,k);
      }
   }
   cout<<ans<<endl;
   return 0;
}

まとめ

• 簡略化した図を描く
• 正方形は斜めに見ていく(対角線が同じ直線状にあるものを一緒に考える)

感想

最後の方がかなり適当になってしまいました。本番は、斜めに見ると良さそうだなぁとは思っていましたが、詰めきれませんでした。図を描くのは大事です。正方形を斜めに見るというのは、最大正方形を尺取り法で解くというので見たことがあります。