2-1 すべての基本 “全探索” (未完)
Updated:
例題 1-1-1 (ハードルの上がった) くじびき
AOJ 0529 ダーツ (JOI 2007)
半分全列挙をする。 2 本の矢で作れる得点を set<int> に入れておき、もう 2 本の矢で作れる得点を sum ごとに、合計が $M$ を超えないような最大の点数を求める。計算量は $O(N^2 \log N)$ となる。……という解答だと AOJ だと TLE になる。 1 sec はきつすぎでは。 vector<int> を sort して尺取り法に変更すると $O(N^2 + \log N) = O(N^2)$ になる。
例題 1-6-1 三角形
AOJ 0582 Triangle Types (JOI 2005)
三角形の判定条件。やるだけ。
例題 2-1-1 部分和問題
全部やっていた。
例題 2-1-2 Lake Counting
これも全部やっていた。
例題 2-1-3 迷路の最短路
AOJ 0558 チーズ (JOI 2010 予選)
重みなしの最短経路。基本は幅優先探索を $N$ 回やるだけ。次の点に注意。
- BFS の visited である
int d[1010][1010]は 距離で管理 する。最初はinftyを入れる。 queueはclear()できない。別のを用意するしかない。
実装ミスは、障害物 X を乗り越えていた。大文字と小文字を間違えた。
以降まだ。