ABC 401-500/ABC441C - Sake or Water - 競技プログラミング用 知識集積所

---

問題

ABC441C

必要知識

B以下レベルの内容は省略

• 考察問題
• 貪欲法（アルゴリズム系）※

考え方

考察問題。
愚直にやるのも大変なので、二重に貪欲法※をやる。

まず、飲むカップを決めたときの最低限飲める酒の量を考える。
カップを決めた場合、飲む水と酒の量の合計は一定。
よって、酒を飲む量が最も少なくなるのは水を飲む量が最も多いとき。
つまり、最低限飲める酒の量は、n-k杯以下なら全て水だった場合の0、それより多いなら量が多い方からn-k杯を除いた量となる。

そして、飲むカップの個数だけを決めたときの最善のカップの選び方を考える。
量が少ないカップ1を飲んで、量が少ないカップ2を飲まないという選択肢は削ってよい。
というのは、カップ1の代わりにカップ2を飲むとすれば、最低限飲める酒の量が絶対に増えるから。
つまり、飲むカップの個数だけを決めたときの最善のカップの選び方は、単純に量が多い方から順に飲めばよい。

以上2つの貪欲法※により、量が少ない方から

• 1番目からi番目までは、飲まない
• i+1番目からk番目までは、飲んで、酒だった
• k+1番目からn番目までは、飲んで、水だった

というような状況のみ考えればよい。

つまり、

• 多い方から順に、残りk個になるまで全部飲み、酒の量を0とする
• 残りk個も多い方から順に1つずつ飲み、酒の量に足していく
• 酒の量がx以上になったら、その状態までに飲んだカップの数を答える
• 最後まで飲んでもx未満だったら不可能判定

とすればよい。

解答例

解答例

注意点

long long型を使用する

酒の量の合計はint型範囲を超えることがある。

別解