SRM642 div1 easy WaitingForBus

考えたこと

• 期待値と言われたので線形性を考えるとn回バスが到着するまでの時間の期待値は求まる気持ちになる
• 何回目のバスに乗ることになるかがわからないので上のが求まったとしてもよくわからない気がする
• i回目のバスでsに達しておらずi+1回目のバスでsを超えるようなバスについて考えたい
• dp[i][j] = (i回目に到着したバスで時刻jに到着する確率) としたDPをできれば求められる気がした
• バスの到着は最悪10^5回、時刻は最大10^5なので状態が10^10、さらに遷移がO(n)かかるので不可能
• 線形性を使って遷移を高速化とかを考えるけど何も思いつかない
  --------解説を見た--------
• 時刻t_1,t_2(t_1<t_2)についてt_2にバスが到着した確率がt_1に到着する確率に影響することはない
• 何回目かの情報を持たなくてよいので dp[j] = (時刻jに到着する確率) と状態を持てばよい
• dp[j] -> dp[j+time[k]] に配るDPをすればよい
• バスの到着回数ごとにDPを回す必要がないので状態数O(s)、遷移O(n)の合計O(ns)で解ける

学び

• ナップザックを逆向きに回すと次元が1つ落とせるみたいな感じで条件から時間計算量の次元を一つ落とせるときがある

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

double dp[100010];
class WaitingForBus {
   public:
   double whenWillBusArrive(vector <int> t, vector <int> prob, int s)
  {
    memset(dp, 0, sizeof(dp));
    int n = t.size();
    if(s == 0) return 0;

    dp[0] = 1;
    REP(i, s+1) REP(j, n) {
      if(i+t[j] < s) dp[i+t[j]] += dp[i]*prob[j]/100;
    }

    double ret = 0;
    REP(i, s+1) REP(j, n) {
      if(i+t[j] >= s) ret += (i+t[j]-s)*dp[i]*prob[j]/100;
    }
    return ret;
  }
};