AtCoder Beginner Contest 034 D : 食塩水
当初の方針
DP? でもwが大きいし・・・。
分からない。
解説を読んで
二分探索。なるほど。その通りに実装してAC。
Submission #935434 - AtCoder Beginner Contest 034 | AtCoder
でも、なんでそれが正しいか分からない。
なぜ基準を決めると優先順位が決まるのか。
図にしてみた。
なんとなくわかった。
そして、目標のパーセンテージによって、
余る/足りない食塩の大小関係も変わるので
(例:25%目標だとA:-10,B:-15,C:10余ることになる)、
これでいい。
二分探索で、
(true, true, ..., true, false, false, ..., false)
↑の一番最後のtrue(目標を達成できる)の場所を知りたい。
ううーん、一から自分で考えられる気がしないな・・・。
算数が苦手。