Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM499 DIV1 HARD - ImpossibleGame (この記事を編集する[管理者用])

Source

TopCoder SRM499 DIV1 HARD (1000pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

次のゲームを行うとき,プレイヤーが絶対勝てないようにするためには,ゲームマスターは最小で何色使えば良いかを求める問題.
ゲームマスターは最初に,ABCDのみからなる長さk (30以下) の文字列に対応する色をすべて決める.
プレイヤーは1つの文字列を選び,最初に選んだ文字列と違う文字列で最初と同じ色に出来れば勝ち.できる操作は以下の通り.
 1. 隣接する2文字を入れ替える
 2. 部分文字列としてbefore[k]を含んでいるなら,その部分をafter[k]に置き換える
before[k]とafter[k]の長さは同じで,この文字列は入力で与えられ,ゲームマスターが自由に決めることはできない.
beforeとafterの要素数は50以下.

解法

まず,文字は自由にswapできるので,ABCDの文字が何文字含まれているかのみを考えれば良い.
すると,状態数はO(k^3)程度しかない.
それをノードとして,状態遷移できるノードに枝をはってグラフを作る.
もし,それがDAG (閉路がない) なら,そこから移動できるノードに使われている色の最大値+1の色を各ノードに割り当てれば良い.
全てのノードが子供より大きい色が割り当てられていることから,自分の子孫までみる必要はなく,自分の子どもの色の最大値+1を割り当てれば良いので,DPでO(枝数)ぐらいで計算可能.
閉路があれば,強連結成分分解してDAGに落とせば良い.強連結成分は全部違う色に塗らないとダメになる.

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

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

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;
}

/* edgeMemory[k]=sizeに変更する.中身のデータは破壊される. */
/* fg=1 ならば,すでにedgeMemory[k]>=sizeの場合は何もしない */
void ListGraphOneEdgeReallocEasy(ListGraph *g,int k,int size,int fg){
  if(fg==1 && g->edgeMemory[k]>=size) return;
  if(g->edgeMemory[k]==size) return;
  if(g->edgeMemory[k]) free(g->edge[k]);
  g->edgeMemory[k]=size;
  g->edge[k] = (int*)malloc(size*sizeof(int));
}

/* g.nodeは既に設定済み,edgeのメモリが足りてない場合は適当にメモリ確保するぜ */
void ListGraphSetDirectEdges(ListGraph *g,int from[],int to[],int size){
  int i,n=g->node;
  rep(i,n) g->edgeSize[i]=0;

  rep(i,size) g->edgeSize[from[i]]++;
  rep(i,n) {ListGraphOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
  rep(i,size) ListGraphAddEdge(g,from[i],to[i]);
}





/* stからの距離をresに格納する,辿り着けないなら-1 */
void ListGraphBFS(ListGraph *g,int st,int res[],void *workMemory){
  int i,j,k,n=g->node;
  int *q,q_st,q_size;
  
  q=(int*)workMemory; q_st=0; q_size=1; q[0]=st;

  rep(i,n) res[i]=-1; res[st]=0;
  while(q_size){
    i=q[q_st++]; q_size--;
    rep(j,g->edgeSize[i]){
      k=g->edge[i][j]; if(res[k]>=0)continue;
      q[q_st+q_size++]=k; res[k]=res[i]+1;
    }
  }
}





/* 番号つけるよ.stからDFSするよ.番号mxからつけるよ.最後につけた番号+1をreturnで返すよ. */
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;
}



int node;
int num[33][33][33][33];
int edge1[2000000], edge2[2000000], m;

vector<int> edge[40000];
long long w[40000];
long long dp[40000];

long long solve(int now){
  int i,j,k;
  long long res=0, tmp;

  if(dp[now] >= 0) return dp[now];

  rep(i,edge[now].size()){
    j = edge[now][i];
    tmp = solve(j);
    if(res < tmp) res = tmp;
  }

  return dp[now] = res + w[now];
}


class ImpossibleGame {
public:
long long getMinimum(int k, vector <string> before, vector <string> after) {
  int i,j,state,st,ed,N;
  int a,b,c,d;
  int A[60], B[60], C[60], D[60], n;
  int E[60], F[60], G[60], H[60];
  int bun[40000];
  void *mem=malloc(1000000);
  long long res, tmp, comb[50][50];
  ListGraph g = NewListGraph(40000,0);
  ListGraph rev = NewListGraph(40000,0);

  comb[0][0]=1; REP(j,1,50) comb[0][j]=0;
  REP(i,1,50){
    comb[i][0]=1; REP(j,1,50) comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
  }
  
  node = 0;
  rep(a,k+1) rep(b,k+1) rep(c,k+1) rep(d,k+1){
    if(a+b+c+d != k) continue;
    num[a][b][c][d] = node++;
  }

  n = before.size();
  rep(i,n){
    A[i] = B[i] = C[i] = D[i] = 0;
    E[i] = F[i] = G[i] = H[i] = 0;
    rep(j,before[i].size()){
      if(before[i][j]=='A') A[i]++;
      if(before[i][j]=='B') B[i]++;
      if(before[i][j]=='C') C[i]++;
      if(before[i][j]=='D') D[i]++;
    }
    rep(j,after[i].size()){
      if(after[i][j]=='A') E[i]++;
      if(after[i][j]=='B') F[i]++;
      if(after[i][j]=='C') G[i]++;
      if(after[i][j]=='D') H[i]++;
    }
  }

  m = 0;
  rep(a,k+1) rep(b,k+1) rep(c,k+1) rep(d,k+1){
    if(a+b+c+d != k) continue;
    rep(i,n) if(a >= A[i] && b >= B[i] && c >= C[i] && d >= D[i]){
      edge1[m] = num[a][b][c][d];
      edge2[m] = num[a-A[i]+E[i]][b-B[i]+F[i]][c-C[i]+G[i]][d-D[i]+H[i]];
      m++;
    }
  }

  g.node = rev.node = node;
  ListGraphSetDirectEdges(&g,edge1,edge2,m);
  ListGraphSetDirectEdges(&rev,edge2,edge1,m);

  N = ListGraphStronglyConnectedComponents(&g, &rev, bun, mem);

  rep(i,N) edge[i].clear();
  rep(i,N) w[i] = 0, dp[i] = -1;
  rep(i,m){
    st = bun[edge1[i]];
    ed = bun[edge2[i]];
    if(st==ed) continue;
    edge[st].push_back(ed);
  }

  j = 0;
  rep(a,k+1) rep(b,k+1) rep(c,k+1) rep(d,k+1){
    if(a+b+c+d != k) continue;
    res = comb[k][a] * comb[k-a][b] * comb[k-a-b][c];
    w[bun[j]] += res;
    j++;
  }

  res = 0;
  rep(i,N){
    tmp = solve(i);
    if(res < tmp) res = tmp;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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