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 を入れる。
  • queueclear() できない。別のを用意するしかない。

実装ミスは、障害物 X を乗り越えていた。大文字と小文字を間違えた。

以降まだ。

OthersPermalink