Submission #7479988


Source Code Expand

// 3_drango2015pre_c
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
#define MOD (1000000007)
typedef long long ll;

vector<double> dp;
vector<vector<double>> ncr;

void calc_ncr(int k){

    for(int n = 1; n <= k; n++){
        ncr[n][0] = 1;
        ncr[n][1] = n;
        for(int r = 2; r <= n; r++){
            ncr[n][r] = ncr[n][r - 1] / r * (n - r + 1);
        }
    }
}

int hantei(int g, int c, int p){
    char ch;
    if((g == 0 && c == 0) || (c == 0 && p == 0) || (p == 0 && g == 0)){
        return g + c + p;
    }

    if(g == c && c == p){
        // pattern 2-3
        return g + c + p;
    }

    // g, c, pいずれも1人以上
    if(g != 0 && c != 0 && p != 0){
        if((g < c && g < p) || (c < g && c < p) || (p < g && p < c)){
            // pattern2-1
            if(g == min({g, c, p})) return g;
            else if(c == min({g, c, p})) return c;
            else return p;
        }

        if((g < p && c < p)){
            return g;
        }else if((c < g && p < g)){
            return c;
        }else{
            return p;
        }
    }

    if(g == 0){
        if(c <= p) return c;
        else return p;
    }
    if(c == 0){
        if(p <= g) return p;
        else return g;
    }
    if(p == 0){
        if(g <= c) return g;
        else return c;
    }
}

double dfs(int n){
    if(dp[n] >= 0) return dp[n];

    double expect = 0.0;

    double p_aiko = pow(1.0 / 3.0, n) * 3;
    if(n % 3 == 0){
        double tmp = pow(1.0 / 3.0, n);
        tmp *= ncr[n][n / 3] * ncr[2 * n / 3][n / 3];
        p_aiko += tmp;
    }

    for(int g = 0; g <= n; g++){
        for(int c = 0; c <= n - g; c++){
            int p = n - g - c;

            double p_gcp = pow(1.0 / 3.0, n) * ncr[n][g] * ncr[n - g][c];

            int a = hantei(g, c, p);
            if(a == n) continue;

            expect += p_gcp * (dp[a] + 1);
        }
    }
    expect = (expect + p_aiko) / (1.0 - p_aiko);
    dp[n] = expect;
    return expect;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    dp.resize(n + 1);
    ncr.resize(n + 1, vector<double> (n + 1));
    rep(i, n + 1){
        dp[i] = -1;
    }
    calc_ncr(n);


    dp[0] = 0;
    dp[1] = 0;

    cout << dfs(n) << endl;

    return 0;
}

Submission Info

Submission Time
Task C - ゲーマーじゃんけん
User Yoko453
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3768 Byte
Status WA
Exec Time 3 ms
Memory 384 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 2
WA × 97
Set Name Test Cases
All input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt
Case Name Status Exec Time Memory
input-002.txt AC 3 ms 384 KB
input-003.txt AC 1 ms 256 KB
input-004.txt WA 1 ms 256 KB
input-005.txt WA 1 ms 256 KB
input-006.txt WA 1 ms 256 KB
input-007.txt WA 1 ms 256 KB
input-008.txt WA 1 ms 256 KB
input-009.txt WA 1 ms 256 KB
input-010.txt WA 1 ms 256 KB
input-011.txt WA 1 ms 256 KB
input-012.txt WA 1 ms 256 KB
input-013.txt WA 1 ms 256 KB
input-014.txt WA 1 ms 256 KB
input-015.txt WA 1 ms 256 KB
input-016.txt WA 1 ms 256 KB
input-017.txt WA 1 ms 256 KB
input-018.txt WA 1 ms 256 KB
input-019.txt WA 1 ms 256 KB
input-020.txt WA 1 ms 256 KB
input-021.txt WA 1 ms 256 KB
input-022.txt WA 1 ms 256 KB
input-023.txt WA 1 ms 256 KB
input-024.txt WA 1 ms 256 KB
input-025.txt WA 1 ms 256 KB
input-026.txt WA 1 ms 256 KB
input-027.txt WA 1 ms 256 KB
input-028.txt WA 1 ms 256 KB
input-029.txt WA 1 ms 256 KB
input-030.txt WA 1 ms 256 KB
input-031.txt WA 1 ms 256 KB
input-032.txt WA 1 ms 256 KB
input-033.txt WA 1 ms 256 KB
input-034.txt WA 1 ms 256 KB
input-035.txt WA 1 ms 256 KB
input-036.txt WA 1 ms 256 KB
input-037.txt WA 1 ms 256 KB
input-038.txt WA 1 ms 256 KB
input-039.txt WA 1 ms 256 KB
input-040.txt WA 1 ms 256 KB
input-041.txt WA 1 ms 256 KB
input-042.txt WA 1 ms 256 KB
input-043.txt WA 1 ms 256 KB
input-044.txt WA 1 ms 256 KB
input-045.txt WA 1 ms 256 KB
input-046.txt WA 1 ms 256 KB
input-047.txt WA 1 ms 256 KB
input-048.txt WA 2 ms 256 KB
input-049.txt WA 1 ms 256 KB
input-050.txt WA 2 ms 256 KB
input-051.txt WA 2 ms 256 KB
input-052.txt WA 2 ms 256 KB
input-053.txt WA 2 ms 256 KB
input-054.txt WA 2 ms 256 KB
input-055.txt WA 2 ms 256 KB
input-056.txt WA 2 ms 256 KB
input-057.txt WA 2 ms 256 KB
input-058.txt WA 2 ms 256 KB
input-059.txt WA 2 ms 256 KB
input-060.txt WA 2 ms 256 KB
input-061.txt WA 2 ms 256 KB
input-062.txt WA 2 ms 256 KB
input-063.txt WA 2 ms 256 KB
input-064.txt WA 2 ms 256 KB
input-065.txt WA 2 ms 256 KB
input-066.txt WA 2 ms 256 KB
input-067.txt WA 2 ms 256 KB
input-068.txt WA 2 ms 256 KB
input-069.txt WA 2 ms 256 KB
input-070.txt WA 2 ms 256 KB
input-071.txt WA 2 ms 256 KB
input-072.txt WA 2 ms 256 KB
input-073.txt WA 2 ms 256 KB
input-074.txt WA 2 ms 256 KB
input-075.txt WA 2 ms 256 KB
input-076.txt WA 2 ms 256 KB
input-077.txt WA 2 ms 256 KB
input-078.txt WA 2 ms 256 KB
input-079.txt WA 2 ms 256 KB
input-080.txt WA 2 ms 256 KB
input-081.txt WA 2 ms 384 KB
input-082.txt WA 2 ms 256 KB
input-083.txt WA 2 ms 384 KB
input-084.txt WA 2 ms 384 KB
input-085.txt WA 2 ms 384 KB
input-086.txt WA 2 ms 384 KB
input-087.txt WA 2 ms 384 KB
input-088.txt WA 2 ms 384 KB
input-089.txt WA 2 ms 384 KB
input-090.txt WA 2 ms 384 KB
input-091.txt WA 2 ms 384 KB
input-092.txt WA 2 ms 384 KB
input-093.txt WA 2 ms 384 KB
input-094.txt WA 2 ms 384 KB
input-095.txt WA 2 ms 384 KB
input-096.txt WA 2 ms 384 KB
input-097.txt WA 2 ms 384 KB
input-098.txt WA 2 ms 384 KB
input-099.txt WA 2 ms 384 KB
input-100.txt WA 2 ms 384 KB