読者です 読者をやめる 読者になる 読者になる

Facebook Hacker Cup 2017 Qualification Round - Fighting the Zombie

問題

Fighting the Zombie | Facebook Hacker Cup 2017 Qualification Round

考察

Zは出目の合計を足した後に加算されるので、同じサイコロに対してX回振った場合の確率分布は一定になります。

dp[i][j] := i回同じサイコロを振った時に、合計が値jになる確率

これは、20回 * 400(出目の合計の最大) = 8000程度の大きさのテーブルで保持できます。 それぞれのマスに対して最大で20通りの状態遷移があるため、 20 * 8000 = 1 * 10^{5}程度で計算できそうです。

T=1000なので、毎回与えられる度に計算をしても間に合いそうではありますが、
サイコロの種類は限られているので、それぞれに対してテーブルをメモしておけばより速く計算できます。

最終的な答えは、それぞれの試行でこのテーブルを参照し、H-Z以上のマスを合計してゆけば確率が算出されます。
なお、H-Zが0より小さくなったり、400より大きくなったりするので、適当にmin/maxを取る必要があり要注意です。

コード

class DiceTable {
public:
    const int MAX_N = 21;
    const int MAX_C = MAX_N * 20 + 10;

    map<int, vvd> diceTable;

    DiceTable() {
        vi t = {4, 6, 8, 10, 12, 20};
        rep(i, t.size())
            prepare(t[i]);
    }

    void prepare(int dice) {
        vvd prop(MAX_N, vd(MAX_C, 0.0));
        prop[0][0] = 1.0;

        double one_p = 1.0 / dice;

        rep(i, MAX_N - 1) {
            rep(j, MAX_C) {
                REP(v, 1, dice + 1) {
                    if (prop[i][j] != 0.0 && j + v < MAX_C)
                        prop[i+1][j + v] += prop[i][j] * one_p;
                }
            }
        }

        diceTable[dice] = prop;
    }

    double calc(int dice, int num, int base) {
        double res = 0.0;
        vvd& dt = diceTable[dice];
        REP(i, max(0,base), MAX_C)
            res += dt[num][i];
        return res;
    }
};

double solve() {
    int H, S;
    cin >> H >> S;

    DiceTable dt;
    double ans = 0.0;

    rep(i, S) {
        string s;
        cin >> s;

        stringstream ss, ss2, ss3;
        int x = 0, y = 0, z = 0;
        rep(j, s.size()) {
            if(s[j] == 'd')
                break;
            ss << s[j];
        }
        ss >> x;

        REP(j, ss.str().size()+1, s.size()) {
            if(s[j] == '-' || s[j] == '+')
                break;
            ss2 << s[j];
        }
        ss2 >> y;

        REP(j, ss.str().size() + ss2.str().size() + 1, s.size())
            ss3 << s[j];
        if(!ss3.str().empty())
            ss3 >> z;

        double res = dt.calc(y, x, H - z);
        chmax(ans, res);
    }

    return ans;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

シンプルなDPでした。
DP部分より数値をパースする所の方が面倒です。