Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Round 4 EASY - BankLottery (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 4 EASY (250pt)
Problem Statement
Open 2010 Algorithm Round 4 自分の参加記録

問題概要

50人以下の銀行の残高が与えられる.
毎週,残高の額に比例する確率で,1人当選して,賞金が配られる.
N週後の0番目の人の残高の期待値を求める問題.
Nは1000以下.

解法

各週の口座に入っている期待値を計算していくだけ.
期待値の割合が毎週固定であることに気づいたら,
 最初の残高 + 最初の残高 / 全員の残高の和 * 当選金額 * 週の数
で答えが求まる.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class BankLottery {
public:
double expectedAmount(vector <int> accountBalance, int weeklyJackpot, int weekCount) {
  int i,j,k,n;
  double now[60], sum;

  n=accountBalance.size();
  rep(i,n) now[i]=accountBalance[i];
  while(weekCount--){
    sum = 0;
    rep(i,n) sum += now[i];
    rep(i,n) now[i] += now[i]/sum * weeklyJackpot;
  }

  return now[0];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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