AtCoder Beginner Contest 307 G - Approximate Equalization
メモ
差分だけが重要なので、各Aiについて Ai -= min(A)としていい
すると任意の値が0以上の整数になる。
また、この操作において合計は不変であるため
最終的なすべての合計はsa := sigma(A)になる
最終的な数列としてあらわれる物を考える
saがNで割り切れるときはすべての要素はsa / Nになり
それ以外の場合、sa/N(切り捨て)と sa/N(切り上げ)になる
切り捨ての小さい数が最終的に数列に含まれる個数をa
切り上げの大きい数が最終的に数列に含まれる個数をbとしたときに
b = sa % Nで、a = n - bになり、他の選択肢はない
よって大きい数をどこに置くかをdpで解く問題になる。
dp[i][j] := iの前まで見て、iより左で大きい数をj個置いたときの最小手数
とすると、操作が終わった部分について、切り上げと切り捨てが何個使われているか分かるため、iより左の合計が操作後どうなったかがdpの添え字i, jから一意に特定することができる。
また、数列の合計は操作の前後で不変でありi-1までしか操作をしていないことから
iの前までの操作が終わった段階で
(A0 ~ Ai)の合計は変わっていない
よってdpの添え字i, jについて現在のAiの値は sum(A0~Ai) - 左の現在の合計
として求められる
あとは自然に遷移する
不変量って感じの問題だった
