Coffee and Coursework D1, D2 ☕

Quiz

Submit

解法

  • d日で解けるかを二分探索
  • カフェイン列は大きい順にソートしておき、各日の早いうちに飲む
    • 同じ日の中で後に飲んだカフェインの「効きが弱くなる」
    • 強いカフェインを1日の後半で飲むと減衰の影響を受けてしまう
    • 一方、弱いカフェインを後半で飲むとmax(A[i], 0) なので減衰の影響を受けないため

その他

  • d日に分割したときの「効く」総カフェイン量、累積和とかで高速化が必要と思っていたけれど不要だった
  • 二分探索しているので総計算量がO(N logN)のため

レート

  • 少し下がって1400ちょい
  • コンテスト内に解けるべき問題だった