オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 034 D: 食塩水

ABC埋め続き。

 

問題文

abc034.contest.atcoder.jp

解法

貪欲に混ぜるとダメ。

水:食塩の比率が同じ2つの食塩があるときは、水が少ないほうを優先的に入れたほうが、全体の濃度を薄める効果が小さい(=最終的な濃度を大きくできる)。みたいに考えていると、瞬間を見ながら解を求めるのではなく、全体(目指すべき濃度)を見て、ある食塩水がその結果に及ぼす影響を考えればよさそうという気持ちになる。

食塩水 i を構成する水量を $w_i$、食塩量を $q_i$ として、目指すべき濃度を総水量 $W$ と総食塩量 $Q$ を使って $\frac{Q}{W}$ と表すことにする。この時、食塩水 i が全体に及ぼす影響 $e_i$ は、

$$e_i = q_i - \frac{Q}{W} * w_i$$

  • $e_i < 0$ のとき、濃度を下げる
  • $e_i = 0$ のとき、濃度を変化させない
  • $e_i > 0$ のとき、濃度を上げる

となる。式の意味がわからなかったら $q_i - \frac{Q}{W} * w_i = 0$ の式を整理するとなんとなくわかるかもしれない。

今回はできるだけ濃くしたいので、目指すべき濃度より高くなるように食塩水を選んでいく。濃度 $X$ より高い食塩水が作れるなら、同じ作り方で濃度 $X-1$ より高い食塩水が作れるわけだから、目指すべき濃度の設定には二分探索が使える。

 

余談

昨日から思ってたけど、日本語が不自由だ。