naoya_t@topcoder

GCJ 2010 Round 2 : A. Elegant Diamond

13:19 |

教訓

・問題はよく嫁

・処理しやすい座標系を考える

・斜め移動は（自分の場合）バグりやすいのでご用心

サンプルは通るけどA-smallでIncorrect、なコード

• enhanced diamondの中心になりうるすべての点について、symmetricなdiamondが作れるか調べてるだけ。O(k^4)。
• アイデアはコンテスト中に思いついたままだけど、実装するのに時間かかってるしA-small通らないしAからやってても駄目だったなと…泣

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

#define skiplf() do{char buf[256];cin.getline(buf,256);}while(0)

#define X 52
#define W (X*2+1)

char raw[W][W];
bool centerable[W][W];
int k,l,w;

#define VISUALIZE 1

bool test(int cy,int cx){
  rep(i,l){
    int dy=i-w, ay=cy*2-dy; /// (ax+dx)/2=cx, ax=2cx-dx
    if(ay<-X || X<ay) continue;
    rep(j,l){
      int dx=j-w, ax=cx*2-dx;
      if(ax<-X || X<ax) continue;
      if (abs(dx)+abs(dy)>w) continue;
      int d=raw[X+dy][X+dx], a=raw[X+ay][X+ax];
      if(d<0 || a<0) continue;
      if(d!=a) return false;
    }
  }
  return true;
}

int main(){
  int T;cin>>T;
  
  rep(t,T){
    rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }

    cin>>k; l=k*2-1; w=k-1;
    skiplf();

    rep(i,l){
      char buf[256]; cin.getline(buf,256);
      int dy=i-w;
      rep(j,l){
        if(!buf[j]) break;
        if(buf[j]<'0' || '9'<buf[j]) continue;
        int dx=j-w;
        raw[X+dy][X+dx] = buf[j]-'0';
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        int n=raw[X+dy][X+dx];
        if(n>=0)
          printf(" %d", n);
        else
          printf("  ");
      }
      cout<<endl;
    }
#endif

    // x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
    int minarea = 99999999;
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        if (abs(dx)+abs(dy)>w) continue; // |dx|+|dy|<=w
        if (centerable[X+dy][X+dx] = test(dy,dx)) {
          int abx=abs(dx), aby=abs(dy);
          int k_ = k + abx+aby;
          minarea=min(minarea,k_*k_);
        }
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        if (abs(dx)+abs(dy)>w) printf("  ");
        else printf(" %c", centerable[X+dy][X+dx] ? 'o' : 'x');
      }
      cout<<endl;
    }
#endif

    printf("Case #%d: %d\n", 1+t, minarea-k*k);
  }
  return 0;
}

間違い発見

• あ、これでは（上下左右対称ではなく）点対称か…orz (nodchipさんのエントリを見て気がつきました)
• というわけで上下左右対称に書き直したらsmall/largeともに通った。
• 主な書き換えポイントはtest()、あと探索範囲をダイヤモンド内だけでなくダイヤモンドを含む（45度ずれた）正方形に広げた

bool test(int cy,int cx){ /// ★MODIFIED
  rep(i,l){
    int dy=i-w, ay=dy, by=cy*2-dy;
    rep(j,l){
      int dx=j-w, ax=cx*2-dx, bx=dx;
      int d=raw[X+dy][X+dx]; if (d<0) continue;
      int a=(-w<=ax && ax<=w && -w<=ay && ay<=w)? raw[X+ay][X+ax] : -1;
      if (a>=0 && d!=a) return false;
      int b=(-w<=bx && bx<=w && -w<=by && by<=w)? raw[X+by][X+bx] : -1;
      if (b>=0 && d!=b) return false;
    }
  }
  return true;
}

int main(){
  int T;cin>>T;
  
  rep(t,T){
    rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }

    cin>>k; l=k*2-1; w=k-1;
    skiplf();

    rep(i,l){
      char buf[256]; cin.getline(buf,256);
      int dy=i-w;
      rep(j,l){
        if(!buf[j]) break;
        if(buf[j]<'0' || '9'<buf[j]) continue;
        int dx=j-w;
        raw[X+dy][X+dx] = buf[j]-'0';
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        int n=raw[X+dy][X+dx];
        if(n>=0)
          printf(" %d", n);
        else
          printf("  ");
      }
      cout<<endl;
    }
#endif

    // x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
    int minarea = 99999999;
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        // if (abs(dx)+abs(dy)>w) continue; /// ★REMOVED
        if (centerable[X+dy][X+dx] = test(dy,dx)) {
          int abx=abs(dx), aby=abs(dy);
          int k_ = k + abx+aby;
          minarea=min(minarea,k_*k_);
        }
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        printf(" %c", centerable[X+dy][X+dx] ? 'o' : '.'); /// ★CHANGED
      }
      cout<<endl;
    }
#endif
    printf("Case #%d: %d\n", 1+t, minarea-k*k);
  }
  return 0;
}

補足

if (centerable[X+dy][X+dx] = test(dy,dx)) {

とか書いてるけど if ( (c.. = t..) == true ) の意味ですからね。仕事コードではこういう書き方は厳禁ですよ！