AOJ 2237 The Castle

猫チャンの気持ちになることが何よりも大事です。

問題

The Castle | Aizu Online Judge

感想

制約が小さいのでDPいろいろできそうですよね。

何かを調べるとき、最初に探索できるかを考えるのも大事だなあと思ったり。それができなければ貪欲だとか、グラフに落としたりだとか？

ということで、これもDPですね。最近DPばかりやってる。メモ化再起ですが、ここら辺の区別わからないです。

持つ状態は

dp[i][j] := 猫の状態がi(bitで管理)でj人の敵を倒しているというもとで、敵を全員倒せる確率(条件付確率みたいな感じ)

行かせる猫の順番は割とどうでもよくって、どの子が残ってて、敵を何体倒せたがが大事。

ICPCの問題は遷移が単純ではないことが多い気がしますね、その状態でどのような遷移をするべきかをしっかりと整理することが大切そうです。(ICPCに限らないね)

今回は、各状態について各猫を行かせたときに敵を倒しきれる確率を計算して、最大を採用する。という感じ。

確率計算に後ろのdp情報を扱いたいので、条件付確率で情報を持っているんですね。

この類は割と得意らしい。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
int n,m;
double v[22][22];
double dp[1<<16][22];
 
double dfs(int state,int num){
     
    if(dp[state][num] != -1)return dp[state][num];
    double ret = 0;
     
    REP(i,n){
        if(!(state & (1<<i))){
            double tmp = 0;
            double p = 1;
            for(int k = num;k < m;k++){
                tmp += p * (1 - v[i][k]) * dfs(state|(1<<i),k);
                p *= v[i][k];
            }
            ret = max(ret,tmp+p);
        }
    }
             
    return dp[state][num] = ret;
}
 
int main(){
     
    cin >> n >> m;
     
    REP(i,1<<16)REP(j,22)dp[i][j] = -1;
         
    REP(i,n){
        REP(j,m){
            cin >> v[i][j];
        }
    }
     
    cout << Decimal << dfs(0,0) << endl;
     
    return 0;
}