Atcoder Regular Contest 079 E - Decrease (Judge ver.)

問題

arc079.contest.atcoder.jp

解法

二分探索をする。操作を全要素に+1、特定の要素に-(n+1)として見ると、k回の操作で全要素をn-1以下にできるかどうかはaの各要素の値xに関して$ \lceil \frac{x-(n-1-k)}{n+1} \rceil $の和をとってkと比較するとわかる。

普通に二分探索をしようとすると単調性が成り立つは微妙に嘘とわかるのでちょっと工夫をする。

check(x) := x回の操作で全要素がn以下になるか とする。

あるkに関してcheck(k)を仮定する。 !check(k+1)ならば最大の要素を減らなければどうしようもないので、最大のやつから選択し減らしていくと任意の要素の選択の仕方のうちで操作の回数が最小化される。

そして全要素に操作を適用すると(たぶん)k+n回の操作でもすべての要素をn-1以下にできる。よってあるl(0 < l <= n)に関して check(k) -> check(k+l) が成立する。

よって区間を2nの大きさの区間に分割して、分割後の2nの大きさの区間のなかで全要素をn-1以下にできるようなものがあればその区間はtrueといったように区間ごとに真偽を割り振る。上での考察よりこのような真偽の割り当てに対しては単調性が成り立つので、二分探索で初めてtrueとなるような区間を求める。そしてその区間内を線形探索する。

計算量はたぶん $ O(n^{2} log{\sum a[i]}) $

ソースコード

今回の想定解みたいな計算量の評価が難しい解法を思いつくのが難しい。