[1] \(1\) 度も操作をしない項が存在するとき

操作は必ず値を増加させるため、操作をしない項は \(A\) の最大値であるとしてよいです。

初期状態での \(A\) の最大値を \(a\) とします。このとき、各 \(A_i\) に対する操作は、

• \(a\) 以上の数のうち、変化させることが可能な最小値に変化させる
• \(a\) 以下の数のうち、変化させることが可能な最大値に変化させる

のどちらかであるとしてよいです。また、これらの最小値・最大値は操作回数ごとに計算することで、\(O(\log a)\) 時間で計算できます。結局、次の問題が解ければよいです。

\(a\) 以下の整数の列 \((L_1, \ldots, L_N)\) および、\(a\) 以上の整数の列 \((R_1, \ldots, R_N)\) が与えられる。各 \(i\) に対して \(A_i\) を \(L_i\) または \(R_i\) の一方に変化させるとき、\(\max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\}\) を最小化せよ。

この問題は次のようにして解くことができます。

まず、ソートをして \(L_1\leq \cdots \leq L_N \leq a\) が成り立つようにしておきます。\(A_n = L_n\) を選ぶ \(n\) の最小値を固定すると、\(i < n\) ならば \(A_i = R_i\)、そうでなければ \(A_i = L_i\) とするのが最適で、その場合の \(\max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\}\) も容易に計算できます。

[2] 本問の解法

まずは、[1] の問題を解いておきます。この答を \(Y\) とします。すると、本問の答は次のようになります：

• \(Y < X\) のとき：答は \(0\) である。
• \(Y \geq X\) のとき：答は \(Y\) である。

このことを確かめましょう。

まず、\(Y < X\) であるとします。次を示せばよいです：

数列 \((A_1, \ldots, A_N)\) の最大値と最小値の差が \(Y\) （\(0 < Y < X\)）であるとき、すべての項に適切に \(1\) 度ずつ操作を行えば、最大値と最小値の差を \(Y\) 未満にできる。

最小値 \(A_i\) を \(2A_i + Y + 1\) に変化させ、最大値 \(A_j\) を \(2A_j\) に変化させると、これらの差は \(Y-1\) に減少します。最小値と最大値の間の値も適切に変化させることで、目的を達成できます。

次に、\(Y\geq X\) であるとします。数列のすべての項に何度か操作を行うことは、次の \(2\) ステップに分解することができます。

• \(1\) 度も操作を行わない項が存在するという制約のもとで、何度か操作を行う。
• その後、「すべての項に \(1\) 度ずつ操作を行う」ことを何度か繰り返す。

前者のステップが完了した時点で、数列の最大値と最小値の差は必ず \(Y\) 以上になります。このとき、後者のステップを何度行っても最大値と最小値の差が常に \(Y\) 以上であることが、\(Y\geq X\) を用いて帰納的に証明できます。したがって、この場合の答は \(Y\) となります。

以上をまとめると、本問は \(O(N(\log N + \log \max A_i))\) 時間で解くことができます。