KUPC 2012 F - Acceleration of Network

• 問題
• AC

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

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

を繰り返すことになるが、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$みたいに展開してしまえば、二次関数の係数の増減だけでシミュレーションできるらしい。ぜんぜん持ってない考え方だった。

---

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