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で最後まで通らなかった。原因は不明。

2012-09-08

SRM 555

| 10:25

最初に書いたeasyがテストケースに通らなくて、何で????てなって、慌てちゃって駄目だった。メンタル大事。

続きを読む

MaVadoMaVado2012/11/15 04:57God, I feel like I suhold be takin notes! Great work

aceumolrumaceumolrum2012/11/16 11:148e7OP3 , [url=http://tiujxmzupahs.com/]tiujxmzupahs[/url], [link=http://qxybcgqfzxvc.com/]qxybcgqfzxvc[/link], http://vaskdacsjgum.com/

ujndyxhamujndyxham2012/11/17 11:54igiTue <a href="http://adlcoeifsfqs.com/">adlcoeifsfqs</a>

ndxwedtubndxwedtub2012/11/17 21:30onU0bu , [url=http://rhcyzrovgklm.com/]rhcyzrovgklm[/url], [link=http://fzggvjadkdvm.com/]fzggvjadkdvm[/link], http://sgafbvxrtbgo.com/

2012-09-02

SRM 554

| 11:17

今回は、easy, mediumをサクッと片付けられたので、初の3完か!と色めき立ったけど、結局出せず。部屋で誰も出せてなかったので、結構難しかったのかな。。。。

easy TheBrickTowerEasyDivTwo

1個ずつ積んで、高さをsetに突っ込む。酷いコピペコードだ。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

set<int> s;

class TheBrickTowerEasyDivTwo{
public:
  int find(int redCount, int redHeight, int blueCount, int blueHeight){
    s.clear();
    {
      int nr=redCount;
      int nb=blueCount;
      bool red=true;
      int sum=0;
      while(nr>0 && nb>0){
	if(red){
	  nr--;
	  sum+=redHeight;
	}
	else{
	  nb--;
	  sum+=blueHeight;
	}
	red=!red;
	s.insert(sum);
      }
      if(red && nr>0){
	sum+=redHeight;
	s.insert(sum);
      }
      if(!red && nb>0){
	sum+=blueHeight;
	s.insert(sum);
      }
    }
    {
      int nr=redCount;
      int nb=blueCount;
      bool red=false;
      int sum=0;
      while(nr>0 && nb>0){
	if(red){
	  nr--;
	  sum+=redHeight;
	}
	else{
	  nb--;
	  sum+=blueHeight;
	}
	red=!red;
	s.insert(sum);
      }
      if(red && nr>0){
	sum+=redHeight;
	s.insert(sum);
      }
      if(!red && nb>0){
	sum+=blueHeight;
	s.insert(sum);
      }
    }
    return s.size();
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

こんな感じで、再帰で書くのがシンプルに書けて良い感じらしい。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

set<int> s;

class TheBrickTowerEasyDivTwo{
public:
  void red(int r, int b, int h){
    if(r==0) return;
    r--;
    h+=rh;
    s.insert(h);
    blue(r,b,h);
  }
  void blue(int r, int b, int h){
    if(b==0) return;
    b--;
    h+=bh;
    s.insert(h);
    red(r,b,h);
  }
  int find(int redCount, int redHeight, int blueCount, int blueHeight){
    s.clear();
    rh=redHeight;
    bh=blueHeight;
    red(redCount, blueCount, 0);
    blue(redCount, blueCount, 0);
    return s.size();
  }
};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


medium TheBrickTowerMediumDivTwo

順列を全列挙して調べ挙げる。next_permutationというstl関数があるのを初めて知った。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


vector<bool> flag;
vector<int> perm;
int n;
int m;
vector<int> ans;
vector<int> h;

class TheBrickTowerMediumDivTwo{
public:
  void check(){
    int sum = 0;
    for(int i = 0; i < n-1; i++){
      sum += max(h[perm[i]], h[perm[i+1]]);
    }
    if(sum < m){
      m = sum;
      ans = perm;
    }
  }
  void dfs(int depth){
    for(int j = 0; j < n; j++){
      if(depth == n){
	// copy(perm.begin(), perm.end(), ostream_iterator<int>(cout, ","));
	// cout << endl;
	check();
	return;
      }
      if(flag[j]){
	flag[j] = false;
	perm[depth] = j;
	dfs(depth+1);
	flag[j] = true;
      }
    }
  }
  vector <int> find(vector <int> heights){
    n = heights.size();
    flag.clear(); flag.resize(n, true);
    perm.clear(); perm.resize(n);
    h = heights;
    m = INT_MAX;
    dfs(0);
    return ans;
  }
};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

LamlakLamlak2012/11/14 21:46Nunquam dormio пишет...Да ничего ужасного в них нет. Просто с ними редко приходится работать и синтаксис у программиста вылетает из головы. Если руку набить, то работать с ними становится легко и приятно.Собсвенно мне приходилось писать под платформу, на которой был только C компилятор(причём результат компиляции выполнялся на виртуальной машине). А хотелось с минимальными усилиями перенести туда кучу кода на C++. И для этой платформы я разрабатывал фрэймворк, использующий что-то вроде классов с наследовнием и виртуальными функциями. Вся система была достаточно сильно завязана на указатели на функции. Работать с ними было действительно легко, но почему-то хотелось лучшего.

MasatoshiMasatoshi2012/11/16 17:31Thanks for introducing a ltitle rationality into this debate.

mfejmkmkrtjmfejmkmkrtj2012/11/16 22:40SI7RT7 <a href="http://riltsdnktpce.com/">riltsdnktpce</a>

chfexptchfexpt2012/11/18 20:062Tx7XX <a href="http://xwgcvxszafet.com/">xwgcvxszafet</a>

ahnixgiahnixgi2012/11/19 09:20So7FuV , [url=http://xgdejbnsovrl.com/]xgdejbnsovrl[/url], [link=http://lqfpsssdaadf.com/]lqfpsssdaadf[/link], http://zwluvnuzugrz.com/

2012-08-12

2012 august challenge

| 21:10

  • Little elephant and bombs
  • delivery boy
  • range of data

の3完。

続きを読む

MiguelinaMiguelina2012/08/29 20:48Most powerful&cost efceftive SEO and website traffic service in world get up to 100’000 forum backlinks now! Get incredible online web traffic using best backlink service available. We can post your custom message up to 100’000 forums worldwide, get insane amount of backlinks and incredible targeted web traffic in shortest time. Most affordable and most powerful service for web traffic and backlinks in the world!!!! Your post will be published up to 100000 forums worldwide your website or blog will get instant traffic and massive increase in seo rankings just after few days or weeks so your site will get targeted long term traffic from search engines. Order now:

uoyaxoglfdjuoyaxoglfdj2012/08/31 04:59scuZqw , [url=http://vlkdqvqlifrd.com/]vlkdqvqlifrd[/url], [link=http://mkrzcgvnnozo.com/]mkrzcgvnnozo[/link], http://kwnqqxfyfyco.com/

jljeifnjjljeifnj2012/08/31 19:09SSv9vA <a href="http://pnwwubddjbtq.com/">pnwwubddjbtq</a>

wvjlhzmjowvjlhzmjo2012/09/02 06:41YREWdO , [url=http://azuvcswvjrov.com/]azuvcswvjrov[/url], [link=http://diatvmcjxrup.com/]diatvmcjxrup[/link], http://dggldhvstkaf.com/

|