天下一プログラミングコンテスト2013 予選B

B. 天下一後入れ先出しデータ構造解説

［問題文］

この問題は基本的なデータ構造の1つであるスタックに関する問題です。

部分点解法（30点）

与えれれる命令の個数、スタックに入れる数値の個数ともに小さいものとなっています。単一の値を保持する様なスタックを作成するか、言語の標準ライブラリ等にあるスタックを利用し、与えられた通りに命令を実行していくと良いでしょう。

満点解法（60点）

命令の個数、スタックに入れる数値の個数がともに10⁵以下となっています。1つ1つ値をスタックへ入れた場合、スタックに対するPush操作とPop操作の最大の回数は合わせて10¹⁰回となります。これを素直に実行した場合、制限時間を超えてしまいます。

スタックに対する操作の回数を減らすため、値と個数の組をスタックに保持する様に実装します。また、10¹⁰は符号付き32bit整数の上限である2147483647を上回っており、サイズに関しての判定にはそれ以上の数を表すことの出来る型を選ぶ等の工夫が必要です。