Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

ソーシャルネットワークで,各個人のページには,友だち登録してるうちの中からランダムにK人へのリンクが表示される.
K人以下しか友達がいなければ,全員表示される.
N人の友達関係(友達関係はその中で閉じている)が与えられたとき,自分のページから初めて,自分の友達を全部ちょうど1回ずつリンクをたどって辿りつける確率を求める問題.
次に行く友達のページは,達成確率を最大にするように選ぶ.
Nは36以下.おのおのの人の友達の数は高々15.

解法

組み合わせの数を計算しながら,ビット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 read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}


int n, m, k;
double dp[300000][20];
double c[50][50];
int edge[40][40], deg[40];
int num[30];

double solve(int mask, int last){
  int i,j,a,b;
  int lis[20], ls, total;
  double per[20];
  double res=0;

  if(dp[mask][last]>-1) return dp[mask][last];
  if(mask == (1<<m)-1) return dp[mask][last]=1;

  a = num[last];
  ls=0; total = deg[a];
  rep(i,m) if(!(mask&1<<i) && edge[a][num[i]]) lis[ls++]=i;

  rep(i,ls) per[i] = solve(mask^(1<<lis[i]), lis[i]);
  sort(per,per+ls);

  if(ls==0) return dp[mask][last]=0;

  if(total <= k){
    res = per[ls-1];
  } else {
    rep(i,ls){
      if(total-i < k) break;
      res += per[ls-1-i] * c[total-1-i][k-1] / c[total][k];
    }
  }

  return dp[mask][last] = res;
}

class FriendTour {
public:
double tourProbability(vector <string> friends, int K_) {
  int i,j;
  int tmp[1000], ts;

  c[0][0]=1; REP(j,1,50) c[0][j]=0;
  REP(i,1,50){
    c[i][0]=1; REP(j,1,50) c[i][j]=c[i-1][j-1]+c[i-1][j];
  }

  k=K_; n=friends.size();
  rep(i,n) rep(j,n) edge[i][j]=0;
  rep(i,n){
    ts = read_int_from_char(friends[i].c_str(),-1,tmp);
    rep(j,ts) edge[i][tmp[j]-1]=1;
  }

  m=1; num[0]=0; rep(i,n) if(edge[0][i]) num[m++]=i;
  rep(i,1<<m) rep(j,m) dp[i][j]=-100;

  rep(i,n) deg[i]=0;
  rep(i,n) rep(j,n) if(edge[i][j]) deg[i]++;
  
  return solve(1,0);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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