Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM501 DIV1 MEDIUM/DIV2 HARD - FoxAverageSequence (この記事を編集する[管理者用])

Source

TopCoder SRM501 DIV1 MEDIUM (500pt)
TopCoder SRM501 DIV2 HARD (1000pt)
Problem Statement
SRM501 DIV1 自分の参加記録

問題概要

beautifulな数列aとは以下の条件をみたすものである.  ・数列の各要素は0以上40以下の整数  ・k番目の要素は,0番目~k-1番目の要素の平均値以下にならないといけない  ・a[k] > a[k+1] > a[k+2]というように2回連続で減ることはない 一部埋まっていない,長さN (40以下) の数列が与えられるので,埋まってない場所を適当な数字に置き換えてできるbeautifulな数列の個数をmod 10^9+7で求める問題.

解法

典型的なDP.
平均値以下になってるかどうかの判定のために,今までの和と,
2回連続で下がるかどうかの判定のために,今まで何回連続で下がったかというのと,配列に前回使った値を状態とする.
だいたい計算量が40^5で怪しいが十分通る.
前回の使った値が0~kまでの時の,DP配列の和,などを求めておくことで40^4にできる.(以下のコードは工夫なく40^5)

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

int n, in[55];
int dp[41][1700][41][2];

int solve(int st,int sum,int bef,int dec){
  int i,j,k,nd;
  ll res = 0;

/*  printf("%d %d %d %d\n",st,sum,bef,dec);*/

  if(dp[st][sum][bef][dec] >= 0) return dp[st][sum][bef][dec];
  if(st==n) return dp[st][sum][bef][dec] = 1;

  rep(i,41) if(in[st]==-1 || in[st]==i) {
    nd = dec;
    if(bef > i) nd++; else nd=0;
    if(nd >= 2) continue;

    if(i*st > sum) continue;
    res += solve(st+1, sum+i, i, nd);
  }

  res %= M;
  return dp[st][sum][bef][dec] = res;
}

class FoxAverageSequence {
public:
int theCount(vector <int> seq) {
  int i,j,k,l;

  rep(i,41) rep(j,1700) rep(k,41) rep(l,2) dp[i][j][k][l] = -1;

  n=seq.size();
  rep(i,n) in[i] = seq[i];

  return solve(0, 0, 0, 0);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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