ABC074 C - Sugar Water
解法
全探索が間に合わないので、ある1箇所だけを探索せずに計算でぱっと求めるパターンです。
操作1~3を探索し、操作4はある1~3のパターンに対する最善手を計算によって求めます。
操作1をx回、2をy回、3をz回行ったとします。
このとき、水は100(ax+by) [g]、砂糖は cz [g]存在しています。これをそれぞれw [g]、s [g]とします。
そして、この場合の操作4を行うべき回数pは、
min(f-w-s,ew/100-s) / d 回
となります。
min()の左側が、合計質量の残りグラム数、現在の水にたいして溶かすことのできる砂糖の量です。
この中の小さい値を超えないギリギリまで、操作4を行うのが正解なので、上のような式になります。
あとは、濃度が100(s+pd)/(w+s+pd)によって求められるので、(x,y,z)について全探索を行い、濃度が最大になるようなパターンを探します。
コーナーケースが存在します。濃度が0%になるのは、砂糖が0[g]の”水”に対してです。水と砂糖どちらも存在しない場合は、そもそも濃度が定義できないので、あやまって出力しないようにしましょう。このケースに気づかず時間を溶かしました。
