PAST5O

https://gyazo.com/9d380fa7f1c141460e331b7a7e7f8144

初回考察

プッシュでもプルでも最悪10^5になるので10^5回のクエリでは破綻する

(補足: 通知発生時に受領者の値を変更する「プッシュ」の場合、フレンドの10^5人いる人が通知を10^5回送るとダメ。逆に通知確認の時にフレンドの誰が送ったか確認しにいく「プル」の場合はフレンドの多い人が通知確認をしまくるとダメ)

フレンドがルートN以上の人の処理だけ遅延させる

こういう人は高々ルートN人

通知確認時にこれらの人xだけプルする

xの発生させた総通知数をxが持つ

yがxから受信した総数をyが持つ。高々ルートN

この二つを引けばxからの新しい通知の数がわかる

考察完了

公式解説