SRM504.5ってなんだろ。SRM504がunratedだった?
http://community.topcoder.com/stat?c=problem_statement&pm=11433
問題
初期状態で1~Nの人が並んでいる。
この状態でサイコロを振り、1人人を選ぶ。
サイコロを振ったときは以下のように処理する。
- 4が出たら列の先頭の人を選んで終了。
- 1,3,5が出たら列の先頭の人を末尾に移動して継続。
- 2,6が出たら先頭の人を列から外して継続。
途中で4が出て1人選ぶか、列が残り1人になるか、K回サイコロを振った時点で処理は終了する。
K回サイコロを振って列に人が残ってたら、先頭の人を選ぶ。
M番目の人が選ばれる確率を求めよ。
解法
1回サイコロを振ると3通りのパターンがある。
最大でK<=10回しかサイコロを振らないので、3^10通り総当たりするだけ。
class TheTicketsDivTwo { int pat; int N,M,K; int hist[11]; public: void dfs(int cur,int npat,vector<int>& v) { int i,j,g=1; for(i=cur;i<K;i++) g*=6; if(cur==K) { if(v[0]==M) pat+=npat; } else if(v.size()==1) { if(v[0]==M) pat+=npat*g; } else { vector<int> v2; //4 if(v[0]==M) pat+=npat*g/6; v2=v; v2.erase(v2.begin()); //2,6 dfs(cur+1,npat*2,v2); //1,3,5 v2.push_back(v[0]); dfs(cur+1,npat*3,v2); } } double find(int n, int m, int k) { int i; pat=0; N=n;M=m;K=k; vector<int> V; FOR(i,N) V.push_back(i+1); dfs(0,1,V); double ret=pat; FOR(i,k) ret/=6.0; return ret; } };
まとめ
Div2 Hardとはいえだいぶ簡単なような。