TopCoder(delta2323) / Codeforces(delta) / twitter
2011-05-19
■ [実践][SRM] TopCoder Single Round Match 504.5 Div1 950 TheTicketsDivOne 
個人結果(要ログイン)
950 TheTicketsDivOne
要約
n人が1列に並んでいて,そのなかから1人を次のように選ぶ
- サイコロを振り,出た目に応じて現在先頭の人が次のように行動する
- 4 : 先頭の人を選んで終了する
- 1,3,5 : 先頭の人が列の最後尾に並び直す
- 2,6 : 先頭の人が列から去る
- 最初に戻る
一番最初の状態でm番目(1-indexed)に並んでいる人が選ばれる数を求めよ.nは1以上1000以下.mは1以上n以下.
(まだ正しい答えは得られていません,思いついた2通りについて書きます.)
方針
p[i][j]で列にi人いる時に,先頭からj番目の人が選ばれる確率とすると,
p[1][1] = 1 p[i][1] = p[i][i] /2 + 1 / 6 ( j = 1 ) p[i][j] = p[i][j-1] /2 + p[i-1][j-1] / 3 ( j != 1 )
の漸化式が得られる.p達の値を求める時に相互参照するので,この式の形のままでは動的に解く事は出来ない.
そこで,右辺から左辺を求める計算を収束するまで行う.
コード例
p[i][j] 達の更新にO(n^{2})かかり,nは1000程度なので,値の更新は10周期程度しか出来ない.しかし,p[1000][1000]の値が0でない値で更新されるには,最低でも更新を1000周期行わなければならず,この方法では正しい答えは求められない.
(このコードはTLEを起こします) class TheTicketsDivOne { public: double find(int n, int m) { vector<vector<double> > p(n + 1, vector<double> (n + 1, 0)); p[1][1] = 1; for(int k = 0; k <= 10000; k++){ vector<vector<double> > nx(n + 1, vector<double> (n + 1, 0)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ if(i == 1){ nx[1][1] = 1; continue; } if(j != 1){ nx[i][j] = p[i][j-1] / (double) 2 + p[i-1][j-1] / (double) 3; }else{ nx[i][1] = p[i][i] / (double) 2 + 1 / (double) 6; } } } p = nx; } return p[n][m]; } };
方針2
漸化式を変形すると
p[i][1] -p[i][i] /2 = 1 / 6 ( j = 1 ) - p[i][j-1] /2 + p[i][j] = p[i-1][j-1] / 3 ( j != 1 )
となり,p[i-1]達からp[i]達を連立一次方程式で求められる.連立方程式はGauss Jordanの消去法で求められるが,これは行列のサイズの3乗のアルゴリズムなので,i = 1〜nまで操作すると,全体でO(n^{4})のアルゴリズムとなる.
コード例2
(このコードはTLEを起こします.Gauss-Jordanの消去法は「プログラミングコンテスト・チャレンジブック」のコードを用いています.)
#include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> using namespace std; typedef vector<double> vec; typedef vector<vector<double> > mat; typedef long long ll; double abs(double k){ return k >= 0 ? k : -k; } const double eps = 1e-9; vec gauss_jordan(const mat& A, const vec& b){ int n = A.size(); mat B(n, vec(n+1)); for(int i = 0;i < n;i++) for(int j = 0;j< n;j++) B[i][j] = A[i][j]; for(int i = 0;i < n;i++) B[i][n] = b[i]; for(int i = 0;i < n;i++){ int pivot = i; for(int j = i;j < n;j++) if(abs(B[j][i] > abs(B[pivot][i]))) pivot = j; swap(B[i], B[pivot]); if(abs(B[i][i]) < eps) return vec(); for(int j = i + 1; j <= n;j++) B[i][j] /= B[i][i]; for(int j = 0;j < n;j++) if(i != j) for(int k = i+1 ;k <=n ;k++) B[j][k] -= B[j][i] * B [i][k]; vec x(n); for(int i = 0;i < n;i++) x[i] = B[i][n]; return x; } class TheTicketsDivOne { public: double find(int n, int m) { m--; vec x(1.0); for(int i = 1;i < n;i++){ cout << i << endl; vec b(i + 1); mat A(i + 1, vec(i + 1)); for(int j = 0; j<= i;j++){ A[j][j] = 1; A[j][(j + i ) % (i + 1)] = -1.0/ 2; } if(i == 1){ b[1] = 1.0 / 3; }else{ for(int j = 0;j < i ;j++){ b[j + 1] = x[j] / 3; } } b[0]= 1/(double) 6; x.clear();x.resize(i + 1); x = gauss_jordan(A, b); } return x[m]; } };