yukicoder No.1043 直列大学

電圧の総和を V _ {sum},抵抗の総和を R _ {sum}とすると、

 A \leq \dfrac{V _ {sum}}{R _ {sum}} \leq B

 A R _ {sum} \leq V _ {sum} \leq B R _ {sum}

となるので、 R _ {sum} を固定したときの  V _ {sum}の範囲は区間になっている!!!

ということで予め前処理として、各 R _ {sum} V _ {sum}がそれぞれ何通りあるかをナップサックDPで求めて、 V _ {sum}については累積和まで求めておくことで、 R _ {sum}を固定したときに、条件を満たす V _  {sum} O(1)で何通りあるかを求めることができる。

よって解けました!!

提出コード

yukicoder.me

まとめ

 B未満だと思ってて、サンプル合わねーとかいってた。

ABC - Dもこれぐらい骨があるやつがいいね