ABC068/ARC079 E - Decrease (Judge ver.)
とても面白い……！
問題概要
長さ$ Nの正数列$ Aに対して以下の操作をする。
$ Aの最も大きい要素を$ 1つ選ぶ。その値を$ N減らす。選ばれなかった要素全てに$ 1を加算する。
この操作を$ \mathrm{max}(A) \gt N-1の間行う。何回操作することになるか？
制約
$ N \leq 50
$ A_i \leq 10^{16}+1000
考察
まず、全ての要素$ A_1, A_2, \ldots, A_Nについて順番に、数列$ A内の大きさに関わらず
$ A_iが$ N-1より大きい間、$ A_iから$ Nを引きそれ以外には$ 1を足す
ことを繰り返しても構わない。操作の順序によらず操作回数は一定なままに保たれることからなんとなくわかるだろう。
ただ、D 問題を解いていればわかると思うが操作回数も非常に大きくなるはずなので、高速にシミュレートすることでなんとかしたい。 $ A_iが$ N-1より大きい間、$ A_iから$ Nを引きそれ以外には$ 1を足す
この操作の回数は、$ A_i / Nを切り捨てた値に等しい。これは簡単にまとめて処理することが出来て、何も頑張らなくても$ Ο(N)で処理できる。
では、どんな順番で数列の値を選ぶか、というところになる。
毎回一番大きい値を取り出すのももちろん頑張れば$ \Omicron(\log N)で出来るのだが、先ほど述べたように$ A_1, A_2, \ldots, A_Nに対して操作することを何回も繰り返す操作のオーダーを評価してみよう。
ここで、以降$ \rho = 50 \times 10^{16}とする。
$ A_1に対して操作したときに$ A_2, A_3, \ldots, A_Nに$ 1足される回数は$ A_1 / Nである。これを全部の要素にした場合、その合計はだいたいどの要素も$ (\Sigma_{k=1}^{N} A_k) \div Nなる。
よって、$ t回操作したときの各要素の値は$ \Omicron(ρ \div N^t)と表すことが出来て、$ \rho \div N^t \leq N-1が成り立つ$ tは本当にひどい場合でも$ 60以下になる。つまり、せいぜい$ 150000ステップ程度で計算は終了することが分かり、この問題を解けた。