一日毎に復旧度をシミュレーションすればよさそう。タイプ$0, 1, 2$のサービスについて優先度付きキュー$Q_0, Q_1, Q_2$を用意しておいて、復旧したサービスは追加して、期限切れになったサービスは削除すればよい。全体の流れとしては
- 今日の復旧度を記録する
- $Q_0, Q_1, Q_2$から期限切れになったサービスを削除する
- 今日復旧したサービスを加える
- 復旧度を更新する
を繰り返すことになるが、4の更新の仕方が問題になる。タイプ毎にわけて考える:
タイプ$0$のサービス: 復旧度の増分は$Q_0$の長さに等しい。
タイプ$1$のサービス: 復旧度の増分が一日毎に$Q_1$の長さだけ増える。
タイプ$2$のサービス: 復旧度の増分の増分が一日毎に$Q_2$の長さ$\times 2$だけ増える。[1]
これらをそのままシミュレーションすればよい。
解説を読んだ。$(今日の日付-復旧した日付)^2$の式を$(t-s_i)^2 = t^2 -2s_it +s_i^2$みたいに展開してしまえば、二次関数の係数の増減だけでシミュレーションできるらしい。ぜんぜん持ってない考え方だった。
$x^2 - (x-1)^2 = 2x-1$だから、1つのサービス毎に、復旧度の増分の増分が2ずつ増えていく。 ↩︎
