Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM504.5 DIV1 HARD - TheTicketsDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM504.5 DIV1 HARD (900pt)
Problem Statement
SRM504.5 DIV1 自分の参加記録

問題概要

N人 (1000以下) が一列に並んでいて,自分は先頭からM番目にいる.
以下の操作によって,1人を選ぶとき,自分が選ばれる確率を求める問題.
 列に1人しかいなければ,その人を選ぶ.
 そうでなければ,サイコロを振って,
  4がでれば,先頭の人を選んで終了
  2か6がでれば,先頭の人は選ばれなかったとして,権利をなくす
  1か3か5がでれば,先頭の人は一番後ろに並びなおす

解法

ループのあるDP.
NとMを状態として,O(N^2)のDPとなる.
あまりに後ろに並んでいる人はほとんど選ばれることはないので,ループは真面目に解決しなくても,適当に収束するまで100回程度ガウスザイデルっぽく計算しても通る.
以下のコードは,自分が先頭で,自分以外にN人いるときに自分が選ばれる確率でDPしている.
真面目にコンビネーションを計算するとdoubleでもオーバーフローするので,logを取って回避している.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

double dp[1200];
double fact[1200];

class TheTicketsDivOne {
public:
double find(int n, int m) {
  int i,j,k;
  double res, loop, per, sum;
  double dp[1200];

  fact[0] = 0;
  REP(i,1,1200) fact[i] = fact[i-1] + log(i);

  dp[0] = 1;
  REP(i,1,1200){
    loop = pow(0.5, i+1);

    res = 1.0/6.0;
    REP(k,0,i){
      per = log(0.5) * k + log(1.0/3.0) * (i-k) + fact[i] - fact[i-k] - fact[k];
      per = exp(per);
      per *= 0.5;
      res += per * dp[k];
    }

    res /= 1 - loop;
    dp[i] = res;
  }

  res = 0; sum = 0;
  REP(i,m-1,m) REP(k,0,m){
    per = log(0.5) * k + log(1.0/3.0) * (i-k) + fact[i] - fact[i-k] - fact[k];
    per = exp(per);
    sum += per;
    res += per * dp[n-(m-k)];
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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