Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 144 B問題 Gift Tax

AtCoder ARC ARC144 B問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の非負整数列 $A=(A_1, \dots, A_N)$ が与えられる.

次の操作を0回以上行った後にあり得る $\min A$ の最大値を求めよ. ただし, $a \leq b$ である.

$1 \leq i, j \leq N, i \neq j$ となる整数 $i,j$ を選び, $A_i$ に $a$ を足し, $A_j$ に $b$ を引く.

制約

$2 \leq N \leq 3 \times 10^5$
$1 \leq a \leq b \leq 10^9$
$1 \leq A_i \leq 10^9$

解法

求めるものが最小値の最大値なので, 二分探索を利用する. つまり, 以下の問題に帰着される.

以下を満たす整数 $X$ のうちの最大値 $\widetilde{X}$ を求めよ: $\min A \geq X$ となる操作が存在する.

この帰着された問題を解く. $a \leq b$ であることから, 次の事がわかる.

$\min A$ の最大値を達成するような操作のうち, $k=1,2, \dots, N$ のそれぞれにおいて, 以下が成立する操作が存在する: 以下の2つが同時に成立しない.

ある操作で $i=k$ とする.
ある操作で $j=k$ とする.

これと,

$\min A \geq X \iff \forall i \in \{1,2, \dots, N\};~A_i \geq X$

という事実から, $\min A \geq X$ となる操作が存在するための必要十分条件は以下の操作の繰り返しで全ての項を $X$ 以上にできることである.

$X$ 未満の項に $a$ を足し, $X+b$ 以上の項から $b$ を引く.

そして, これは以下と同値である.

$\displaystyle \sum_{\substack{1 \leq i \leq N \\A_i \lt X}} \left \lceil \dfrac{X-A_i}{a} \right \rceil \leq \sum_{\substack{1 \leq j \leq N \\ X+b \leq A_j}} \left \lfloor \dfrac{A_i-X}{b} \right \rfloor = \sum_{\substack{1 \leq j \leq N \\ X \leq A_j}} \left \lfloor \dfrac{A_i-X}{b} \right \rfloor$

最後に, 明らかに答えは $\min A$ 以上であり, 最大値も1回の操作で和が減少することから, $\max A$ 以上である. 従って, 計算量は $\Delta:=\max A-\min A$ とすると, $O(N \log \Delta)$ である.