Knapsack And Queries - JAG夏合宿2018 day2 D
D - Knapsack And Queries
良く出来てるなぁ。
queueをstack２つで実現できるっていう知る人ぞ知るテクがある。
純粋関数型データ構造界隈とかで有名らしい。
どうやるかというと、
- queueにpush
- 単にstack2にpushする
- queueからpop
- stack1が空でない：stack1からpop
- stack1が空：「stack2からpopしてstack1にpush」をstack2が空になるまでやる
計算量は、各要素が高々2回ずつしかpushされないことから、均しで線形であることがわかる。
これをそのまま使うと例えば以下の問題が解ける。
- 正整数の集合Sがあり、最初は空である。Sに対する以下のクエリを処理せよ。
- push x：Sにxを追加する
- pop：Sの要素のうち最も古いものを削除
- gcd：Sの要素のgcdを答える
- 計算量は O(クエリ数*gcdの計算量)
ただ、これだとsegtreeを使ったりするのと区別ができないのでコンテストで出題するのは難しい。
元の問題の解法に話を戻すと、あとはdpテーブル２つから答えを計算できればいいけど、これは片方のテーブルを全部舐めてもう片方のテーブルでスライド最小値をすれば良い。
なるほど、このテクでは２つの要素をマージできる必要はなくて、２つの要素から答えを計算できれば十分なんだなぁ。
作問が上手すぎる。
ちなみに、dequeもstack２つで実現できる。（償却計算量は同様に線形）