Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

ビンゴカードと,今まので出た数字が与えられる.
ビンゴは1~75の数字を使う.
ビンゴカードのうち,どのサブセットが全部出ていればいくら貰えると言った規則が与えられる.
次に1個ボールが来たときに,得られる金の増加分の期待値を求める問題.

解法

今まで出た数字を消して,残り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)

class ExtraBall {
public:
double expectedPayout(vector <int> card, vector <int> balls, vector <string> patterns, vector <int> prizes) {
  int i,j,k;
  double res=0;

  rep(i,card.size()){
    rep(j,balls.size()) if(card[i]==balls[j]) break;
    if(j==balls.size()) continue;

    rep(j,patterns.size()) patterns[j][i]='.';
  }

  rep(i,patterns.size()){
    k=0;
    rep(j,card.size()) if(patterns[i][j]=='X') k++;
    if(k==1) res += prizes[i]/(75.0-balls.size());
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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