2-1 すべての基本 “全探索” (未完)

更新日時:

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

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

以降まだ。

その他

コメントする