Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM527 DIV1 MEDIUM (450pt)
Problem Statement

問題概要

n*m (30*30以下) のグリッド (rows) が与えられる.
また,m個だけ,長さnの文字列 (cols) が与えられる.
それぞれは,グリッド,文字は,0か1か?からなる.
?を0か1に変えて,以下の条件を満たすようにしたい.
 各グリッドを縦に読んで,得られるm個の長さnの文字列は,(順番を入れ替えると)colsに一致する.
条件を満たすグリッドのうち,辞書順最小のものを求める問題.条件を満たすグリッドは少なくても1つは存在することは保証されている.

解法

つまりは,各列をどの文字列に対応させれば良いのか,マッチング問題になる.
なので,条件を満たす?の変え方が存在するかどうかは判定することができる.
グリッドの?を最初の方から,1文字ずつ0に置き換えて,条件をみたすことができなくなったらそれは1に置き換える,とgreedyに置き換えていく.

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 INT_INF 1000000000

#define INT_LIST_MAX_FLOW_NODE 102
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];
int intLmfQueue[INT_LIST_MAX_FLOW_NODE];

void intListMaxFlowLevelize(int n,int st,int ed){
  int i,j,k,t;
  int q_st,q_end;
  rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_end=1; intLmfQueue[0]=st;
  while(q_st!=q_end){
    i=intLmfQueue[q_st++]; t=intLmfLevel[i]+1;
    rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
      k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
      intLmfLevel[k]=t; intLmfQueue[q_end++]=k; if(k==ed) return;
    }
  }
}

int intListMaxFlowFlow(int i,int ed,int lim){
  int j,k,ret=0,t,s,ji;
  if(i==ed) return lim;
  rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
    k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
    s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
    t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
    ret+=t; lim-=t; ji=intLmfInv[i][j];
    intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
    if(!lim) break;
  }
  if(lim) intLmfLevel[i]=-1;
  return ret;
}

/* Dinic(Dinitz) */
/* 制約: n<=INT_LIST_MAX_FLOW_NODE, st!=ed */
int intListMaxFlow(int n,int st,int ed){
  int ret=0;
  for(;;){
    intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
    ret += intListMaxFlowFlow(st,ed,INT_INF);
  }
  return ret;
}

void intListMaxFlowEdgeInit(){
  int i;
  rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeInitAdv(int n){
  int i;
  rep(i,n) intLmfEdgeSize[i]=0;
}

/* 制約: n1!=n2 */
void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
  int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
  intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
  intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
  intLmfInv[n1][s1]=s2;  intLmfInv[n2][s2]=s1;
}



class P8XMatrixRecovery {
public:
vector <string> solve(vector <string> rows, vector <string> cols) {
  int i,j,k;
  int a, b;
  int x, y;
  int node, st, ed;

  x = rows.size();
  y = rows[0].size();
  
  rep(i,x) rep(j,y) if(rows[i][j]=='?'){
    node = y+y+2;
    st = node - 2;
    ed = node - 1;

    intListMaxFlowEdgeInitAdv(node);

    rows[i][j] = '0';
    rep(a, y) intListMaxFlowEdgeAdd(st, a, 1, 0);
    rep(a, y) intListMaxFlowEdgeAdd(a+y, ed, 1, 0);

    rep(a, y) rep(b, y){
      rep(k, x){
        if(rows[k][a]=='?' || cols[b][k]=='?') continue;
        if(rows[k][a] != cols[b][k]) break;
      }
      if(k==x) intListMaxFlowEdgeAdd(a, b+y, 1, 0);
    }

    k = intListMaxFlow(node, st, ed);
    if(k!=y){ rows[i][j] = '1'; continue; }
  }

  return rows;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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