オレンジ！

サブタスク 1：一人目が購入するオレンジの部分集合をすべて列挙する。要素数が $K$ の各集合について満足度を直接計算し、最大値を求める。時間計算量は $O(N2^N)$、空間計算量は $O(N)$ である。

全体の解法：二人目がすべて購入すると、満足度は $\sum_{i=1}^N b_i$ となる。$i$ 番目を一人目に渡すと、満足度は $a_i-b_i$ だけ変化する。

$c_i=a_i-b_i$ とすると、ちょうど $$ 個の差を選び、その総和を最大化すればよい。降順にソートして大きい方から 個を選ぶ。選んでいない値が選んだ値より大きければ、両者を交換することで総和を増やせるため、この選び方は最適である。同じ値の選択順は任意でよい。

ソート後の値を $c_1\geq c_2\geq\cdots\geq c_N$ とすると、答えは

$$\sum_{i=1}^N b_i+\sum_{i=1}^K c_i$$

となる。ちょうど $K$ 個を選ぶ必要があるため、選ぶ差が負でも省略してはいけない。

各ケースの時間計算量は $O(N\log N)$、空間計算量は $O(N)$ である。答えと途中の和の絶対値は $2\times10^{14}$ 以下、差の絶対値は 以下となる。和には 64 ビット整数を使う。

Solution written by GPT