7K12 blog

猫でも分かるアルゴリズム解説

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)で求まる。

同値なRiがあるので、maxはupper_bound(all(R), R[i] + D);から-1したインデックスとすれば実装が楽になる。