問題概要
Joseph の住む町のバスターミナルは確率的に営業される．
バスターミナルの開業前，バスターミナルには 台のバスが待機していて，各バスは
で番号付けられる．また，各バスは 2 つの属性
と
をもつ．
その日の運行を始めるときを時刻 0 とする．バスの運行は，まず時刻 0 に於いて，最初に出発するバスがランダムに決定される．このとき，バス が選ばれる確率は
[%] である．バスの決定と同時にバスは出発し，バス
は出発後，
の時間をかけてルートを回り，バスターミナルに戻ってくる．
バスが戻ってきてバスターミナルにいるバスが 台になった瞬間，始業時と同様にランダムに次に出発するバスが選ばれる．同時に，同様に所定の時間をかけてルートを回ってから戻ってくる．
Joseph は時刻 にバスターミナルに到着する．このとき，次のバスが出発するまでの時間の期待値を求めよ．
解法
期待値の計算は，事象の発生確率と，そのときの値の積の和です．従って，バスの待ち時間の期待値を求めるためには， からの経過時間と，その時刻にバスが出発する確率を求める必要があります．時刻が分かれば経過時間は単純な引き算で計算できるため，求めなけばならないのは，各時刻についてそのときにバスが出発する確率です．
さて，時刻 にバスが出発する（＝前のバスが戻ってくる）確率はどのように計算されるか考えていきます．これは，前のバスが時刻
に戻ってくるタイミングで出発している確率と，その（前のバスの）出発時刻にバスが到着する確率の積の和になります．すなわち，
です．これを適当に計算すればよいのですが，何も考えずに再帰関数を書くと分岐が多いので TLE します．
ところで，任意の に対し，
の値は一定です．従って，一度計算した
の値を保存しておくことで高速化できる筈です．すなわち，次のような動的計画法を考えます．
- dp[ t ] := 時刻
にバスが出発する確率
を計算するときに必要な値に於ける
の添字が常に
より小さいことを考えると，単純に
を昇順にループさせることで値を計算していくことができます．dp[ t ] からの遷移は，その時刻に発生する可能性を全て試す必要があるので，
- dp[ t + time[ i ] ] += dp[ t ] * prob[ i ] / 100.0
という更新を全ての について行うことになります．また，
になったら更新を止めることで，
以降の時刻については「
以降初めてバスが出発する確率」を求めることができます．
この計算が終わったら， 以上の
について，dp[ t ] * ( t - s ) の和を求めることで答えを計算できます．
さて， の範囲については敢えて触れないように書いてきましたが，計算しなければならない
の範囲はきちんと求められます．
以降の時刻については初めてバスが到着する確率を求めていることを考えると，
以降のバスの出発を考慮する必要はありません．つまり，考慮しなければならないのは時刻
以前に出発するバスだけです．
に関する制約を考えると，最大でも
程度まで求めておけば，考慮しなければならないバスの到着を全てカバーできます．また，DP の実行が
時間で完了することも分かります．
コード
template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define ALL( c ) ( c ).begin(), ( c ).end() class WaitingForBus { public: double whenWillBusArrive( vector <int> time, vector <int> prob, int s ) { const int N = time.size(); VT< double > ps; transform( ALL( prob ), back_inserter( ps ), bind( divides< double >(), _1, 100 ) ); VT< double > dp( s + 100000 + 5 ); dp[0] = 1; REP( t, 0, s ) { REP( i, 0, N ) { dp[ t + time[i] ] += dp[t] * ps[i]; } } double res = 0; REP( t, s, dp.size() ) { res += ( t - s ) * dp[t]; } return res; } };
