Yuki 58 イカサマなサイコロ ( DP or Monte Carlo )

No.58 イカサマなサイコロ - yukicoder
制限が小さいゆえMonte Carlo で適当にやってもおk。
DP:

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

signed main(){
  int N, K; cin >> N >> K;
  vector< vector< double > > dpn( N + 1, vector< double >( N * 6 + 1 ) );
  dpn[ 0 ][ 0 ] = 1.0;
  for( int i = 0; i < N; ++i )
    for( int j = 0; j < dpn[ i ].size(); ++j )
      for( int k = 1; k <= 6; ++k )
        if( j + k < dpn[ i ].size() )
          dpn[ i + 1 ][ j + k ] += dpn[ i ][ j ] / 6.0;
  vector< vector< double > > dpk( K + 1, vector< double >( K * 6 + 1 ) );
  dpk[ 0 ][ 0 ] = 1.0;
  for( int i = 0; i < K; ++i )
    for( int j = 0; j < dpk[ i ].size(); ++j )
      for( int k = 4; k <= 6; ++k )
        if( j + k < dpk[ i ].size() )
          dpk[ i + 1 ][ j + k ] += dpk[ i ][ j ] / 3.0;
  vector< double > tarou( N * 6 + 1 );
  for( int i = 0; i < dpk[ K ].size(); ++i )
    for( int j = 0; j < dpn[ N - K ].size(); ++j )
      tarou[ i + j ] += dpk[ K ][ i ] * dpn[ N - K ][ j ];
  double ans = 0.0;
  for( int i = 0; i < tarou.size(); ++i )
    for( int j = 0; j < i; ++j )
      ans += tarou[ i ] * dpn[ N ][ j ];
  cout << fixed << setprecision( 6 ) << ans << endl;
  return 0;
}

Monte Carlo:

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

signed main(){
  int N, K; cin >> N >> K;
  const int trial = ( int ) 1e6;
  int win_cnt = 0;
  for( int i = 0; i < trial; ++i ){
    int nirou = 0;
    for( int j = 0; j < N; ++j )
      nirou += rand() % 6 + 1;
    int tarou = 0;
    for( int j = 0; j < N - K; ++j )
      tarou += rand() % 6 + 1;
    for( int j = 0; j < K; ++j )
      tarou += rand() % 3 + 4;
    win_cnt += tarou > nirou;
  }
  cout << fixed << setprecision( 6 ) << 1.0 * win_cnt / trial << endl;
  return 0;
}