yukicoder No. 75 : 回数の期待値の問題
問題リンク : No.75 回数の期待値の問題 - yukicoder
問題概要 :
日本語なので略
解法 :
これまでの目の合計をノードとする ( つまり0,1,2,...,K がノードとなる )
各ノードから遷移できるノードに対して辺を張り、有向グラフをつくる
各辺の重みは1とする ( 1回サイコロを振るため )
こうすると問題は、0番目のノードからK番目のノードまで移動する距離の期待値を求めるものとなる
あとはこのグラフから連立1次方程式をつくり解くことで答えが得られる
AOJ 2171 と同じアイデアなので分からなければその問題の解説を読むとよい
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define EPS (1e-8) #define equals(a,b) (fabs((a)-(b))<EPS) using namespace std; typedef vector<double> vd; typedef vector<vd> mat; vector<double> gauss_jordan(const mat& A,const vd& b){ int n = A.size(); mat B(n,vd(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 vd(); 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]; } } } vd x(n); for(int i=0;i<n;i++) x[i] = B[i][n]; return x; } int K; void compute(){ mat A(K+1,vector<double>(K+1,0)); vd b(K+1,0); rep(src,K){ REP(dst,src+1,src+7){ if( dst <= K ) { A[src][dst] += -1; } else { A[src][0] += -( (src+7) - dst ); break; } } A[src][src] += 6; b[src] += 6; } A[K][K] = 1; vector<double> answer = gauss_jordan(A,b); printf("%.10f\n",answer[0]); } int main(){ cin >> K; compute(); return 0; }