SRM 460 500pt: TheFansAndMeetingsDivOne

TopCoder

問題概要

JohnとBrusは、それぞれN(<40)個ある街の内丁度K(

考えたこと

  • JohnとBrus別々に考えて最後にまとめる方針が見えるけど、SRMの問題としてはそういうのは珍しい気がする。
  • しかしSRM的云々は置いておくとしてもこれ完全に問題分離できそう。
  • 状態を(何番目の街か、既にいくつ訪ねたか、何人に会ったか)で状態数40^4通り。配るのに必要なのは各状態につきmaxJ[i]-minJ[i]。全体で計算量O(40^5)で間に合いそう。
  • あとはやるだけだけど、Johnの作業とBrusの作業はまったく同じなので関数にする。
  • 街を訪ねるかどうかの確率が条件つき確率っぽくなってちょっと自信ない。
  • 今回は計算量厳しめなので念のためif(dp[i][j][a] > EPS)みたいな枝刈りを入れる。
    • これを入れないと非正規化数が出てきてTLEする恐れが出てくる。今回は大丈夫だろうけど。
  • 書けた。一発コンパイルでちゃんと通った。

practiceで通ったコード

計算量O(K*N^2*MAX_P^2)。

#include <vector>
using namespace std;

const int MAX_N = 42;
const int MAX_P = 42;
const double EPS = 1e-12;

double dpJ[MAX_N+1][MAX_N + 1][MAX_N * MAX_P + 1];
double dpB[MAX_N+1][MAX_N + 1][MAX_N * MAX_P + 1];


struct TheFansAndMeetingsDivOne {

	double find(vector <int> minJ, vector <int> maxJ, vector <int> minB, vector <int> maxB, int k) {
		const int N = maxJ.size();

		//それぞれ確率を求める。
		solve(minJ, maxJ, k, dpJ);
		solve(minB, maxB, k, dpB);

		double ret = 0.0;
		for(int i=0; i<=MAX_N * MAX_P; i++){
			ret += dpJ[N][k][i] * dpB[N][k][i];
		}
		return ret;
	}

	void solve(const vector<int>& mins, const vector<int>& maxs, int K, double dp[MAX_N + 1][MAX_N + 1][MAX_N * MAX_P + 1]){
		const int N = mins.size();

		//DP (i番目の街、既に訪れた数、何人訪れたか
		dp[0][0][0] = 1.0;
		for(int i=0; i<N; i++){
			for(int j=0; j<=K; j++){
				for(int a=0; a<=MAX_N*MAX_P; a++)if(dp[i][j][a] > EPS){
					double prob_city = (double)(K - j)/(N - i);

					//i番目の街を尋ねる
					if(j<K)for(int p=mins[i]; p<=maxs[i]; p++){
						dp[i+1][j+1][a+p] += prob_city / (double)(maxs[i] - mins[i] + 1) * dp[i][j][a];
					}

					//i番目の街を訪ねない
					dp[i+1][j][a] += (1.0 - prob_city) * dp[i][j][a];
				}
			}
		}
	}
};