Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM464 DIV1 MEDIUM - ColorfulDecoration (この記事を編集する[管理者用])

Source

TopCoder SRM464 DIV1 MEDIUM (550pt)
Problem Statement
SRM 464 自分の参加記録

問題概要

同じサイズの正方形を重ならないように配置する.
向きはx軸y軸に並行.
各正方形は正方形ごとに与えられる2つの座標のうち,どちらかを中心にしなければいけない.
正方形のサイズの最大値を求める問題.
正方形の数は50以下.

解法

答えに対する二分探索をする.
あるサイズの正方形が配置可能かどうかは2-SATに帰着される.
ので,何も考えずに強連結成分分解したんだけど,よく考えると,無向グラフなのでワーシャルフロイドとかするだけでも良かった.

C++によるスパゲッティなソースコード

このコードは実際に本番にサブミットしたコードです.

// #includeとusing namespace std;は略

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

#define INF 2000100100
#define ll long long

ll ab(ll x){if(x<0) return -x; return x;}

typedef struct struct_kdyenbxjdhd{
  int node, nodeMemory;
  int *edgeSize, *edgeMemory;
  int **edge;
}ListGraph;

ListGraph NewListGraph(int maxNode,int maxDegree){
  int i; ListGraph res;
  res.node=0; res.nodeMemory=maxNode;
  res.edgeSize   = (int*)malloc(maxNode*sizeof(int));
  res.edgeMemory = (int*)malloc(maxNode*sizeof(int));
  res.edge = (int**)malloc(maxNode*sizeof(int*));
  rep(i,maxNode) res.edgeMemory[i]=maxDegree;
  if(maxDegree) rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
  return res;
}

void DeleteListGraph(ListGraph g){
  int i;
  rep(i,g.nodeMemory) if(g.edgeMemory[i]) free(g.edge[i]);
  free(g.edgeSize); free(g.edgeMemory); free(g.edge);
}

void ListGraphSetEmpty(ListGraph *g,int node){
  int i;
  g->node = node;
  rep(i,node) g->edgeSize[i]=0;
}

void ListGraphAddEdge(ListGraph *g,int node1,int node2){
  int s=g->edgeSize[node1]++;
  g->edge[node1][s]=node2;
}

int ListGraphStronglyConnectedComponentsDFS(ListGraph *g,int num[],int st,int mx){
  int i,j,n=g->node;
  num[st]=-2;
  rep(i,g->edgeSize[st]) {
    j=g->edge[st][i]; if(num[j]==-1) mx=ListGraphStronglyConnectedComponentsDFS(g,num,j,mx);
  }
  num[st]=mx; return mx+1;
}

int ListGraphStronglyConnectedComponents(ListGraph *g,ListGraph *rev,int res[],void *WorkMemory){
  int i,j,k,n=g->node,ret=0;
  int *st, st_size, *num, *nrv;

  st  = (int*) WorkMemory; WorkMemory = (void*)(st  + n);
  num = (int*) WorkMemory; WorkMemory = (void*)(num + n);
  nrv = (int*) WorkMemory;

  rep(i,n) res[i]=num[i]=-1; k=0;
  rep(i,n) if(num[i]==-1) k=ListGraphStronglyConnectedComponentsDFS(g,num,i,k);
  rep(i,n) nrv[num[i]]=i;

  for(k=n-1;k>=0;k--) {
    i=nrv[k]; if(res[i]>=0)continue;
    res[i]=ret; st_size=0; st[st_size++]=i;
    while(st_size){
      i=st[--st_size];
      rep(j,rev->edgeSize[i])
        if(res[rev->edge[i][j]]==-1) res[rev->edge[i][j]]=ret, st[st_size++]=rev->edge[i][j];
    }
    ret++;
  }

  return ret;
}

class ColorfulDecoration {
public:
int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb) {
  int i,j,k,n;
  ll a,b,c;
  void *mem=malloc(1000000);
  int res[220];
  ListGraph g = NewListGraph(220,220);
  ListGraph G = NewListGraph(220,220);
  int dist[220][220], dx, dy;

  a=0; b=INF; n=xa.size();

  rep(i,2*n) rep(j,2*n){
    if(i<n) dx =xa[i], dy =ya[i]; else dx =xb[i-n], dy =yb[i-n];
    if(j<n) dx-=xa[j], dy-=ya[j]; else dx-=xb[j-n], dy-=yb[j-n];
    dx=ab(dx); dy=ab(dy); if(dx<dy) dx=dy;
    dist[i][j]=dx;
  }
  
  while(b>a){
    c=(a+b+1)/2;
    
    ListGraphSetEmpty(&g,2*n); ListGraphSetEmpty(&G,2*n);
    rep(i,2*n) rep(j,2*n) if(dist[i][j]<c){
      if(i%n==j%n) continue;
      k=(j+n)%(2*n);
      ListGraphAddEdge(&g,i,k);
      ListGraphAddEdge(&G,k,i);
    }

    ListGraphStronglyConnectedComponents(&g,&G,res,mem);
    rep(i,n) if(res[i]==res[i+n]) break;
    if(i==n) a=c; else b=c-1;
  }

  DeleteListGraph(g);
  DeleteListGraph(G);
  free(mem);
  return (int)a;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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