ARC082 F: Sandglass

F - Sandglass

解き方

  • ある時刻におけるAの砂の量は、max(E1+C, min(E2+C, a+C))の形で表せる(aは最初にAに入っている砂の量)
  • r_iについて、E1, E2, Cを前計算しておき、クエリに対しては二分探索→最後だけ計算
    • r_{i-1}のときの関数が求まれば、そこからr_iのときの前計算ができる

ハマったところ

  • r_iについて、二分探索→最後だけ計算の流れはそうだろうと思ったが、関数の形に対して思いつかなかった
    • 場合分けもっと増えると思って前計算諦めたんだけど、もう少し真面目に考えれば思いついたのだろうか。

github.com