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