問題のリンク : https://atcoder.jp/contests/abc441/tasks/abc441_c
この問題の難しいところは、「人間側がコップを選ぶ」と言う操作と、「コップを選んだ上でどれに日本酒が入っているのか選ぶ」 と言う操作の2つを考える、つまり「2変数関数」的な側面があるところであると思う。
2変数関数である時は、まずはどちらか1文字を固定して考えるのが典型。
まず、コップの選び方を固定して考える。
その上で日本酒の配置を考えると、1番最悪なパターンは、(∵1番最悪なパターンでも要件を満たさなければいけない)
「選んでいないコップになるべく多く日本酒が入っていて、(その上でまだ日本酒を配置できるなら)選んだコップの中から容量の小さい方から日本酒を配置する」である。
ここで、コップの選び方の固定を解除して最適な選び方を考える。
(つまり、「コップの選び方を最適(=大きい方から取っていく)」にした上で、「日本酒の場所は最悪」である場合を考えればいいと言うこと。)
その時、明らかに容量の大きい方から必要な分だけコップを取っていく操作が最適だとわかる。
以上の考察から、以下のようなアルゴリズムを考えることでACを得る。
コップの容量の小さいK個に日本酒、残りの(N - K)個に水が入っているとする。その上で、コップの容量の大きい方から1個ずつ取っていって、日本酒の量量がX以上になった時点で取るのをやめる。そこまでにかかったコップの個数が答えである。(最後まで無理なら-1)
また直感的な別解として、「どうせどれに日本酒が入っているか分からないのであれば、
なるべく容量の大きいコップから取っていくのが最適」であるとわかる。
(なぜならば、最小化したいコストはコップの「個数」であるので、どれに日本酒が入っているのか
分からない状況であれば、「コップ1つあたりの容量」は大きい方が良いと直感的にわかる)
2変数ある時、どっちを先に固定してどっちを動かすかなど(というか、ルールの順序としてどちらが先か)を整理して考えるのが大事な問題だった。