結果

問題 No.58 イカサマなサイコロ
ユーザー is_eri23is_eri23
提出日時 2014-11-05 01:32:38
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 600 ms / 5,000 ms
コード長 4,634 bytes
コンパイル時間 1,250 ms
コンパイル使用メモリ 165,220 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 19:08:23
合計ジャッジ時間 2,447 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 600 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 57 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 53 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>&)’:
main.cpp:24:139: warning: no return statement in function returning non-void [-Wreturn-type]
   24 | template <class T,class U> std::ostream& operator<<(std::ostream &os, std::pair<T,U> &v){os << "(" << v.first << ", " << v.second << ")"; }
      |                                                                                                                                           ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define numa(x,a) for(auto x: a)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define pf push_front
#define sec second
#define sz(x) ((int)(x).size())
#define ALL( c ) (c).begin(), (c).end()
#define gcd(a,b) __gcd(a,b)
#define mem(x,n) memset(x,n,sizeof(x))
#define endl "\n"
using namespace std;
template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class T,class U> std::ostream& operator<<(std::ostream &os, std::pair<T,U> &v){os << "(" << v.first << ", " << v.second << ")"; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "}" : ", "); return os; }
#define DEBUG1(var0) { std::cerr << (#var0) << "=" << (var0) << endl; }
#define DEBUG2(var0, var1) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG1(var1); }
#define DEBUG3(var0, var1, var2) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG2(var1,var2); }
#define DEBUG4(var0, var1, var2, var3) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG3(var1,var2,var3); }
using ll = long long;
int N,K;
/*
map <int,int> tmp1;
map <int,int> tmp2;
map <int,int> tmp3;
map <int,int> tmp4;
map <int,int> res1;
map <int,int> res2;
*/
//map <int,int> taro;
//map <int,int> jiro;
vector <pair <int,int> > taro_c;
vector <pair <int,int> > jiro_c;
/*
void count2(int n,int sum,bool flag){
  if(n == 0){
    if(flag){
      tmp1[sum] += 1;
    }else{
      tmp2[sum] += 1;
    }
  }else{
    for(int i = 1;i <= 6;i++){
      count2(n-1,sum+i,flag);
    }
  }
  return;
}
void count3(int k,int sum,int tm,bool flag){
  if(k == 0){
    if(flag){
      tmp3[sum] += tm;
    }else{
      tmp4[sum] += tm;
    }
  }else{
    for(int i = 4;i <= 6;i++){
      count3(k-1,sum+i,tm*2,flag);
    }
  }
}
void count(int n,int k,bool is_taro){
  tmp1.clear();tmp2.clear();tmp3.clear();tmp4.clear();
  count2((n-k)/2,0,true);
  count2((n-k+1)/2,0,false);
  count3(k/2,0,1,true);
  count3((k+1)/2,0,1,false);
  res1.clear();res2.clear();
  numa(c1,tmp1){
    numa(c2,tmp2){
      res1[c1.fir+c2.fir] += c1.sec*c2.sec;
    }
  }
  numa(c3,tmp3){
    numa(c4,tmp4){
      res2[c3.fir+c4.fir] += c3.sec*c4.sec;
    }
  }
  numa(r1,res1){
    numa(r2,res2){
      if(is_taro){
        taro[r1.fir+r2.fir] += r1.sec*r2.sec;
      }else{
        jiro[r1.fir+r2.fir] += r1.sec*r2.sec;
      }
    }
  }
  return;
}
*/
int taro[61],jiro[61];
void naive_count(int n,int k,bool flag,int tm=1,int sum = 0){
  if(n == 0 && k == 0){
    if(flag){
      taro[sum] += tm;
    }else{
      jiro[sum] += tm;
    }
    return;
  }
  if(n == 0){
    for(int i= 4;i <= 6;i++){
      naive_count(n,k-1,flag,tm*2,sum+i);
    }
  }else{
    for(int i =1;i <= 6;i++){
      naive_count(n-1,k,flag,tm,sum+i);
    }
  }
}
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> N >> K;
  naive_count(N,0,true);
  naive_count(N-K,K,false);
  for(int i = 1;i <= 6*N;i++){
    if(taro[i] != 0){
      taro_c.pb(mp(i,taro[i]));
    }
    if(jiro[i] != 0){
      jiro_c.pb(mp(i,jiro[i]));
    }
  }
  {
    int sums = 0;
    for(int i = sz(jiro_c)-1;i>=0;i--){
      sums += jiro_c[i].sec;
      jiro_c[i].sec = sums;
    }
  }
  ll ans_child = 0;
  rep(i,sz(taro_c)){
    auto it = upper_bound(ALL(jiro_c),taro_c[i],[](pair <int,int>a,pair <int,int> b){return a.fir < b.fir;});
    if(it != jiro_c.end()){
      ans_child += (ll) taro_c[i].sec * (ll) it->sec;
    }
  }
  long double ans = ans_child;
  rep(i,2*N){
    ans /= 6;
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}
0