第n回情報

第n回情報 おしながき • 貪欲法(Greedy) • しゃくとり法 旭丘数理科学部 情報講義担当 たきかわ @cinnamon_cute_

まえがき

まえがき • あまりにもスライドを作らなさすぎて今回何回目か忘れま した。 • 次回以降n+1, n+2, n+3回…となっていきます。

貪欲法

貪欲法 • 貪欲とは…? • 非常に欲が深いこと。むさぼって飽くことを知らないこと。また、 そのさま。「貪欲に知識を吸収する」「貪欲な男」 デジタル大辞泉より • 情報科学では、 • 今できる一番良い動作をすること • 一番効率の良いものを選ぶこと • などが貪欲法に当たる

貪欲法 • 具体例 • 問題 : 金銭の支払い • しなもん王国の通貨には、 • 500円,100円,50円,10円,5円,1円の硬貨 • のみがが存在します。 • 今、6789円をお釣り無しで支払いたいとき、 • 最低何枚の硬貨を使用する必要がありますか？

貪欲法 • 回答 • 6789を高い硬貨から順に割っていく • 6789 / 500 = 13...289 • 289 / 100 = 2...89 • 89/50 = 1...49 • 49/10 = 4...9 • 9/5 = 1...4 • 4/1 = 4 • 計25枚

貪欲法 • 一見すると、貪欲法はとても応用範囲が広く、 • 多数の問題に対して活用できそうに見える。 • では、次のようなケースではどうだろう？

• 問題 : 金銭の支払い2 • しなもん王国の通貨には • 11円硬貨 7円硬貨 2円硬貨 • のみが存在します。 • クラス費として21円をお釣り無しで支払いたいです。 • 最低何枚の硬貨を使用する必要がありますか？

• 回答 • 21円を高い硬貨から順に割っていく • 21/11 = 1...10 • 10/7 = 1...3 • 3/2 = 1...1 • ……? • 払えない…

• 実際には人間でも解がすぐわかるが、 • (7*3 = 21より、3枚) • 貪欲法では解くことができなかった。 • なぜ…? • 1では、 「上位の単位 = k * 下位の単位」 で表せた。 • そのため、わざわざ下の単位の硬貨をk枚以上使うなら上位単位でOK • ２では、上位単位と下位単位が互いに素 • 上の単位も、下の単位もメリットが有り、どれを使えばいいかわからな い

貪欲法 • とりあえずいえること •ちゃんと証明してから使え！！！

貪欲法 • このように、きれいな性質を持っている場合以外 • 貪欲法は基本的に使うことができない • ただ、一見貪欲法が使えない問題に対して操作を加えるこ とで、最適解を出すことができるようになる • 最適解を出すことが難しい問題に対して近似解を出すこと が可能 • など、使える範囲は意外とある。

しゃくとり法

しゃくとり法 • 説明するより問題を出したほうが早いんで問題を出します

しゃくとり法 • 問題 • A = {1,9,8,3,7,4,7,3,6,4,0,8,1,6,9,1,1,0,3,7,5,8,1,6,5,8,0,9,2,4}(30) • の中から”連続する”部分列Sを取り出したとき、 • Sの要素の和 <= 15 • となるSの長さの最大値を求めよ • Ex. • 7~10を取り出すと、S = {3,6,4,0}(長さ4) , 和 = 13

アホ回答 for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ int sum = 0; for(int k = I; k < j; k++){ sum += A[k]; if(sum <= 15 && ans < j-1+1 ) ans = j – I + 1; } } } cout << ans << endl; //アホ

しゃくとり法 • (プログラミングやってない人向け) • Sの始点をi, 終点をjとおいて、中身を全部加算する • これがのサイズが、 • 15以下 かつ、 • 現在判明している最大サイズよりも大きい • 場合、最大サイズを更新する

アホ回答 • 𝑂(𝑁 3 )ですよ頭おかしいんですか？？？？？？？？？ • 人生をもう一度悔い改めて見直して来なさい。 • 私の講義に毎回来ている人は • 累積和だ！！！と思ったかもしれませんが、 • 「残念」です。 • (ちなみに累積和だと𝑂(𝑁 2 )になりますね)

しゃくとり法 • しゃくとり法を用いると、なんと𝑂(𝑁)まで軽くなります。 • どうやるの？ • 範囲の始点l, 範囲の終点rを持ち、 • 現在のsum+A[r+1]がKを超えるならば、 • lに+1をし、 • そうでないならば • rに+1をする。 • これをnまで繰り返す • 文だと非常に分かりづらいので図を使います。

しゃくとり法 • 簡単のために、N=10 , K = 5;の、 • A = {3, 1 ,1, 2, 2, 4, 1, 1, 1, 2} • という配列で考えます。 3 1 1 2 nowsum = 2 4 1 1 1 4 nowmaxsize =

• l,rを0に置きます l r 3 1 1 2 nowsum = 3 2 4 1 1 1 2 nowmaxsize = 1

• 3 + 1 <= 5 より、 r++ l r 3 1 1 2 nowsum = 4 2 4 1 1 1 2 nowmaxsize = 2

• 4 + 1 <= 5より、 r++ l r 3 1 1 2 nowsum = 5 2 4 1 1 1 2 nowmaxsize = 3

• 5 + 2 > 5 なので、 l++ l r 3 1 1 2 nowsum = 2 2 4 1 1 1 2 nowmaxsize = 3

• 2 + 2 <= 5 , r++ l r 3 1 1 2 nowsum = 4 2 4 1 1 1 2 nowmaxsize = 3

• 4+2 > 5 l++ l r 3 1 1 2 nowsum = 3 2 4 1 1 1 4 nowmaxsize = 3

• 3 + 2 <= 5 r++ l r 3 1 1 2 nowsum = 5 2 4 1 1 1 2 nowmaxsize = 3

• 5 + 4 > 5 l++ l r 3 1 1 2 nowsum = 4 2 4 1 1 1 2 nowmaxsize = 3

• 4 + 4 > 5 l++ l r 3 1 1 2 nowsum = 2 2 4 1 1 1 2 nowmaxsize = 3

• 2 + 4 > 5, l++ …って、あれ???? • 配列の範囲と和がおかしくなってしまいました… l r 3 1 1 2 2 nowsum = -2 4 1 1 1 2 nowmaxsize = 3

• こういうときは、lがrを超えないように、rも一緒に動かし ましょう • 2 + 4 > 5 , l++,r++ l r 3 1 1 2 nowsum = 4 2 4 1 1 1 2 nowmaxsize = 3

• 4+1 <= 5 , r++ l r 3 1 1 2 nowsum = 5 2 4 1 1 1 2 nowmaxsize = 3

• 5+1 > 5 ,l++ l r 3 1 1 2 nowsum = 1 2 4 1 1 1 2 nowmaxsize = 3

• 1+1 <= 5 ,r++ l r 3 1 1 2 nowsum = 2 2 4 1 1 1 2 nowmaxsize = 3

• 2+1 <= 5, r++ l r 3 1 1 2 nowsum = 3 2 4 1 1 1 2 nowmaxsize = 3

• 3+2 <= 5 , r++ l r 3 1 1 2 nowsum = 5 2 4 1 1 1 2 nowmaxsize = 4

• rが右端に到達したので終了！！！ l r 3 1 1 2 nowsum = 5 2 4 1 1 1 2 nowmaxsize = 4

しゃくとり法 • 計算量 • lを動かす回数 𝑂 𝑁 • rを動かす回数𝑂 𝑁 • 和を更新する回数𝑂 𝑁 • 和の更新にかかる時間𝑂 1 • 合計𝑂 𝑁 • すごい！！！！！！！

しゃくとり法 • 欠点 • バグらせやすい • バグらせやすい • バグらせやすい • • • • • 初期位置の処理 lがrを超えるときの処理 終端の処理 和を更新するときの処理 etc…

例題

例題 • Face the Right Way (POJ No.3276) • N頭の牛が一列に並んでいます。各牛は前か後ろのいずれ かを向いています。 • 農家ジョンは牛自動回転機を購入しました。 • この機械は、数Kを設定すると、1回の操作でK頭の牛の向 きを反転させることができます。 • すべての牛を前向きにするために必要な最小の操作回数M と、それを達成する最小のKを求めなさい。

例題 • 解説 • 黒板に書いて

例題 • N個の整数の数列{𝐴𝑖 }が与えられます • 𝐴𝑖 から連続する部分列𝑆を取り出す • 𝑆の総積 がK以下となるとき、 • 𝑆のサイズの最大は？ • 0 ≤ 𝑁 ≤ 2 ∗ 105 • 0 ≤ 𝐴𝑖 ≤ 104 • 0 ≤ 𝐾 ≤ 105

• 解説 • 基本は例題しゃくとりでいいです。 • 𝐴𝑖 = 0のときを考慮し忘れると...?

ご清聴ありがとうございました