Algoogle

Algorithm for Programming Contest

AOJ 2294 Entangled with Lottery

Category: AOJ Tag: dp, probability

Entangled with Lottery

問題概要


高さHのN本の縦棒からなるあみだくじがある.1以上H以下の整数の高さにそれぞれ1本まで隣り合った縦棒をつなぐ横棒を置ける.
現在M本の横棒が置かれている.ここにさらに上記の条件を満たすようにランダムにK本の横棒を置く.
左からP本目の下端が当たりの時,最も当たる確率が高くなるようにスタートを選んだ時の当たる確率を求めよ.

解法


ある開始位置を決めた時,下端の各位置にたどり着く確率は以下のDPでもとまる.
dp[i][k][j] := 高さiでこれまでにk本設置して,左からj番目にいるときの確率
更新は,すでにその高さに横棒があるなら対応する位置の確率をswap.
そうでないなら,それ以降でその高さが選ばれる確率は (K-k)/(残りの設置されてない高さの数).
その高さで各位置に設置される確率はさらに 1/(N-1)
よってこの2通り*2通りの遷移をすればよい.
このDPの計算量はO(NHK)

どの開始位置がPにたどり着く最大の確率を取るかすべて試すのはちょっと危うそう(メモ化再帰とか定数倍高速化を頑張ればいける?).
あみだくじの性質として,上から下へ辿る時の経路と下から上への経路は同じ.
つまりあみだくじをひっくり返して下端のPから上端の各位置への到達確率のうち最大のものを持って来ればよい.

コード


(2294.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

int h, n, p, m, K;
int bar[512], res[512];
double dp[2][128][128];

double solve()
{
        res[0] = h-m;
        for (int i = 0; i < h; i++) res[i+1] = res[i]-!bar[i];
        const double qr = 1./(n-1);

        dp[0][0][p] = 1;
        for (int i = 0; i < h; i++) {
                if(bar[i]) {
                        for (int k = 0; k < K+1; k++) swap(dp[0][k][bar[i]-1], dp[0][k][bar[i]]);
                        continue;
                }
                memset(dp[1],0,sizeof(dp[1]));
                for (int k = 0; k < K+1; k++) {
                        const double pr = 1.*(K-k)/res[i];
                        for (int j = 0; j < n; j++) {
                                double r = 1., x = dp[0][k][j];
                                if(j) dp[1][k+1][j-1] += x*pr*qr, r -= qr;
                                if(j < n-1) dp[1][k+1][j+1] += x*pr*qr, r -= qr;
                                dp[1][k+1][j] += x*pr*r;
                                dp[1][k][j] += x*(1-pr);
                        }
                }
                swap(dp[0], dp[1]);
        }
        return *max_element(dp[0][K], dp[0][K]+n);
}

void input()
{
        cin >> h >> n >> p >> m >> K; p--;
        for (int i = 0; i < m; i++) {
                int a, b; cin >> a >> b;
                bar[h-a] = b;
        }
}

int main()
{
        input();
        cout << fixed << setprecision(12) << solve() << endl;
        return 0;
}

Comments