2020年2月24日月曜日

KUPC 2012 F - Acceleration of Network

KUPC 2012 F - Acceleration of Network

一日毎に復旧度をシミュレーションすればよさそう。タイプ0,1,20, 1, 2のサービスについて優先度付きキューQ0,Q1,Q2Q_0, Q_1, Q_2を用意しておいて、復旧したサービスは追加して、期限切れになったサービスは削除すればよい。全体の流れとしては

  1. 今日の復旧度を記録する
  2. Q0,Q1,Q2Q_0, Q_1, Q_2から期限切れになったサービスを削除する
  3. 今日復旧したサービスを加える
  4. 復旧度を更新する

を繰り返すことになるが、4の更新の仕方が問題になる。タイプ毎にわけて考える:

タイプ00のサービス: 復旧度の増分はQ0Q_0の長さに等しい。
タイプ11のサービス: 復旧度の増分が一日毎にQ1Q_1の長さだけ増える。
タイプ22のサービス: 復旧度の増分の増分が一日毎にQ2Q_2の長さ×2\times 2だけ増える。1

これらをそのままシミュレーションすればよい。


解説を読んだ。()2(今日の日付-復旧した日付)^2の式を(tsi)2=t22sit+si2(t-s_i)^2 = t^2 -2s_it +s_i^2みたいに展開してしまえば、二次関数の係数の増減だけでシミュレーションできるらしい。ぜんぜん持ってない考え方だった。


  1. x2(x1)2=2x1x^2 - (x-1)^2 = 2x-1だから、1つのサービス毎に、復旧度の増分の増分が2ずつ増えていく。 ↩︎