yukicoder No.58 - イカサマなサイコロ

Source

ニコニコミュニティ
問題文

問題概要

サイコロAは普通のサイコロで，サイコロBは $4$ から $6$ の目が $2$ 個ずつある歪んでいないサイコロである．
太郎くんは，サイコロAを $N-K$ 個，サイコロBを $K$ 個振る．
二郎くんは，サイコロAを $N$ 個振る．
出目の和を比べた時，太郎くんの出目の和の方が大きくなる確率を求める問題．

解法

それぞれ動的計画法で出目の和が $k$ になる確率を求めれば良い．
状態として，（今まで振ったサイコロの数，出目の和）を取り，その確率を計算する．
要求誤差が緩いので，モンテカルロ法でも通る．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}

int N, K;
double dp1[100], dp2[100], nx[100];

int main(){
  int i, j, k;
  double res;
  
  reader(&N,&K);
  dp1[0] = dp2[0] = 1;

  rep(k,K){
    rep(i,100) nx[i] = 0;
    rep(i,90) REP(j,4,7) nx[i+j] += dp1[i] / 3;
    rep(i,100) dp1[i] = nx[i];
  }
  rep(k,N-K){
    rep(i,100) nx[i] = 0;
    rep(i,90) REP(j,1,7) nx[i+j] += dp1[i] / 6;
    rep(i,100) dp1[i] = nx[i];
  }

  rep(k,N){
    rep(i,100) nx[i] = 0;
    rep(i,90) REP(j,1,7) nx[i+j] += dp2[i] / 6;
    rep(i,100) dp2[i] = nx[i];
  }

  res = 0;
  rep(i,100) rep(j,i) res += dp1[i] * dp2[j];

  printf("%.10f\n",res);

  return 0;
}

Current time: 2024年04月24日09時45分01秒
Last modified: 2014年12月23日23時07分59秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：