Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Round 2 HARD - BreakingChocolate (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 2 HARD (1000pt)
Problem Statement
Open 2010 Algorithm Round 2 自分の参加記録

問題概要

W*Hの板チョコがある.
40個以下の座標が与えられる.その座標の部分のチョコは特別.
チョコを割って,全ての破片が,特別なもののみか,特別じゃないもののみか,となるようにするための最小の割る回数を求める問題.
WとHは10億以下.

解法

座標圧縮してDP.
 dp[x1][x2][y1][y2] = (x1,y1) - (x2,y2)を対角線とするチョコレート板の部分を分割するための割る回数の最小回数
をメモする.状態数は40^4 / 4程度.
x1に特別な破片がなければ,特別な破片のある最小のx座標まで割ってしまって良い,などというのはadhocに割る.
後は,x座標でソートして,2つのピースの間を割るなどという感じの処理でDPを組み立てる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x, y;
int X[40], Y[40];
int sx[40], sy[40], n;
map<int,int> map_x, map_y;

int dp[40][40][40][40];

int solve(int x1,int x2,int y1,int y2){
  int i,k,in=0,res=100000,tmp;
  int xx[40], yy[40], xxx, yyy;

  if(dp[x1][x2][y1][y2]>=0) return dp[x1][x2][y1][y2];

  REP(i,x1,x2+1) xx[i]=0;
  REP(i,y1,y2+1) yy[i]=0;
  rep(i,n) if(x1<=sx[i] && sx[i]<=x2 && y1<=sy[i] && sy[i]<=y2){
    xx[sx[i]]=1; yy[sy[i]]=1;
    in++;
  }

  if(in == 0) return dp[x1][x2][y1][y2] = 0;
  if(in == (X[x2]-X[x1]+1) * (Y[y2]-Y[y1]+1)) return dp[x1][x2][y1][y2] = 0;

  k=x1; while(xx[k]==0) k++; if(k!=x1) return dp[x1][x2][y1][y2] = solve(k,x2,y1,y2)+1;
  k=x2; while(xx[k]==0) k--; if(k!=x2) return dp[x1][x2][y1][y2] = solve(x1,k,y1,y2)+1;
  k=y1; while(yy[k]==0) k++; if(k!=y1) return dp[x1][x2][y1][y2] = solve(x1,x2,k,y2)+1;
  k=y2; while(yy[k]==0) k--; if(k!=y2) return dp[x1][x2][y1][y2] = solve(x1,x2,y1,k)+1;

  xxx = yyy = 0;
  REP(i,x1,x2+1) if(xx[i]) xx[xxx++]=i;
  REP(i,y1,y2+1) if(yy[i]) yy[yyy++]=i;

  REP(i,1,xxx){
    tmp = solve(x1,xx[i-1],y1,y2) + solve(xx[i],x2,y1,y2) + 1;
    if(X[xx[i]]-X[xx[i-1]]>1) tmp++;
    if(tmp < res) res = tmp;
  }
  REP(i,1,yyy){
    tmp = solve(x1,x2,y1,yy[i-1]) + solve(x1,x2,yy[i],y2) + 1;
    if(Y[yy[i]]-Y[yy[i-1]]>1) tmp++;
    if(tmp < res) res = tmp;
  }

  return dp[x1][x2][y1][y2] = res;
}

class BreakingChocolate {
public:
int minSteps(int W, int H, vector <int> sx_, vector <int> sy_) {
  int i,j,k,l;
  int res;

  n = sx_.size();
  map_x.clear(); map_y.clear();

  x=0; y=0;
  rep(i,n){
    X[x++] = sx_[i];
    Y[y++] = sy_[i];
  }

  sort(X,X+x); sort(Y,Y+y);

  k=0; rep(i,x) if(!i || X[i]!=X[i-1]) X[k++] = X[i]; x = k;
  k=0; rep(i,y) if(!i || Y[i]!=Y[i-1]) Y[k++] = Y[i]; y = k;

  rep(i,x) rep(j,x) rep(k,y) rep(l,y) dp[i][j][k][l]=-1;

  rep(i,x) map_x[X[i]] = i;
  rep(i,y) map_y[Y[i]] = i;
  rep(i,n) sx[i] = map_x[sx_[i]], sy[i] = map_y[sy_[i]];

  res = solve(0,x-1,0,y-1);
  rep(i,n) if(sx_[i]==1) break; if(i==n) res++;
  rep(i,n) if(sx_[i]==W) break; if(i==n) res++;
  rep(i,n) if(sy_[i]==1) break; if(i==n) res++;
  rep(i,n) if(sy_[i]==H) break; if(i==n) res++;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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