TopCoder SRM 515 Div1 Medium: NewItemShop

解法

動的計画法(メモ化再帰)する。

2回以上来る顧客をbitで管理しておく。
各タイミングの各bitにおいて、「来ない時」「来たから売る時」「来たけど売らない時」をそれぞれの計算して期待値を出せばいい。

重要な式はこんな感じ。

double sell = dfs(time + 1, sword - 1, nextBit) + gain;// 来たので売った
double ignore = dfs(time + 1, sword, nextBit);// 来たけどスルーした
double notcome = dfs(time + 1, sword, bit);// 来なかった

// pは来る確率
dp[time][sword][bit] = Math.max(sell, ignore) * p + notcome * (1.0 - p);

ここでi回目のタイミングで来る確率pは、「i-1回目までは来ないで、i回目に来る」という条件付き確率なので、以下のようになる。

 p = P_{i}/(100 - P_{0} - P_{1} - ... - P_{i-1})

コード

public class NewItemShop {
	private double[][][] dp;
	private Customer[] customers;

	public double getMaximum(int swords, String[] c) {
		int N = c.length;
		customers = new Customer[N];
		for (int i = 0; i < N; i++) {
			customers[i] = new Customer(c[i]);
		}

		// 複数回くる客の数
		int moreComes = 0;
		for (int i = 0; i < N; i++) {
			if (customers[i].size() > 1) {
				moreComes++;
			}
		}

		// 微妙な座標圧縮
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (customers[i].size() > 1) {
				customers[i].moreComeID = cnt;
				cnt++;
			}
		}

		dp = new double[24][swords + 1][1 << moreComes];
		return dfs(0, swords, 0);
	}

	private double dfs(int time, int sword, int bit) {
		if (sword <= 0 || time >= 24) {
			return 0.0;
		}
		if (dp[time][sword][bit] > 0) {
			return dp[time][sword][bit];
		}

		// timeにくる顧客がいるかどうかを調べる
		Customer coming = null;
		for (int i = 0; i < customers.length; i++) {
			if (customers[i].comeAt(time)) {
				if (customers[i].size() == 1) {
					// 1回しか来ない顧客なら
					coming = customers[i];
					break;
				}
				// 2回以上来る顧客ならまだ来ていないかどうかチェックする
				int id = customers[i].moreComeID;
				if (((bit >> id) & 1) == 0) {
					coming = customers[i];
					break;
				}
			}
		}

		// timeに来る顧客がいなければ何もせずに経過
		if (coming == null) {
			dp[time][sword][bit] = dfs(time + 1, sword, bit);
			return dp[time][sword][bit];
		}

		// 1回しか来ない顧客ならbitは操作しなくていい
		if (coming.size() == 1) {
			double p = (double) coming.probability[0] / 100;
			double sell = dfs(time + 1, sword - 1, bit) + coming.gain[0];
			double ignore = dfs(time + 1, sword, bit);
			dp[time][sword][bit] = Math.max(sell, ignore) * p + ignore
					* (1.0 - p);
			return dp[time][sword][bit];
		}

		// 2回以上来る顧客はbit操作が要る
		double p = 0.0;// timeに来る確率
		double gain = 0.0;// 売った場合に得られる利益
		double prev = 0;
		for (int i = 0; i < coming.size(); i++) {
			if (time > coming.time[i]) {
				// timeより以前に来る確率を出しておく
				prev += coming.probability[i];
			} else if (time == coming.time[i]) {
				p = (double) coming.probability[i];
				gain = coming.gain[i];
			}
		}
		p /= (100 - prev);// 条件付き確率を計算する

		// 新しいbitを発行する
		int id = coming.moreComeID;
		int nextBit = bit | (1 << id);

		// 各選択肢を計算する
		double sell = dfs(time + 1, sword - 1, nextBit) + gain;// 来たので売った
		double ignore = dfs(time + 1, sword, nextBit);// 来たけどスルーした
		double notcome = dfs(time + 1, sword, bit);// 来なかった

		dp[time][sword][bit] = Math.max(sell, ignore) * p + notcome * (1.0 - p);
		return dp[time][sword][bit];

	}
}

class Customer {
	int[] time;
	int[] gain;
	int[] probability;
	int moreComeID = -1;// 何回か来る人だけのIDを設定しておく

	public Customer(String s) {
		String[] strings = s.split(" ");
		int num = strings.length;
		time = new int[num];
		gain = new int[num];
		probability = new int[num];

		for (int i = 0; i < num; i++) {
			String[] coming = strings[i].split(",");
			time[i] = Integer.parseInt(coming[0]);
			gain[i] = Integer.parseInt(coming[1]);
			probability[i] = Integer.parseInt(coming[2]);
		}
	}

	public int size() {
		return time != null ? time.length : 0;
	}

	public boolean comeAt(int t) {
		for (int i = 0; i < time.length; i++) {
			if (time[i] == t) {
				return true;
			}
		}
		return false;
	}
}