Livedoorブログからの移動
はてなブログからの移動

C - Sugar Water

解き方

  • A, B, C, Dそれぞれの操作を何回するか、全探索
    • A, Bについては、100A <= F <= 30 * 100より、たかだか30回
    • C, Dについては、最大でF/2g溶ける（E=100の時）ので、たかだか1500回
  • 合計で[tex:O(109)]なので、ダメでは？という気もするが、間に合った
    • 水のありうる量を列挙、砂糖のありうる量を列挙し、各水の量について、最大の砂糖の量を二分探索、とすると、O(1500^2+30^2*log(1500^2))となって十分間に合う感じになりそう

ハマったところ

  • 濃度の比較を整数で行おうとした時、\frac{a_1}{a_1+b_1} > \frac{a_2}{a_2+b_2}の式変形で、a_1(a_1+b_1)(a_2+b_2) > a_2(a_1+b_1)(a_2+b_2)としていてWA

github.com