Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

1次元上に,12個以下の半径0のボールが置いてある.それぞれのボールの位置が与えられる.
時間0で全てのボールが左右どちらかに確率0.5ずつで動き始める.
ボールのスピードは1で固定,ぶつかると跳ね返るけど,スピードは1で固定.
時間T以下の間に衝突する回数の期待値を求める問題.

解法

ボールを区別する必要はないので,ボールが衝突するというのをすれ違うと考える.
E[A+B]=E[A]+E[B]なので,それぞれ2つのボールのペアが衝突する期待値を考えて,それを足す.
2つのボールが衝突するのは,初期位置の距離が2T以下の場合,確率1/4で衝突する.
思いつかなければ,ボールの個数が12個しかないので,全パターンをシミュレーションしてもOK.

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 BouncingBalls {
public:
double expectedBounces(vector <int> x, int T) {
  int i,j; double res=0;
  rep(i,x.size()) REP(j,i+1,x.size()) if(-2*T<=x[i]-x[j] && x[i]-x[j]<=2*T) res += 1/4.0;
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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