読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

蟻本2-4

動的計画法を一旦飛ばして読み進めてる(個数制限なしナップサック問題の漸化式の変形がわからんかった)

プライオリティキュー

使い方

#include <queue>

priority_queue<int> pque; // int型のプライオリティキューpque

pque.push(num); // numをpqueにpush
pque.top() // pqueの最大値
pque.pop() // pqueの最大値をpop
pque.empty() //pqueが空ならtrue

プライオリティキューはキューの中身が(デフォルトでは)降順に並べ替えられてるだけで、操作方法(使う関数)は同じ。
中身を昇順にしたければ、宣言の部分を、

priority_queue<int, vector<int>, greater<int> > que;

とすればいいらしい。中身はリファレンス見たけどわからなかった。(vectorとgreaterがわからなかったけど省略した)
これでDijkstraが実装できるぞー(やったぜ)

Expedition(POJ2431)

全部試すとO(2^N)でまあ全探索は無理。
「ガソリンスタンドを通ると燃料缶がもらえて、なくなったところで今持ってる燃料缶を使う。使った回数は?」って言いかえた方が自分はわかりやすかった。ガソリンスタンドの場所気にしなくていいって考えは使えそう。
1番量の多い缶から補給するから貪欲法って言っていいのだろうか。補給場所に制限があったら使えなさそう(補給した次のガソリンスタンドでは補給しちゃダメとか)。
計算量は最悪は全部燃料使った時だからO(N)。
POJに通そうと思ってちょこっと修正したら、サンプルは通ったのにRuntimeErrorだった。

Fence Repair(POJ3253)

前回はO(N^2)の方法が載ってたけどプライオリティキューだとO(NlogN)でいけますね〜という話だけど、前回の時点で、O(NlogN)でソート+O(logN)で挿入がN回だからO(NlogN)でいけることに気がついてた。二分探索のリファレンス見るの面倒だったから実装してないけども。

二分探索木

ちゃんと実装するとポインタの操作がつらそう(せやろか)。やっぱりあってよかったSTL
setとかmapとか。

setの使い方

#include <set>

set<int> s; // int型のset sの宣言

s.insert(num); // numをsにinsert
s.erase(num); // numをsから削除

set<int>::iterator ite; setを探索する用のイテレータite
s.begin() // sの先頭(一番初めの一つ前)のイテレータ、最初の要素のイテレータではない
s.end() // sの末尾(一番最後の一つ後)のイテレータ、最後の要素のイテレータではない
s.find(num); // findはnumがあればnumのイテレータが、なければs.end()が帰る
s.count(num); // countはnumがあれば1が、なければ0が帰る(setは重複がないから必ず0か1になる)

勝手にソートしてくれるから二分探索木になってるそうな。

mapの使い方

#include <map>

map<int, const char*> a; // int型のキーとchar*型の値を持つmap mの宣言

m.insert(make_pair(num, "hogehoge")); // キーがnumで値がhogehogeであるpairをmにinsert
m[num]="hogehoge" // 上と同じ結果が得られる(配列風の書き方ができる)
m.erase(num); // numをmから削除

map<int, const char*>::iterator ite; mapを探索する用のイテレータite
m.begin() // mの先頭(一番初めの一つ前)のイテレータ、最初の要素のイテレータではない
m.end() // mの末尾(一番最後の一つ後)のイテレータ、最後の要素のイテレータではない
m.find(num); // findはnumがあればnumのイテレータが、なければs.end()が帰る
m.find(num)->first // numが帰る(ポインタ風の書き方ができる)
m.find(num)->second // "hogehoge"が帰る

キー付きのsetという解釈してる。

両方ともここ(C/C++ リファレンス)を参考にした。
単に二分木つくるだけだと根に一番小さい値を持ってきた場合とか、アホみたいに深くなるけど、これらは勝手にバランスとって平行二分木になってくれるらしい。やっぱりC++つよい。

Union-Find木

グループ化されたいくつかの木について、

  • 2つの数が同じグループに属するか調べる
  • 2つの数の属するグループを統合する

という2つのことが効率的にできるデータ構造らしい。
計算量はO(α)とかいうほとんどお見かけしないやつ。αはAckermannの逆関数らしい。
以前、計算量の話でちらっと見かけたことはあったけど、お初にお目にかかった。

食物連鎖(POJ1182)

最初解説読んでも意味わからんかったけど、数学的帰納法っぽく考えたらいけそうな時はいけそうってなった。
これで全通り調べられてるのにTLEしないのは驚愕っぽい。