ICPCの季節 - Logic Dice

練習量が足りない……とりあえず、高速に問題を解くためのメモ。

setは追加にinsertメソッドを利用する。集合なので、重複要素は登録されない。
要素の比較にはfindメソッドを利用する。見つからない場合、イテレータ終端が返る。
要素数はsizeメソッドで取得できる。
setの場合、iteratorで取り出す要素は、自動的にソートされている。
(データ構造)::iteratorのようにしてイテレータを使用する。
vectorなどの全要素のソートにはalgorithm内のsortが利用できる。引数は、ソートする範囲を示すイテレータ。
listは標準でsortメソッドを持つ。
自分のオリジナルの構造体などをソートする場合、それらの演算子(大なり比較、小なり比較)を定義する必要がある。

// setの使用例
set<int> s;
s.insert(10);  // 追加
if( s.find(100) != s.end() ) {
   // 発見
}

// vectorの全要素ソート(昇順)
vector<int> v;
sort(v.begin(), v.end());

// 自作構造体Edgeの順位づけ
// 長さが短い方が小さいとみなされる
typedef struct __EDGE {
  double len;
  int v1, v2;
}Edge;

bool operator<(const Edge& left, const Edge& right) {
  return left.len < right.len;
}

bool operator>(const Edge& left, const Edge& right) {
  return left.len > right.len;
}

とりあえず解いてみた。C++で。STLの勉強を兼ねるので、最適化、何ソレ美味しいの？というレベル。

1314 - Finding Rectangles

タダの全数探索。ソートして行えば良い物を無理矢理setを利用してみる。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1314

2560 - Freckles

最小全域木の作成。昔Javaでやったのとほぼ同じコードが出来た。プリム法。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2560