ABC068 D - Decrease (Contestant ver.)
解法
操作が2種類あって考えづらいので、操作をひとまとめにします。
答えとなる数列の全ての数字にを足し、1回の操作を行うと、数列の最大値を1つ選びを減らす、というようにすると、回操作を行った後の状態はもともとの条件と同じ数列になります。
最終的な状態はにしたいので、その状態から逆向きに復元していきます。
このとき、にするという条件に変更すれば、最終的に出来上がる数列が上で行ったを足すという操作を打ち消すことができ、そのまま答えとなります。
ということで、全ての要素がの個の数字が並んだ数列について、回増やすという操作を行って元の状態に戻すことを考えると、どこか1つに集中して操作を行うと答えの条件を満たさなくなってしまう(数字が大きくなりすぎるため)ので、
回の操作は個の要素に均一になるように割り振ってあげればいいことになります。
あとは、が大きい時はが小さいと条件を満たせなくなりますが、を常に最大のに設定していれば、全てのパターンを網羅できるため、常にと固定してしまって処理を行ってあげます。
ということで、、要素の初期値がすべての数列に、個のを、それぞれの要素について回ずつ割り振ってあげれば答えとなります。端数は、その個数だけ適当に1回操作を追加してあげれば大丈夫です。