練習帳

■ [実践][SRM] TopCoder Single Round Match 504.5 Div1 950 TheTicketsDivOne 02:21

　コンテスト結果概要

　個人結果（要ログイン）

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];
  }
};

ツイートする