Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Round 1B C問題 - Your Rank is Pure (この記事を編集する[管理者用])

Source

Google code jam 2010 Round 1B C問題
Problem Statement

問題概要

与えられた2以上の自然数Nに対して,
 {2, 3, ..., N}
の部分集合SでNがPureなものの数をmod 100003で求める問題.
F(N)を集合Sの中にあるN以下のものの数として
 「NがPure」 とは 「F(N)=1 か F(N)がPure のどちらかが成り立つ」
で定義する.
small: Nは25以下.
large: Nは500以下

解法

コンビネーションを使いながら計算するO(N^3)のDP.
 dp[i][j] = {2, 3, ..., i}の部分集合でiがPureで要素数がjの集合の数

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#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 100003

ll dp[510][510];
int res[510];
int conb[510][510];

int main(){
  int i,j,k,l,m,n;

  int size,count=0;

  conb[0][0]=1; REP(j,1,510) conb[0][j]=0;
  REP(i,1,510){ conb[i][0]=1; REP(j,1,510) conb[i][j]=(conb[i-1][j-1]+conb[i-1][j])%M; }

  rep(i,510) dp[i][1]=1;
  REP(i,2,510) REP(j,2,i){
    dp[i][j]=0;
    REP(k,1,j) dp[i][j] = (dp[i][j]+dp[j][k]*conb[i-j-1][j-k-1])%M;
  }

  REP(i,2,510){
    res[i]=0;
    REP(j,1,i) res[i]=(res[i]+dp[i][j])%M;
  }
  
  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    printf("Case #%d: %d\n",++count,res[n]);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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