ABC068/ARC079 D - Decrease (Contestant ver.)
構築のほうが下にあるペア問題ってなかなか珍しい気もする
問題概要
長さ$ Nの正数列$ Aに対して以下の操作をする。
$ Aの最も大きい要素を$ 1つ選ぶ。その値を$ N減らす。選ばれなかった要素全てに$ 1を加算する。
この操作をちょうど$ k回行ったときに$ \mathrm{max}(A) \leq N-1になるような数列を$ 1つ構築せよ。
制約
$ K \leq 50 \times 10^{16}
$ 2 \leq N \leq 50, A \leq 10^{16}+1000となるように構築せよ。
考察
サンプル$ 1に大ヒントがある。全ての$ iについて$ A_i = N-1ならば$ 1度も操作はされないし出来ない。
これを起点に考える。
また、構築系の問題では典型的な方針として「必勝法」があることが多い。今回もそれを探っていく。
ひとまず、操作を全てひっくり返してみる。
最小の要素を$ 1つ選び、その値に$ Nを足す。選ばれなかった要素全てから$ 1を引く。
例えば$ [3, 3, 3, 3] に対してこの操作を繰り返すと$ N=4 回後に$ [4, 4, 4, 4] を得られる。
どうも全ての値が$ 1大きくなるのに$ N回かかるらしい。
操作内容を全てひっくり返しているので、実際には$ N回後には全ての値が$ 1小さくなるのだが、これはいい性質である。
残り$ 0 回操作をする必要があるときの数列$ = [N-1, N-1, \ldots, N-1] であるとしよう。
残り$ K回操作をする必要があるときの数列が欲しいのだから、$ \alpha N回の操作を全体に$ \alphaを足すことですっ飛ばしてやればよく、$ \alpha = K \div Nの切り捨て とすることで残り$ K \bmod N回の逆操作を愚直にシミュレートしてよいことになり、計算量は$ \Omicron(N^2)になる。
最後に$ Nとして使う値が気になるところだが、基本的に$ N=50である必要がある。
これは$ \alpha \geq 10^{16}となると基本的に論外なためであり、$ K \leq 50 \times 10^{16}から$ N=50が妥当だろう。