蟻本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++つよい。
