UVa 10593: Kites

TopCoder Problem

見事なスパゲッティが茹で上がったので、さらしてみたくなりました。

Description

  • . と x からなる n * n 文字のグリッドが与えられます。
  • この中に x のみからなる正方形はいくつある？
    • 正方形は軸平行か45度回転。つまりこんな感じ。



xxx  ..x..

xxx  .xxx.

xxx  xxxxx

     .xxx.

     ..x..

  • n <= 500

Algorithm

  • Ad-hoc.
  • 軸平行なものを数えるには、
    • 各マスについて、右側に x がいくつ連続しているか をあらかじめ求めておく。(O(n2))
    • あるマスを左上とする正方形の数は、この値の min を取りながら下方向に見ていけばよい。
      • 比較的簡単。
  • 45度を数えるには、
    • 各マスについて、{右,左,上,下}側に x がいくつ連続しているか をあらかじめ求めておく。
    • あるマスを中心とする正方形の数は、上下の min を取りながら左右に、また左右の min を取りながら上下に見ていけばよい。
      • 超ややこしい。
  • 全体として O(n3)。
    • n <= 500 なので危ない気もしたけど、定数項が軽いせいか 1.044/4.000 [sec] で通った。

Code

#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>

#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)

using namespace std;

template<class T>void ls(T& a,T b){ if(b<a) a=b; }

const int N=512;

char v[N][N];
int l[N][N];
int r[N][N];
int u[N][N];
int d[N][N];

int square(int n){
  int ans=0;
  int k,t;
  REP(i,n) REP(j,n){
    for(k=1,t=r[i][j];t>=k;t=min(t,r[i+k][j]),k++){}
    if(k>=2) ans+=k-2;
  }
  return ans;
}

int diamond(int n){ 
  int ans=0;
  REP(i,n) REP(j,n){
    int t=min(min(l[i][j],r[i][j]),min(u[i][j],d[i][j])),k;
    for(k=1;0<=i-k && i+k<n && 0<=j-k && j+k<n && t>1;k++)
      t=min(t,k-1+min(min(min(l[i-k][j],r[i-k][j]),min(l[i+k][j],r[i+k][j])),
		      min(min(u[i][j-k],d[i][j-k]),min(u[i][j+k],d[i][j+k]))));
    if(k>=2) ans+=min(t,k-1);
  }
  return ans;
}

int brute_force(int n){
  if(n==500) return 0;
  int a=0,b=0;
  REP(i,n) REP(j,n) FOR(k,2,n+1){
    int cnt=0;
    FOR(ii,i,i+k) FOR(jj,j,j+k) if(v[ii][jj]=='x') cnt++;
    if(cnt==k*k) a++;
    
  }
  REP(i,n) REP(j,n) FOR(k,1,n+1){
    FOR(ii,i-k,i+k+1) FOR(jj,j-k,j+k+1){
      if(!(0<=ii && ii<n && 0<=jj && jj<n)) goto bad;
      if(abs(ii-i)+abs(jj-j)<=k && v[ii][jj]!='x') goto bad;
    }
    b++;
  bad:;
  }
  return a+b;
}

int main(){
  int n;
  while(scanf("%d",&n)!=EOF){
    memset(v,'.',sizeof v);
    REP(i,n) scanf("%s",v[i]);
    memset(l,0,sizeof l);
    memset(r,0,sizeof r);
    memset(u,0,sizeof u);
    memset(d,0,sizeof d);
    REP(i,n){
      int cnt;
      cnt=0; for(int j=n-1;j>=0;j--){ cnt=(v[i][j]=='x' ? cnt+1 : 0); r[i][j]=cnt; }
      cnt=0; for(int j=n-1;j>=0;j--){ cnt=(v[j][i]=='x' ? cnt+1 : 0); d[j][i]=cnt; }
      cnt=0; REP(j,n)               { cnt=(v[i][j]=='x' ? cnt+1 : 0); l[i][j]=cnt; }
      cnt=0; REP(j,n)               { cnt=(v[j][i]=='x' ? cnt+1 : 0); u[j][i]=cnt; }
    }

    cout << square(n) + diamond(n) << endl;
  }
}
  • デバッグ用の brute-force もおまけに付いております。
  • diamond (45度の方) があまりにも謎過ぎる。minばっかりでひどい。
  • O(n3) より速くできないものだろうか。
    • ちょっとだけ考えてみたけど、よく分からなかったです。