Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM532 DIV1 MEDIUM (450pt)
Problem Statement

問題概要

N, M, Kが与えられた時,以下の条件を満たす無向グラフの数をmod 1000000007で求める問題.
 ノード数N (30以下) で,枝数M (30以下)
 各ノードの次数は偶数 (0でも良い,同じノード間にたくさん枝があっても良い)
 ノードAとノードBの間に枝があるならば,|A-B|はK以下.ただしノード番号は1からNまでとする.Kは8以下.

解法

DPする.
少なくても状態は,今見ているノード番号(N),すでに使った枝の本数(M),自分とK個先までの次数の偶奇(2^(K+1))が必要.
ノード番号が小さい方から見て行って,枝を追加していく.
枝を追加していく順番に依存させないために,最後に枝を追加した相手のノード番号(K)も覚えておくと良い.
すると,状態数はN*M*K*2^(K+1)ぐらいになる.

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 ll long long
#define M 1000000007

int k;
ll dp[31][31][10][600];

ll solve(int n, int m, int nex, int mask){
  int i,j;
  int smask;
  ll res = 0;

  if(dp[n][m][nex][mask] >= 0) return dp[n][m][nex][mask];
  if(n == 0){
    if(m==0 && mask==0) res = 1;
    return dp[n][m][nex][mask] = res;
  }

  if(nex==n-1 || nex==k){
    if(mask%2) return dp[n][m][nex][mask] = 0;
    return dp[n][m][nex][mask] = solve(n-1, m, 0, mask/2);
  }

  rep(i,m+1){
    smask = mask;
    if(i%2){
      smask ^= (1<<0);
      smask ^= (1<<(nex+1));
    }
    res += solve(n,m-i,nex+1,smask);
  }

  res %= M;
//  printf("%d %d %d %d : %lld\n",n,m,nex,mask,res);
  return dp[n][m][nex][mask] = res;
}

class DengklekBuildingRoads {
public:
int numWays(int n, int m, int k__) {
  int a,b,c,d;
  int res;

  k = k__;

  rep(a,31) rep(b,31) rep(c,10) rep(d,600) dp[a][b][c][d] = -1;
  res = solve(n, m, 0, 0);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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