ボールが消えるかどうか判定するためには、同じ整数が書かれたボールが何個連続しているかを管理する必要があります。

同じ整数が書かれたボールが連続している部分を \((整数, 個数)\) の形で管理することを考えます。

新たに \(x\) が書かれたボールを落とすとします。筒が空の場合は \((x, 1)\) を新たに追加します。筒が空でない場合、筒の最上部の連続した部分が \((a, b)\) であるとすると、

• \(a \neq x\) のとき、\((x, 1)\) を新たに追加する。
• \(a = x\) のとき、\((a, b)\) を \((a, b + 1)\) に置き換える。
  • ここで、\(a = b + 1\) となってしまった場合は、\((a, b + 1)\) を取り除く。これがボールを消す操作に対応する。

以上はスタックと呼ばれるデータ構造を用いて実装することができます。スタックは次の操作をサポートします :

• \(\mathrm{push}(x) : \) 新たに \(x\) を追加する。
• \(\mathrm{top}() : \) 現存する要素のうち、最後に追加されたものを取得する。
• \(\mathrm{pop}() : \) 現存する要素のうち、最後に追加されたものを取り除く。

机の上に本を積んだり、一番上に積まれた本を取ったりする様子を考えるとイメージしやすいでしょう。

実装例 (C++)