乱択解を紹介します。

\(M\) 回、以下の手続きをします。

• 団子の列をシャッフルする
• 二分探索で、左からちょうど1組分の団子を作れる場所を見つける
• その中の団子を一つずつ取り除いたとき、団子が作れなくなったら採用する
• 採用した団子を団子の列から抜く

回数を見積もります。

二分探索にかかる回数は多くても \(O(M\log N)\) 回で、実際はもっと小さく十分無視できます。

その次の工程を考えます。これは、団子が多ければ多いほど時間がかかります。

しかし、シャッフルをすれば、雑な見積もりですが平均的に \(O(MN)\) 回になると見積もれます。実際にはこれよりはずっと多くなりますが、よほど運が悪くない限りこれで事足りることがわかります。

ただし、シャッフルの工程を抜かすとWAになります。

実装例(C++17,2589ms)