AOJ 1286 - Expected Allowance

問題概要

n個のサイコロがあり、それぞれのサイコロには1〜mまでの目がある。
サイコロをn個振ったときの和をSとするとき、S-kの期待値を求めよ。
ただしS-kが0以下になる場合はS-kを1と見なす。

制約

• 1 ≤ n
• 2 ≤ m
• 0 ≤ k < nm
• nm × mⁿ < 100000000

解法

全探索。
それぞれのサイコロの出目を全て試す。

制約の与えられ方がよくわからなかったが間に合った。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
int N,M,K;
map<int,int> mp;
 
void make(int n,int sum){
  if(N == n){
    if(sum-K <= 0){
      mp[1]++;
    }else{
      mp[sum-K]++;
    }
    return;
  }
  for(int i = 0 ; i < M ; i++){
    make(n+1,sum+i+1);
  }
}
 
int main(){
  while(cin >> N >> M >> K, N){
    mp.clear();
    make(0,0);
    double ans = 0;
    map<int,int>::iterator it;
    for(it = mp.begin() ; it != mp.end() ; ++it){
      ans += ((double)it->second/pow((double)M,N))*it->first;
    }
    printf("%.8f\n",ans);
  }
  return 0;
}