整数 $N,X$ と各要素が $1$ 以上 $X$ 以下の整数である長さ $N$ の数列 $A$ が与えられる。
$A$ の要素を並べ替えることで、以下で定義される「ポイント」を最適化せよ。
- 最初、 $h=0$ とする。
- その後、 $i=1,2,\dots,N$ について以下を繰り返す。
- $h$ に $A_i$ を加算する。
- この時点で $h$ が $X$ 以上である場合、 $h$ から $X$ を減算し、 $A_i$ ポイント獲得する。
$1 \le N \le 10^5$
$1 \le X \le 10^9$
$1 \le A_i \le X$
$A$ を並べ替えようと総和は一定、かつ全ての要素が $1 \le A_i \le X$ なので、ポイントが加算される回数を変えることはできない。
なので、 $A$ のうち大きい方から $k$ 要素を選んでそれをポイントの加算対象にしたい(それが自明な上界となる)が、どうすれば良いだろうか？
ポイント加算対象を直接置く方法は部分和問題みたいなものが出てきて上手くいかなそう。
いったん心を落ち着けて $A$ を昇順ソートして、前から最終的な数列を決定することを考えてみる。
すると、以下のどちらかが常に可能であることが示せる。
- ポイントを加算しないように、最小の要素 $m $ を最終的な数列の末尾に付ける
- ポイントを加算するように、最大の要素 $M $ を最終的な数列の末尾に付ける
証明
背理法で示す。
前者も後者も不可能であるとき、 $m $ を末尾に付けるとポイントが加算され、 $M $ を末尾に付けるとポイントが加算されないことになる。しかし、 $m \le M $ であるはずなのでこれは矛盾。
これから、以下の手法でポイントを自明な上界とできる。
- まず、 $A$ を昇順ソートして全て deque に突っ込む。
- 次に、dequeの末尾を現在の列の末尾に追加した際ポイントが増えるなら、そうする。その後、 deque の末尾を消す。
- そうでないなら、dequeの先頭を現在の列の末尾に追加する。その後、dequeの先頭を消す。
https://codeforces.com/contest/2161/submission/346679609
見た目えげつないのに可能枠で証明も面白い。珍しく前半枠で記事書いてる。
