More Related Content
What's hot (20)
Similar to 二分探索をはじめからていねいに (8)
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
二分探索をはじめからていねいに
- 3. 二分探索のイメージ 50 13 19 27 30 34 39 44 47 56 58 60 ● 昇順ソート済みの配列 a の要素について 探索することを考える ● 今回は、47がどこにあるかを探してみよう
- 4. 二分探索のイメージ 0 5 13 19 27 30 34 39 44 47 56 58 60 lb ubmid src
- 5. 二分探索のイメージ 0 5 13 19 27 30 34 39 44 47 56 58 60 lb ubmid midの要素は47以下である → 探索したい数字は配列の右半分にある！ → 探索範囲を右半分に絞る ※midの要素が47を超える数字の場合は、 探索範囲を左半分に絞る これの繰り返しを、ub - lbが1になるまで行う src
- 6. 二分探索のイメージ 0 5 13 19 27 30 34 39 44 47 56 58 60 lb ubmid src midの要素は47以下である → 探索したい数字は配列の右半分にある！ → 探索範囲を右半分に絞る ※midの要素が47を超える数字の場合は、 探索範囲を左半分に絞る これの繰り返しを、ub - lbが1になるまで行う
- 7. 二分探索のイメージ 0 5 13 19 27 30 34 39 44 47 56 58 60 lb ubmid src midの要素は47を超えている → 探索したい数字は配列の左半分にある！ → 探索範囲を左半分に絞る ※midの要素が47以下である数字の場合は、 探索範囲を右半分に絞る これの繰り返しを、ub - lbが1になるまで行う
- 8. 二分探索のイメージ 0 5 13 19 27 30 34 39 44 47 56 58 60 lb ub lbは、探索する要素 「以下」になる 最後の要素を指す(注意) ubは、探索する要素を 「超える」 最初の要素を指す src
- 9. 二分探索 (C++) ● 先ほどの操作をしてくれるSTLが用意されている ● 要 #include <algorithm> ● イテレータが返ることに注意 ● lower_boundは、探索する要素「以上」になる 最初の要素のイテレータを取得する ● upper_boundは、探索する要素を「超える」 最初の要素のイテレータを取得する
- 10. 二分探索問題解説 二分探索は、今まで説明してきた 「値の検索」以外の使い方もできる …今回は4題を解説！ ● Cable master ● Aggressive cows ● Monthly Expense ● 平均最大化
- 11. Cable master 長さがそれぞれLiであるようなN本の紐がありま す。これらの紐を切って、同じ長さの紐をK本作 るときの最長の長さを求めなさい。答えは小数点 以下2桁までを切り捨てで出力しなさい。 制約: ● 1 ≦ N ≦ 10,000 ● 1 ≦ K ≦ 10,000 ● 1 ≦ Li ≦ 100,000
- 12. Cable master たとえば… N = 4, K = 11, L = {8.02, 7.43, 4.57, 5.39} 8.02 7.43 4.57 5.39
- 14. Cable master 条件 C(x) = 「長さxの紐をK本切り出すことが できるかどうか (bool値)」 を用意 ※floor関数は、切り捨て操作を行う関数
- 15. Cable master 今回は、ub – lbの値を終了条件にするのではなく、 二分探索をした回数を終了条件とする ※二分探索を100回行うと、解の最終的な存在範囲は、 (最初の範囲) ? (?) ^ 100 になるため、十分範囲が狭くなる！
- 16. Aggressive cows 農夫ジョンは、N個の牛舎を持つ小屋を作りました。各牛 舎は直線上に並んでおり、i番目の牛舎は位置xi にありま す。しかし、彼のM頭の牛達は小屋の配置が気に入らず、 とても攻撃的になってしまいました。ジョンは、牛達が 互いに傷つけあうのを防ぐため、他の牛とできるだけ離 れるように牛舎に入れることにしました。最も近い二頭 の牛の間の間隔を最大化しなさい。 制約: ● 2 ≦ N ≦ 100,000 ● 2 ≦ M ≦ N ● 1 ≦ xi ≦ 109
- 17. Aggressive cows 1 2 4 8 9 たとえば… N = 5, M = 3, x = {1, 2, 8, 4, 9} 最善で、(最も近い二頭の牛の間の間隔) = 3より、 答えは3 「最小値の最大化」問題！
- 18. Aggressive cows 条件 C(d) = 「最も近い二頭の牛の間隔をd以上にすることが できる」 を用意 (ソート前提) 。ちゃんと書けるようになろう
- 20. Monthly Expense 農夫ジョンは経理の達人です。彼は農場の運営でお金がなくなって しまうかもしれないことに気がつきました。彼はすでに、1日に必 要な金額vi を、今後N日にわたって正確に計算?記録しています。 ジョンは”fajomonths”というM期の会計期間に分けて予算を作ろう としています。会計期間は1日以上の連続する期間からなり、同じ 日が複数の会計期間に含まれることはありません。この 時、fajomonth中の出費の合計の最大値を最小化しなさい。 制約: ● 1 ≦ N ≦ 100,000 ● 1 ≦ M ≦ N ● 1 ≦ vi ≦ 10,000
- 21. Monthly Expense たとえば… N = 7, M = 5 100 400 300 100 500 400101 ↓ 100 400 300 100 500 400101 区間の項の和の最大値は500なので、答えは 500 「最大値の最小化」問題！
- 22. Monthly Expense 条件 C(x) = 「区間にある項の和がx以下になる 区間をM個作ることができる」を用意。
- 24. 平均最大化 重さと価値がそれぞれwi ,vi であるようなn個の品 物があります。この中からちょうどk個選んだ時 の単位重さあたりの価値の最大値を求めなさい。 制約: ● 1 ≦ k ≦ n ≦ 104 ● 1 ≦ wi , vi ≦ 106
- 25. 平均最大化 たとえば… n = 3, k = 2, (w, v) = { (2 , 2) , (5 , 3) , (2 , 1) } 答えは (2 , 2) , (2 , 1) の2つを選んだ時の 0.75 ※単位重さあたりの価値が大きい物から貪欲に とるのは間違い！
- 28. 平均最大化 さっきの式: これは、以下のように変形できる。 これならば(vi – x ? wi )の値でソートして貪欲に 選べるので、C(x) = 「(vi – x ? wi ) の大きい方 からk個の和が0以上」として解ける。
- 31. まとめ ? 二分探索でやりたいこと ? 解の存在範囲を半分に狭めていくことによって最適解 を求めたい！ ? どんな問題で二分探索が有効か？ ? 値の探索 (ソート済み配列、典型的な問題) ? 最小値の最大化 (Aggressive cows) ? 最大値の最小化 (Monthly Expense) ? ある条件下での最大化、最小化 (Cable master, 平均最大化) ? 終了条件は？ ? while(ub – lb > 1) パターン (配列操作、答えが整数) ? 二分探索の回数で判定するパターン (100回やれば十分)