定数 \(B\left(B \ge N \right)\) と，変数\(m\)を\(M\)と定めて，次のような解法を考えます．

1. まだ串にさしていない団子のなかからランダムに \( \min(B,mN)\) 個の団子を選び印をつける.
   

2. \(Query (印のついた団子の集合)\)が \(0\) なら \(1\) に戻る．
   そうでないなら3に進む．
   

3. 印のついた団子それぞれについて，( \(団子X\) とする)
   \(団子X\) を取り除いてもまだ一つ以上の串団子が作れるならば，\(団子X\) の印を消す．つまり，\(Query(印のついた団子の集合\setminus 団子X )\) が \(1\) 以上なら \(団子X\) の印を消す．
   

4. \(Answer(印のついている団子の集合)\) を実行し，印のついている団子を串にさす．
   \( m ← m-1 \) とし，\(m\) が \(1\) 以上ならば1に戻る．
   
   

\(Query\) を実行する回数を考えない時，この解法の正当性，つまり \(Answer\) で答える団子の集合の正当性は明らかです．
\(Query\) を実行する回数について考えます．

\(Query\) が実行される回数が高確率で \(50000\) 回に収まる正当性

簡単のため，\(M=25,N=400,B=4N=1600\) とします．

3で \(Query\) が実行される回数

これは\(20 \times B + \sum_{i=1}^{4} i \times N =36000\) です．

2で \(Query\) が実行されるおおよその値

まず，2が実行された後，1に戻らない確率は \( \left(1- \left(1 - \frac{4}{m} \right)^{m}\right)^{N}\) です．

簡単のため \(m=25\) とし，全体で2を実行する回数(=2で \(Query\) を実行する回数)のおおよその分布を考えます．

これは，確率 \( \left(1- \left(1 - \frac{4}{25} \right)^{25}\right)^{400}\) であたりが出るガチャを \(20\) 回あたりが出るまで回す回数の分布と一致します．(負の二項分布)

\(\left(1- \left(1 - \frac{4}{25} \right)^{25}\right)^{400} \ge 0.057\) ですが，
\(14000\) 回以内に \(20\) 回当たりを出すのに十分大きい確率です．
実際，\(14000\)回ガチャを回せば \(1-{10}^{-14}\) 以上の確率で \(20\) 回当たりが出ることが分かります．
(実際は \(m\) が動くためより小さい回数で当たりが出ます．)
よって全体で \(Query\) を高々\(50000 \) 回実行すればとても高い確率で実行が終わることが分かりました．

よって，この解法の正当性が示されました．
実装例