Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1271-0cb8ce60
この記事にトラックバックする(FC2ブログユーザー)

2010 Round 1C C問題 - Making Chess Boards (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1C C問題
Problem Statement
SPOJ 6706 [CT101CC] (2010/05/28 23:45追加)

問題概要

各セルが黒か白かのM*Nのグリッドが与えられる.
チェス盤を切り取っていく.チェス盤は白と黒とが交互になっている市松模様の正方形の盤面.
切り取っていく順番は,できるだけ大きいのから,複数あるなら,左上のから切り取る.
最終的に,どのサイズのチェス盤が,どのぐらい切り取られたかを求める問題.
small: M, Nは32以下
large: M, Nは512以下

解法

全てのマスに対して,そのマスを左上角になるようなチェス盤のうち,最大サイズをDPで求める.これはO(MN)で可能.
後は,実際に大きいものから切り出していって,切り出されたことによって,DPの値を修正していく.
このときに,サイズごとになぞっていくとO(MN*MIN(M,N))ぐらいになる.
ヒープを使うと,O(MN log(MN))ぐらいで解ける.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

void intHeapGoUp(int n,int hp[],int hpi[],int d[]){
  int k,m;
  if(!n) return;
  m=(n-1)/2;
  if(d[hp[m]]<=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoUp(m,hp,hpi,d);
}

void intHeapGoDown(int n,int hp[],int hpi[],int hp_size,int d[]){
  int k,m;
  m=2*n+1; if(m>=hp_size) return;
  if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
  if(d[hp[m]]>=d[hp[n]]) return;
  k=hp[m]; hp[m]=hp[n]; hp[n]=k;
  hpi[hp[m]]=m; hpi[hp[n]]=n;
  intHeapGoDown(m,hp,hpi,hp_size,d);
}

void intHeapInsert(int n,int hp[],int hpi[],int *hp_size,int d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  intHeapGoUp((*hp_size)-1,hp,hpi,d);
}

int intHeapDelete(int hp[],int hpi[],int *hp_size,int d[]){
  int r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  intHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}

int char2int(char c){
  if('0'<=c && c<='9') return c-'0';
  return c-'A'+10;
}



int hp[300000], hpi[300000], dp[300000], hp_size;

int main(){
  int i,j,k,l,m,n,sz,ss;
  int x,y,xy,a,b;
  int sx,sy;
  int size,count=0;

  int res[600], mx;
  char in2[160], in[600][600];
  int tmp[160];

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&x,&y); xy=x*y;

    mx = x; if(mx > y) mx = y;
    rep(i,mx+1) res[i]=0;

    rep(i,x) {
      scanf("%s",in2);
      rep(j,y/4) tmp[j]=char2int(in2[j]);
      rep(j,y){
        in[i][j]=0;
        if(tmp[j/4]&(1<<(3-j%4))) in[i][j]=1;
      }
    }

    for(i=x-1;i>=0;i--) for(j=y-1;j>=0;j--){
      dp[i*y+j]=1;
      if(i+1 >= x || j+1 >= y) continue;
      if((in[i][j]^in[i+1][j])==0) continue;
      if((in[i][j]^in[i][j+1])==0) continue;
      if((in[i][j]^in[i+1][j+1])==1) continue;

      k=dp[i*y+(j+1)];  if(k>dp[(i+1)*y+j]) k=dp[(i+1)*y+j];  if(k>dp[(i+1)*y+(j+1)]) k=dp[(i+1)*y+(j+1)];
      dp[i*y+j] = k+1;
    }

    rep(i,xy) dp[i] = - (dp[i]*xy + xy-1-i);
    hp_size = 0; rep(i,xy) hpi[i]=-1;
    rep(i,xy) intHeapInsert(i,hp,hpi,&hp_size,dp);

    for(;;){
      k = hp[0];
      sz = (-dp[k])/xy;
      if(sz==0) break;
      res[sz]++;

      sx = k/y; sy = k%y;
      REP(i,sx-sz,sx+sz) if(0<=i&&i<x) REP(j,sy-sz,sy+sz) if(0<=j&&j<y){
        a = sx-i; b = sy-j;
        if(a<b) a=b;
        if(a<0) a=0;
        ss = (-dp[i*y+j])/xy;
        if(ss > a){
          dp[i*y+j] = -(a*xy+(xy-1-(i*y+j)));
          intHeapGoDown(hpi[i*y+j],hp,hpi,hp_size,dp);
        }
      }
    }

    k=0; rep(i,mx+1) if(res[i]) k++;
    printf("Case #%d: %d\n",++count,k);
    for(i=mx;i;i--) if(res[i]) printf("%d %d\n",i,res[i]);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1271-0cb8ce60
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。