Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM467 DIV1 EASY (250pt)
TopCoder SRM467 DIV2 MEDIUM (500pt)
Problem Statement
SRM 467 自分の参加記録

問題概要

生徒は最初は時刻0に部屋に行って,以下の行動を繰り返す.
 WaitTimeだけ部屋にいる.区間の両端の時間は部屋にいる.
 その後,WalkTimeだけ部屋に居ない.
教授は時間bestArrivalからworstArrivalまでの中で一様分布にしたがって部屋に到着する.
教授が部屋に到着した瞬間から,そのlateTime未満後までの間に生徒がいればOK.
OKじゃない確率を求める問題.

解法

bestArrival=worstArrivalのときは例外処理する.
後は愚直にシミュレーションして求めていく.

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

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

// #includeとusing namespace std;は略

class LateProfessor {
public:
double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) {
  int i,j,k,now,ok=0;
  double res=0;

  if(lateTime >= walkTime) return 0.0;
  
  now=0;
  while(now <= worstArrival + waitTime + walkTime + lateTime){
    j = now - lateTime;
    k = now + waitTime;

    if(j < bestArrival && bestArrival <= k) ok=1;

    if(j < bestArrival)  j = bestArrival;
    if(k > worstArrival) k = worstArrival;
    i = k-j;
    if(i>0) res += i;

    now += waitTime + walkTime;
  }

  if(ok && bestArrival == worstArrival) return 0.0;
  if(bestArrival == worstArrival) return 1.0;

  return 1.0 - res / (worstArrival - bestArrival);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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