Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-23

SRM455 Easy(300): DonutsOnTheGridEasy

| 22:00 | SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder のブックマークコメント

  • 問題激しく読み違えてた...ドーナツが幾つ取れるか数えようとしてた。重箱状の階層の深さの最大を求めるだけだった。
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

// memoize..
char z[50][50][51][51], mp[50][50][51][51];

class DonutsOnTheGridEasy {
  vector<string> gr;
  int R,C;
  
  int isZeroShape(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (z[r][c][h][w]>=0) return z[r][c][h][w]; // memo

    int re=1;
    
    rep(j,h) { int y=r+j;
      if (gr[y][c]=='.') {re=0; goto end;}
      if (gr[y][c+(w-1)]=='.') {re=0; goto end;}
    }
    rep(i,w) { int x=c+i;
      if (gr[r][x]=='.') {re=0; goto end;}
      if (gr[r+(h-1)][x]=='.') {re=0; goto end;}
    }
 end:
    return z[r][c][h][w] = re;
  }

  int sub(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (mp[r][c][h][w]>=0) return mp[r][c][h][w]; // memo

    int ct=0; if (isZeroShape(r,c,h,w)) ct=1+sub(r+1,c+1,h-2,w-2);
    FOR(hj,1,h-1) ct = max(ct, max(sub(r,c,hj,w),sub(r+hj,c,h-hj,w)));
    FOR(wj,1,w-1) ct = max(ct, max(sub(r,c,h,wj),sub(r,c+wj,h,w-wj)));

    mp[r][c][h][w] = ct;
    return ct;
  }
 public:
  int calc(vector<string> grid) {
    R=sz(grid), C=sz(grid[0]);
    gr = grid;

    // clean up
    memset(z,255,sizeof(z)); memset(mp,255,sizeof(mp));

    return sub(0,0,R,C);
  }
};

rng_58rng_582009/12/24 19:36C = 2 のとき、奇数なら1を足す関数
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします

n4_tn4_t2009/12/25 11:49問題作成者様直々にコメントありがとうございます!!
なるほどそういうのもアリですね。頭固かったです。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091223