AtCoder Beginner Contest 144 E - Gluttony

解法

この問題はいくつか考察ステップが必要なので、順に見ていきましょう。

記法などについて

簡単のため、入力として与えられる値の集合 $\lbrace A_{1}, ..., A_{N} \rbrace$ を単に $A$ 、 $\lbrace F_{1}, ..., F_{N} \rbrace$ を単に $F$ と書くことにします。

また、最小化すべき値である「メンバーと食べ物の組み方を決めた時の、積 $A_{i}F_{i}$ の最大値」を単に「スコア」と書くことにします。

最適なメンバーと食べ物の組み方

まず修行のことは忘れましょう。

メンバーの消化コスト $A$ と食べ物の食べにくさ $F$ が与えられた時、どのように組めばスコアを小さくできるでしょうか。感覚的には大きい値同士を組ませると超大きい値ができるので悪手であり、大きいものと小さいもの、小さいものと大きいものを組ませたほうが良いような気がします。

これは実際に正しくて、 $A$ を小さい方から順に、 $F$ を大きい方から順に並べて組ませるのが最適になります。証明してみましょう。

f:id:betrue12:20191030005215p:plain

最適性の証明

このような並べ方や組み方の最適性を証明するテクニックとして、「このような組み方になっていないものは、ある所を組み替えることで得をする（または損しない）」ということを示す方法があります。

図のように、まず $A$ を昇順にソートして固定します。この下に $F$ をどう並べるかを考えます。インデックスは、並べた順番に振り直すことにします。

f:id:betrue12:20191030005633p:plain

もし上の図のように $F$ が降順に並んでいないとします。このときには、 $A_{i} \le A_{j}$ かつ $F_{i} \lt F_{j}$ であるようなペア $i$ とペア $j$ が必ずどこかに存在しているはずです。上の図でいうと $2, 3$ です。

このとき常に $A_{i}F_{i} \lt A_{j}F_{j}$ が成り立つので、最大値を考える上で $A_{i}F_{i}$ は無視できます。つまりスコアを $S$ とすると

$S = \max\left(A_{j}F_{j}, (他のペアたちの値...)\right)$

となります。

この $F_{i}$ と $F_{j}$ を入れ替えてみましょう。この時のスコアを $S^{\prime}$ とすると

$S^{\prime} = \max\left(A_{i}F_{j}, A_{j}F_{i}, (他のペアたちの値...)\right)$

となります。 $A_{i}F_{j}$ と $A_{j}F_{i}$ のどちらが大きいかは場合によりますが、これらはどちらも $A_{j}F_{j}$ 以下です。他のペアたちの値は変わらないので、

$S \ge S^{\prime}$

が常に成立します。これはつまり、 $F$ が降順に並んでいないならば、 $A_{i} \le A_{j}$ かつ $F_{i} \lt F_{j}$ であるような $F_{i}, F_{j}$ を選んでスワップすることで、得をするか損をしないように必ず組み方を変更できるということを意味します。

そしてこの操作ができなくなるまで繰り返すと、どのような並び方からスタートしてどう操作をしても、最後には $F$ が降順にソートされた状態になります。これはつまり $F$ が降順にソートされた状態が、他の全ての並べ方よりも得をするか損をしないこと、つまり最適であることを意味します。

修行で $A$ が変化する場合は？

修行のことを思い出しましょう。

修行前の $A$ を昇順に並べてペアを決めたとします。ここでもし修行によって大小が逆転すると、最適な組み方が変わってしまいます。

ただしこれは気にしなくて良いです。大小が逆転するような修行の割り振りは、以下のように同じ値で大小が逆転しないような割り振りに置き換えることができるからです。

f:id:betrue12:20191030010728p:plain

答えを求める

いよいよ答えを求めます。これまで見てきたように、ペアの組み方は修行前の $A$ を昇順に、 $F$ を降順にしたものだけを考えれば良いです。

もし修行回数 $K$ が少なければ、例えば「今 $A_{i}F_{i}$ が最も大きい組を選んで修行させる」ことを $K$ 回繰り返して最大値がどこまで落ちるか調べることで答えを求められます。ですが今回は $K \le 10^{18}$ なので厳しいです。

発想を逆転させましょう。ある目標スコア $X$ を決めて、

$\max A_{i}F_{i} \le X$ とするための合計修行回数はいくつか？

を求めるような問題を考えます。この場合は全ペアについて $A_{i}F_{i} \le X$ となればよいので、メンバー $i$ の $A_{i}$ の目標値は $\lfloor\frac{X}{F_{i}}\rfloor$ です。初期値が目標値以下である場合は修行不要で、目標値より大きい場合はその差がそのまま必要修行回数となります。その合計は $O(N)$ で求められます。

そしてこれは二分探索ができる形になっています。目標スコア $X$ を小さくするほど必要な修行回数は多くなり、単調性があるからです。つまり判定問題を

ある固定した値 $X$ について、 $\max A_{i}F_{i} \le X$ とするための合計修行回数は $K$ 以下か？

として二分探索をすることで、答えを求めることができます。その判定方法は先ほど書いたように、メンバー $i$ の $A_{i}$ の目標値を $\lfloor\frac{X}{F_{i}}\rfloor$ として、初期値がこれより大きいものについてその差を合計し、 $K$ 以下であるか調べれば良いです。

まとめ

この問題で用いた方法はかなりの頻出テクニックで、覚えておくと役に立つ可能性大です。

要素の組み合わせ方・並べ方について、「ある規則でソートするとそれが最適になっている」という場合がある。
- その証明テクとして、「そうなっていないものはあるところを入れ替えると必ず改善できる」という手法を使うことが多い。
- こういうソート規則が使えない問題ではDP等に頼ることになります
「最大値を最小化する」という問題では二分探索が使えることが非常に多い。
- 最大値を $X$ 以下にする＝全ての要素を $X$ 以下にする
- 目標値を固定することで、そのために必要な操作回数などが簡単な計算で求まったり、貪欲法が使えたりする。
- 過去記事にもまとめています