Typical DP Contest - J ボール

条件付き期待値による方程式を立ててとく問題。以下の記事が超わかりやすい。
//
// いつまでたってもボールがあたらない場合の計算式はどうなる？
// p*p*p*...
//
// => 条件付き期待値による方程式をたてて解く
//
// +-+
// | v
// [0] <=> [1] -> [2] -> ...
//  ^              |
//  +--------------+
//
// 状態遷移を考えて漸化式をたてる
//
//  E(0) = 1 + p0*E(0) + p1*E[1] + p2*E(2)
//
// mask := 物がたっている場所を表す bit 列
//
// Exp(mask) := mask にたっている物を倒すために必要なボールを投げるときの期待値
//
// とすると、x にむかって投げるとき
//
// Exp(mask) = Σ p(u) * Exp(mask & ~u) + (1- Σ p(u)) * Exp(mask) + 1
//            u in {x-1,x,x+1}               u in {x-1,x,x+1}       ~~~
//                                  mask から遷移しない確率    必ず 1 回は投げることになるので
//  p(u) : u のものにあたる確率
//
// Exp(mask) について解くと
//
//     Exp(mask) = (1 + Σ p(u) * Exp(mask ^ u)) / (Σ p(u))
//
// となる
//
class j_ball {
public:
    vector<double> memo_;
    double Exp(const int mask) {
        if (mask == 0) // すでに全て倒れている
            return 0.0;
        if (memo_[mask] >= 0.0)
            return memo_[mask];

        double res = (1<<30);

        // どの物をねらってボールをなげると最善かためす
        // !(y & mask) であってもボールがぶれることで最善になるケースがあるのでためす
        REP(x, 16)
        {
            double p = 0.0;
            double exp = 1.0;
            int y = (1<<x);

            int mask1 = mask & ~y;
            int mask2 = mask & ~(y<<1);
            int mask3 = mask & ~(y>>1);

            // 状態遷移するケースだけ加算
            if (mask != mask1) { exp += Exp(mask1)/3.0; p += 1.0/3.0; }
            if (mask != mask2) { exp += Exp(mask2)/3.0; p += 1.0/3.0; }
            if (mask != mask3) { exp += Exp(mask3)/3.0; p += 1.0/3.0; }

            // 最善なものを更新
            res = min(res, exp/p);
        }
        return (memo_[mask] = res);
    }
    void solve(void) {
        int N;
        cin>>N;
        memo_.resize((1<<16), -1.0);
        int mask = 0;
        // x が 0 <= x[i] <= 15 なので全ての位置を bit で表現できる
        REP(i, N)
        {
            int x;
            cin>>x;
            mask |= (1<<x);
        }
        // 出力精度が影響しないように、10桁くらい出力しておく
        cout<<setprecision(10)<<Exp(mask)<<endl;
    }
};