まず次のような問題を考えてみます。

\(N\) 人のこどもが一列に並んでいます。前から \(i\) 番目のこどもは \(A_i\) 個のアメを持っています。
あなたは全てのこどもが \(X\) 個以上アメを持っている状態になるまで次の操作を繰り返します。
「持っているアメの個数が最も少ないこども(複数いるならそのうち最も前にいるこども) \(1\) 人に、アメを \(K\) 個与える」
操作回数を求めてください。

この問題では、アメをあげる対象として「持っているアメの個数が最も少ないこども」をわざわざ選ぶ必要はなく、こどもごとに操作をしてよいため、答えは \(\displaystyle \sum_{i=1}^{N} \max\left(0,\left\lceil\frac{X-A_i}{K}\right\rceil\right)\) となります。

元の問題を考えます。操作を行うごとに子供が持っているアメの個数の最小値は単調に増加していきます。したがって、\(M\) 回の操作後の子供が持っているアメの個数の最小値は二分探索により求めることができます。判定問題では前述の問題を解くことになるため \(O(N)\) の時間がかかります。

二分探索によりもとめた、\(M\) 回の操作後に子供が持っているアメの個数の最小値を \(X\) とします。この情報を使って操作を終盤までショートカットしましょう。前述の問題のように、こどもごとに持っているアメの個数が \(X\) 以上になるまでアメを与えます。これは \(O(N)\) 時間でできます。残った操作回数は、先頭から順に、持っているアメの個数がちょうど \(X\) であるようなこどもに対して操作を行うことで消化できます。

\(M\) 回の操作後にこどもが持っているアメの総数は \(S:=MK+\sum_i A_i\) なので、こどもが持っているアメの個数の最小値として考えられる最大値は \(\lfloor\frac{S}{N}\rfloor\) であり、これを二分探索の上限値として使うことができます。

以上により、 \(O(N\log \frac{S}{N})\) で問題を解くことができました。実装の際はオーバーフローに注意してください。