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回目に来る」という条件付き確率なので、以下のようになる。
コード
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; } }