AOJ 2237 The Castle (JAG 夏合州 2010 day3-F) (500 点)

一目見て bitDP なのはわかるのだけど、手こずった......

問題へのリンク

問題概要

匹の猫をステージ に順番に送り込む

• 猫 がステージ をクリアできる確率は
• 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない
• 猫 があるステージをクリアできなかったら、もうその猫は使えない
  • そのときは別の猫を送り込むことができる

状況に応じて適切に挑ませる猫を選択していくことで、ステージ まで全クリできる確率を最大にせよ。

制約

• 

考えたこと

意外と詰め切るのが大変だった...

猫を送り込む順序を最適化する問題 (厳密にはクリア状況によって最適順序が動的に変わるが...)。いかにも bitDP っぽい。制約から見て、 とかは間に合わないけど なら間に合う。

なかなか DP が上手く組めなかったが最終的には

---

dp[ S ][ r ] := 残った使える猫の集合が S (他の猫はすべて敗北済) で、残りステージ数は r という状況で、そこから全クリできる確率

---

としたら上手く行った。DP 更新順序など、頭がごっちゃになったので、メモ化再帰で頑張った。理由はよくわからないけど、この手の戦略 DP は後ろから引っ張って来るように設計するのが見通しいいみたい。うーむ...。

dp[ S ][ r ] を考える際に、

• どの猫を使うのがよいのかを場合分けして、その時点で送り込むのによい猫を求める
• 各猫 について、残りステージ 個のうち、どこで敗退するのかを場合分けして合算する

という風にした。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
using namespace std;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else return false; }

int m, stage;
vector<vector<double> > p;

double dp[(1<<16)+10][20]; // remained member, #. of remained stages
double rec(int bit, int rem) {
    if (dp[bit][rem] >= -1e-10) return dp[bit][rem];
    if (rem == 0) return 1.0;
    
    double res = 0.0;
    int start = stage - rem;
    for (int i = 0; i < m; ++i) {
        if (!(bit & (1<<i))) continue;
        int nbit = bit & ~(1<<i);
        double tmp = 0.0;
        double prob = 1.0;
        for (int lose = start; lose < stage; ++lose) {
            double loseprob = prob * (1.0 - p[i][lose]);
            tmp += loseprob * rec(nbit, stage - lose);
            prob *= p[i][lose];
        }
        tmp += prob * rec(nbit, 0);
        chmax(res, tmp);
    }
    return dp[bit][rem] = res;
}

int main() {
    while (cin >> m >> stage) {
        p.assign(m, vector<double>(stage, 0.0));
        for (int i = 0; i < m; ++i) for (int j = 0; j < stage; ++j) cin >> p[i][j];

        memset(dp, -1, sizeof(dp));
        cout << fixed << setprecision(10) << rec((1<<m)-1, stage) << endl;
    }
}