[AtCoder] ABC 144 E – Gluttony

問題

方針

最適な食べ物の配置

証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を

\[ A_1 \geq A_2 \geq \cdots \geq A_N \]

\[F_1 \leq F_2 \leq \cdots \leq F_N\]

と整列させます。このときのコストを、\( c \) とすると、

\[ c = \max A_iF_i \ ( 1 \leq i \leq N)\]

となります。

二分探索

成績 \( x \) を二分探索によって求めます。また、以下の手法も証明ができませんでした。上記の食べ物の配置のままで、修行を行います。\[A_iF_i > x\] を満たす \( i \) について、

\[ \lceil  \dfrac{A_iF_i – x}{F_i} \rceil\]

回の修行を行うとします。この修行回数の累積和が \( K \) 以下であれば、その \( x \) の成績は達成可能です。

コード

感想

解説を見ましたがよく分かりませんでした。