CPSCO2019 Session4 C - Make a Team

f:id:tkr987:20200621173512p:plain

https://atcoder.jp/contests/cpsco2019-s4/submissions/13596303

チーム内の最小を決め打ちすると[最小, 最大]の範囲が $10^5$ 通りある
あとは $10^5$ 通りの上記範囲に対してnCrを考えれば答え

f:id:tkr987:20200621173921p:plain

チーム内の $min=R_i$ を決め打ちすると $max=min+D$ も決まり、[min, max]の範囲が $10^5$ 通りあると気づける。[min+1, max]の範囲kから2人選ぶ（1人目は必ずminを選ぶとするので残り2人を選ぶ）のは $_kC_2$ で $O(1)$ なので、それら全ての合計は計算量 $O(N)$ で求まる。