2011 TCO Algorithm Qualification Round 1 medium

問題概要

n曲のリストが与えられる。
曲によって長さが違う。
聞く曲を選ぶときランダムに選ぶ。
t分きいたときに、どの曲をどのくらいの確率で聞いてるか返せ。

解法

DP
最初はn * n * tのアプローチでdpした。
つまり、t分にi番目の曲を聞いてる確率を状態にして、
そこからそれぞれすべての曲に対してどの曲を選ぶか等間隔にしていった。
でも、TLE
じつはn*tにすることができる。
どの曲が終わって選んでも、曲を選ぶ確率は等しいので、
その単位時間に曲が終わる確率を全ての曲に対して合計してやって、
そこから曲に振り分けていけばおk

ソース

#include<vector>
#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
using namespace std;
const int T = 80010;
class FoxListeningToMusic{
public:
  vector <double> getProbabilities(vector <int> length, int t){
    int n = length.size();
    vector<double> ret(n, 0.0);
    double sum[T];
    rep(i, T)sum[i] = 0;
    sum[0] = 1;
    rep(i, t+1){
      double nowP = sum[i] / (double)n; 
      rep(j, n){
        int nextT = i + length[j];
        if(nextT > t) ret[j] += nowP;
        else sum[nextT] += nowP;
      }
    }
    return ret;
  }
};