Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-10-10

最小値を返せるFIFO queue

| 22:52

Codechef 2012 sep challenge CHEFTOWNの解説を読んだメモ。Codechefは解説付きなのが有難い。

  • 要素の追加削除はFIFO
  • いつでも最小値を取り出せる

というデータ構造を考えたい。いきなりソース。

#include <deque>
#include <queue>
#include <iostream>


using namespace std;


template<class T>
class FifoMin{
public:
  T pop(){
    T ret = q.front(); q.pop();
    if(ret==dq.front()) dq.pop_front();
    return ret;
  }
  T insert(const T& x){
    while(dq.size()>0 && x < dq.back()) dq.pop_back();
    dq.push_back(x);
    q.push(x);
  }
  T min(){
    return dq.front();
  }
  size_t size(){
    return q.size();
  }
protected:
  deque<T> dq;
  queue<T> q;
};

int main(int argc, char *argv[]){
  FifoMin<double> x;
  for(size_t i = 0; i < 10; ++i){
    x.insert(i);
  }
  x.insert(3.5);
  x.insert(5.5);
  while(x.size()>0){
    cout << x.min() << "\t";
    cout << x.pop() << endl;
  }
  return 0;
}
ポイント1 基本的な構造

普通のFIFO queueと、dequeを持つ。queueには全要素を通常のFIFO順で保持。dequeには、一部の要素を昇順で保持。この時、dequeの先頭が最小要素であるように保つ。

ポイント2 挿入動作

新しく、xという値を挿入することを考える。この時、xより大きい要素を全部dequeの後ろから除いた上で、xをdequeの最後尾に追加。ここで除かれている要素は、今挿入したxよりも先に登録されている事に注意。その事と、要素の削除がFIFO順であることから、最小値の問い合わせの際にこれら除かれた要素が返される事はあり得ない。

queueの方には、特別な事をせずに最後尾に追加。

ポイント3 計算量

例えば、1,2,3,...,n,0という順に追加する時、最後の0の追加でn回のdequeからのpopがあるけど、その前のn回の挿入の際には1度もpopが無い。という感じで、均せばO(1)で挿入出来る。

余談

検算の出力の部分を

 cout << x.min() << "\t" << x.pop() << endl;

としていたら、出力が想定と違っちゃって焦った。x.pop()が先に評価されるらしい。

余談2

上のデータ構造を使えば O(n)の解答が書けるというのが解説の内容。本番では、O(n log W)の解答を出しているつもりだったんだけど、TLEで最後まで通らなかった。原因は不明。

 |