SRM 384 500pt: SchoolTrip

TopCoder

問題概要

人がN(<=6)人いる。0番目の人から順に、誰か一人を選んでボールをぶつけようとする。各人がボールをぶつけられる確率はP[i](0.1<=P[i]<=1.0)である。ボールをぶつけられた人は退場する。これを最後の一人になるまで繰り返す。ゲーム終了までのターン数の期待値を最小化するように各人が振る舞うとき、ゲーム終了までのターン数の期待値を求める問題。

考えたこと

  • ビットDP臭。でもそれにしても6は小さい気がする。
  • 最も単純に状態を表すと、(残ってるメンバー、今誰のターンか)で6*2^6通り。
  • この状態遷移はDAGになってないからDPやメモ化再帰だと素直にかけない。
  • ならば連立方程式か。
  • これだと計算量的にも(6*2^6)^3となって何かいい感じになる。
  • 係数行列をどうつくるかが問題だけど、一番当てる能力が低いやつを選べば良いだろう。
  • 書けた。一発コンパイルでサンプル通っていい感じ。提出したら落ちた。あれ？
  • あー、一番当てる能力が低いやつを選ぶっていうのは怪しいな。
  • でも誰に当てるかが固定できないと係数行列が作れない。連立方程式案はちょっと捨てよう。
  • じゃあ、この手の問題の嘘解法として常套手段の「深さ付けて適当なところで打ち切りDP」を実装しよう。
    • この手の解法に適切なネーミングが欲しい。
  • よく考えたら条件の確率に下限がついてるのも好都合だ。
    • 状態が変わらない確率は最大0.9で、例えば1000ターン後も誰も倒れていない確率は0.9^1000=1.74*10^-46とかで無視できるようになる。
  • 計算量やメモリ使用量、スタックオーバーフローの可能性を考えると深さ1000位までいける。
  • この手のやつをメモ化再帰で書くと大抵スタックの消費量が増える。なのでローカル変数を増やさないように注意する。
    • ちなみにDPで書くと配列の再利用ができて空間計算量が落とせる。
  • 書いた。無事通った。

practiceで通ったコード

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int INF = 1<<29;
const int MAX_N = 6;
const int MAX_DEPTH = 1000;

int N;
double prob[MAX_N];
double memo[MAX_DEPTH][(1<<MAX_N)][MAX_N];
bool visited[MAX_DEPTH][(1<<MAX_N)][MAX_N];

struct SchoolTrip {

	double duration(vector <int> probability) {
		N = probability.size();

		//doubleに変換
		for(int i=0; i<N; i++){
			prob[i] = (double)probability[i]/100.0;
		}

		return rec(0, (1<<N)-1, 0);
	}

	double rec(int depth, int bit, int turn){
		//基底
		if(depth == MAX_DEPTH){
			return 0.0;
		}

		//メモ化処理など
		if(visited[depth][bit][turn]){
			return memo[depth][bit][turn];
		}
		visited[depth][bit][turn] = true;

		//基底(もう終わってる)
		if(__builtin_popcount(bit) <= 1){
			return 0.0;
		}

		double& ret = memo[depth][bit][turn];
		ret = 1e100;

		//パス
		if( !((bit>>turn)&1) ){
			turn++;
			if(turn == N){
				turn = 0;
				depth++;
			}
			return ret = rec(depth, bit, turn);
		}

		for(int target=0; target<N; target++)if( turn != target && ((bit>>target)&1) ){
			ret = min(ret, prob[turn] * (1.0 + rec(depth+(turn==N-1?1:0), bit&(~(1<<target)), turn<N-1?turn+1:0) ) +
						(1.0 - prob[turn]) * (1.0 + rec(depth+(turn==N-1?1:0), bit, turn<N-1?turn+1:0) ));
		}

		return ret;
	}

};