Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM401 DIV1 EASY/DIV2 MEDIUM - FIELDDiagrams (この記事を編集する[管理者用])

Source

TopCoder SRM401 DIV1 EASY (250pt)
TopCoder SRM401 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

1行目がf以下, 2行目がf-1以下,k行目がf-k+1以下を満たすヤング図形の数を求める問題.
fは30以下.

解法

DPすれば良い.
なんかよく見ると答えがカタラン数なので,それを使っても良い.
カタラン数と解釈する方法の1つは最初に赤のみからなるf+1の長さの行があるとして,
上から見て行って,k行目からk+1行目に行く時,
 赤が減少した数だけ(を書いて,その後)を1つ書く
とすると,対応付けられた()の列と一対一に対応する,とかと自分は考えてみた.
wikipediaにそのもの図があった….( jpg )

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

// DP
ll solve1(int fieldOrder){
  int i,j,k;
  ll dp[40][40]={0};
  dp[0][fieldOrder]=1;
  rep(i,39) rep(j,40) rep(k,min(fieldOrder-i,j)+1) dp[i+1][k]+=dp[i][j];
  return dp[fieldOrder+1][0]-1;
}

// Catalan number
ll solve2(int fieldOrder){
  int i,j; ll C[80][80];

  // C[n][k] = n!/k!/(n-k)!
  C[0][0]=1; REP(j,1,80) C[0][j]=0;
  REP(i,1,80){
    C[i][0]=1; REP(j,1,80) C[i][j]=C[i-1][j-1]+C[i-1][j];
  }
  
  return C[2*(fieldOrder+1)][fieldOrder+1]/(fieldOrder+2) - 1;
}

class FIELDDiagrams {
public:
ll countDiagrams(int fieldOrder) {
  ll a=solve1(fieldOrder);
  ll b=solve2(fieldOrder);

  if(a==b) return a;
  return -1985617356178956316LL;
}

};

以下のコードは実際に本番でサブミットしたコードです.

// #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

ll f;
ll ans[40][40];

ll sol(int k,int last){
  ll i,j,mx;
  ll res=0;

  if(ans[k][last]>=0) return ans[k][last];

  mx = f-k;
  if(last==0){ans[k][last]=1; return ans[k][last];}

  res++;
  for(i=1;i<=last && i<=mx;i++){
    res += sol(k+1,i);
  }

  ans[k][last]=res;
  return res;
}

class FIELDDiagrams {
public:
long long countDiagrams(int f_) {
  ll i,j;

  f=f_;
  rep(i,40) rep(j,40) ans[i][j]=-1;
  return sol(0,39)-1;
} 

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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