Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-19

[][] TopCoder Single Round Match 504.5 Div1 950 TheTicketsDivOne 02:21 はてなブックマーク -  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];
  }
};