SRM 466 500pt: LotteryPyaterochka

問題概要

N*5(N<100)のマスがある。このうち5個のマスを無作為に選んでオープンにする。3マス以上オープンになっている行が存在する確率を求める問題。

考えたこと

• (初めて通したMedium。当時は高校数学っぽくO(1)解で通した)
• 前回通したときは組み合わせっぽく解いたので今回はDPで解くことにする。
• 識別できる状態がそんなに多くないのでvectorをキーにしたメモ化再帰で書くのが楽そう。
• 状態を(i個オープンになっている行はそれぞれj個ずつある)とすればよさげ。
• 再帰関数の引数を参照にしたのは余計なミスを生む可能性があったので値コピーにすべきだったと反省。もともとconstにしてたのを外したのが原因なんだけど。

practiceで通ったコード

#include <map>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int N;
map< vector<int>, double > memo;

struct LotteryPyaterochka {

	double chanceToWin(int N_) {
		N = N_;
		vector<int> start(6, 0);
		start[0] = N;
		return rec(start);
	}

	double rec(vector<int>& cnts){
		//メモ化処理
		if(memo.find(cnts) != memo.end()){
			return memo[cnts];
		}

		double& ret = memo[cnts];

		//既に何枚開いたか
		int already_open =  0;
		for(int i=0; i<=5; i++){
			already_open += i * cnts[i];
		}

		//基底：もう全部開いた
		if(already_open == 5){
			return ret = (cnts[3] > 0 || cnts[4] > 0 || cnts[5] > 0 ? 1.0 : 0.0);
		}

		//未オープンなマスの個数
		int total = 5*N - already_open;

		for(int i=0; i<=4; i++){
			double prob = (double)cnts[i] * (5 - i) / total;
			cnts[i]--;
			cnts[i+1]++;
			ret += prob * rec(cnts);
			cnts[i]++;
			cnts[i+1]--;
		}

		return ret;
	}

};