戻す DP シリーズのトレーニング
問題概要 (入力形式は多少改変)
正の整数 と、 個の正の整数 が与えられる。これらをランダムシャッフルする。
を満たす最小の を考える。この値の期待値を求めよ (要求精度は )。
制約
考えたこと
各要素 に対して、それが再生される確率を求めて合計していけばよい。
大まかな方針として、 の前に 個の要素が来る場合について までの総和が 以下となる確率を求めることにする。この値を各 に対して合計して で割ればよい。 の前にくる 個の選び方は、 通りある。そのうちの何通りについて、総和が 以下となるかを考えよう。これは 個の要素についての部分和 DP をすることで求められる。
- dp[ i ][ j ][ k ] := 個の要素のうちの最初の i 個について、そのうちの j 個を選ぶ場合であって、総和が k となるものが何個あるか
さて、このままでは、各 に対して、 個の要素のついての部分和問題を解くため、 となってしまう。計算量的に厳しい。
戻す DP
各 に対して、 個の要素から 番目を除いた 個の要素についての解を得る方法として、「戻す DP」が有効。dp 遷移と、逆変換を考える。
dp 配列に値 v を追加するとき
配列 dp から配列 ndp への遷移は次のようになる
ndp[ j ][ k ] = dp[ j ][ k ] + dp[ j - 1 ][ k - v ]
その逆変換
dp[ j ][ k ] = ndp[ j ][ k ] - dp[ j - 1 ][ k - v ]
以上によって、計算量は に改善できる。
コード
#include <bits/stdc++.h> using namespace std; vector<vector<long long>> add(vector<vector<long long>> dp, int v) { auto res = dp; for (int j = 1; j < res.size(); ++j) { for (int k = v; k < res[0].size(); ++k) { res[j][k] += dp[j-1][k-v]; } } return res; } vector<vector<long long>> sub(vector<vector<long long>> dp, int v) { auto res = dp; for (int j = 1; j < res.size(); ++j) { for (int k = v; k < res[0].size(); ++k) { res[j][k] -= res[j-1][k-v]; } } return res; } double com(int n, int r) { double res = 1; for (int i = 0; i < r; ++i) { res *= (n-i); res /= (i+1); } return res; } int main() { int N, L; cin >> N >> L; L *= 60; vector<int> S(N); for (int i = 0; i < N; ++i) { string str; cin >> str; int m = (str[0]-'0')*10 + (str[1]-'0'); int s = (str[3]-'0')*10 + (str[4]-'0'); S[i] = m*60+s; } double res = 0; vector<vector<long long>> dp(N+1, vector<long long>(L+1, 0)); dp[0][0] = 1; for (int i = 0; i < N; ++i) dp = add(dp, S[i]); for (int i = 0; i < N; ++i) { double tmp = 0; auto sdp = sub(dp, S[i]); for (int k = 0; k < N; ++k) { double num = 0; for (int j = 0; j <= L-1; ++j) num += sdp[k][j]; tmp += num / com(N-1, k); } res += tmp / N; } cout << fixed << setprecision(10) << res << endl; }