Codeforces 393 C Nikita and stack

問題概要

codeforces.com

stackの操作列が順次与えられます.それまでに与えられた操作列を適用したときのtopを求めてください 操作は(順番, 操作)で与えられます.うまく説明できないので下に例を出します
入力
(2, push1)
(3, pop)
(1, push2)
(4, push3)

1個目が飛んできます.操作列は(push 1)のみです.よってtopは1なので1を出力します.
2個目が飛んできます.操作列は(push1)(pop)です.よってstackは空なので-1を出力します.
3個目が飛んできます.順番通りに操作を並べるので,操作列は(push2)(push1)(pop)です.よってtopは2なので2を出力します.
4個目が飛んできます.操作列は(push2)(push1)(pop)(push3)なので出力は3です.
よって,
1
-1
2
3
を出力すればいいです.
また,スタックが空の時にpopが来ても,何もしないこととします.

解法

先に,自分がバチャ中にとった解法を説明して,なぜこの解法を思いつくに至ったかを説明しようと思います.

平方分割をします.
操作列をブロックに分割して,最後にそれらをマージすることを考えます.

ちなみに,O(nlogn)で済むセグ木解が想定だし,実装も少なそうです.
ですが,個人的には平方分割が考察が少なくてすぐ思いつけたので,一応記事を残しておこうと思います.

各分割で何を持つか

各分割の操作を要約することを考えると,結局,何個かの要素をpopしたあとに数をいくつかpushする,という操作に要約できます.
以下に例を示します.
(push3)(pop)(pop)(push1)(push3)(pop)(push4)
という操作は,相殺される部分を考慮すると,1回popしたあとに[1, 4]をpushする,というように言い換えることができます.
このように,ブロックbについて,先にpopする回数k_b,そのあとpushする数p_b=[p_b0, p_b1, ...]を管理します.
これで,クエリが飛んでくるたびに,更新がいるのは1ブロックだけなので,更新にいるのはO(sqrt(n))です.

各分割をマージしてスタックトップを求める

では,これらのブロックからスタックトップを求めることを考えましょう.
こちらは考えてみると意外と簡単で,スタックの気持ちになると操作列の後ろの方から考えてあげるのが自然です.
例を示しましょう.
ブロック1 : k=3, p=[2,3,4]
ブロック2 : k=2, p=[6,1,8]
のような分割をしたときに,スタックトップは8です(それはそう).最後にpushするのが8なわけですから.では,
ブロック1 : k=3, p=[2,3,4]
ブロック2 : k=2, p=[ ]
の時はどうでしょう.この時,スタックトップは2になります.操作は,(pop)x3, (push 2, 3, 4), (pop)x2になるからです.
最後にダメ押しの1例を考えます.
ブロック1 : k=3, p=[2,3,4]
ブロック2 : k=1, p=[5,6,7]
ブロック3 : k=4, p=[ ]
この時はどうなるでしょう.
この時,スタックトップは2になります.後ろからみていくとわかりやすいです.
結局,後ろからスタックを掘る数を累積していって,掘り切れなくなったところが答えです(日本語力がないから説明がヘタクソ)
そして,この時,pの中身をいちいち見る必要がないので,各ブロックからスタックトップを求めるのもO(sqrt(n))でできます.

結果,操作が飛んでくるたびに,分割の1ブロックの更新,全ブロックからスタックトップを求める,の両方がO(sqrt(n))でできるので,この問題をO(n sqrt(n))で解くことができました.

平方分割でやろう,という気になると後の考察に難しいポイントはあまりないような気がします.

じゃあどうやって思いつくの?

こういうのはどうやって思いつけばいいのかが大事だと思います.
僕がとった考察の流れとしては,
1. セグ木っぽい.操作列をセグ木で持って,操作が飛んでくるたびに,何かを更新してO(nlogn)で解けないか.
2. セグ木でいい方法があまり思いつかない.というか,セグ木である必要ある?毎回求めるのは全体の操作列の後のスタックトップ,部分的な解がいるならセグ木じゃないとだけど
3. じゃあ平方分割考えてみるか.意外と簡単にできそう?
という流れでした.

おまけ

平方分割,解いたことがないとどのような実装をすればいいのかわからないと思います(僕がそうだったため).
僕が意識しているコツとしては,
1. ブロックのサイズは問題の制約をみて固定する,入力に依存する形にしない.この問題ではn<=1e5だったので僕は400に固定しました.
2. ブロックの更新はできるだけサボる.ブロックの更新も必要な部分だけやろうとすると大変なことが多いので,思い切ってリセット.実装を後に載せますが,この問題では,更新のたびに,上でいうpをクリアしてもう1回全部求めなおしています.この方が圧倒的に楽だと思います.

実装です.
codeforces.com

最後に

僕は頭があまりよくないので,平方分割をスムーズにできるようになるまで大分時間を要しました.
なのでこの問題を割とスムーズにしばけたのは嬉しかったです.
と,いうかセグ木で考え出してセグ木諦めて平方分割で解きます->セグ木が想定でした.なの,弱い.悲しい