数列のソート 4

位置 $i$ を選ぶ回数を $x_i$ とする。総操作回数は全要素から共通に引かれるので整列条件には影響しない。必要な条件は $A_i+2x_i\leq A_{i+1}+2x_{i+1}$。$x_1=0$ とし、$x_i=\max(0,x_{i-1}+\lceil(A_{i-1}-A_i)/2\rceil)$ とする。前の回数を増やしても後の下限は減らないため、これは最適である。

各 $x_i$ は $5\cdot10^8+50000$ 以下であり、操作回数の総和も $5.0005\cdot10^{13}$ 以下となる。したがって、符号付き64ビット整数型で正確な答えを計算できる。負の差の切り上げ除算に注意する。計算量は である。

Solution written by GPT6