不等式と貪欲法について
こんにちは御室戸斉部のsyamu好きです。今回は本の感想でも何かの参加記でもなく、まあ強いて言えば本の感想ですがある本(この記事の末にでも貼っておきます)の中に出てきた話で競プロとの親和性も高そうな話があったので紹介兼自分が後で見返すよう見たいな感じでいきます。
なお当記事の目的は貪欲法と呼ばれるアルゴリズムを使って初等的な不等式を見てみようというものです。
貪欲法とは
本題に入る前に貪欲法についてすこし説明します。なので知ってる人は飛ばしていただいて。貪欲法はもとGready Algorithmと英語で言ってどのようなアルゴかと申しますと例えば問題として以下のようなものを解決する際に出てくる考え方です。
【問題】
10000円札が 3 枚、5000円札が 5 枚、2000円札が 5 枚、1000円札が 4 枚あります。この中から合計で 4 枚貰えるとします。一番多くもらえていくらでしょうか。
というような問題があるとすればほとんどの人は迷わずに10000円札 3 枚と5000円札 1枚貰えば最多のお金、35000円を獲得できると答えられますよね。これは全通り試せばわかりますがそうでなくても大きい金額のお札をより多くもらう方がより多くの金額を得られるというのは感覚的にありますね。では次の問題はどうでしょうか。
【問題】
数列A={1,3,2,4}、数列B={5,1,7,3}があります。数列A,Bはそれぞれの数列内での要素の入れ替えは可能です（1≦i,j≦4の任意のi,j（整数）についてswap(ai,aj)が認められています）。いまnについて 1から 4まででanとbnの積の和の最大値・最小値は何ですか
要するに↑これの最大・最小値はなんぼですか？
これは数列AをA={1,2,3,4}、BをB={1,3,5,7}としてともに昇順に並び替えたものを前から積を取っていったものが最大となります。つまり最大は1*1+2*3+3*5+4*7=50ですね。これも全通り試せば最大値が50だとわかります。ではなぜ昇順でソートされたものが最大になるかですが、これを前問と合わせて考えますと「大きいものをできるだけ多くとる」ことが見えてきますね。感覚的にも大きいものを多くとっていくと結果も大きくなりそうだというのが分かります。このような思考を貪欲法と言います。ちなみにこの問題の最小値ですがそれはAをA={1,2,3,4}、B={7,5,3,1}としてそれぞれを昇順と降順に並べ替えたものを前から積を取っていくことで得られます。最小は1*7+2*5+3*3+4*1=30ですね。これは言わずもがなAを降順、Bを昇順にソートした結果でも同じです。この場合も貪欲法で説明がつき、「大きいものをできるだけ少なくとる」と結果も少なくなるだろうというわけです。これも貪欲法の一つの形態です。これらは一般にn個の要素数を持つ数列A,Bに対しても以下の式が成り立ちます。証明をする気はないです。
（ただしpi,qiはA,Bをそれぞれ昇順にソートした際の添え字）
以上が貪欲法のおおざっぱな紹介です。この思考法は競技プログラミングでもよく出てくるので覚えておくと吉。
初等的な不等式をGreadyに説明する
さて次は不等式ですがそれぞれ出てくる文字は正の実数としておきます。以下のような不等式は有名不等式なので知ってる人も多いと思われます。右端が不揃いなのは目を瞑っていただきたい。
......1
......2
......3
......4
......5
として番号を振ってそれぞれ言及します。1などは典型的な相加平均相乗平均の関係式、またそれ以外の不等式もどっかしらで見たことがあるような不等式ですね。全て成り立ちます。当ブログでは例によって初等的な証明はのっけません。証明を知りたい場合はググるなどしてください。さて。
1の相加相乗の不等式ですが要素が√aと√bの二つで構成された数列を２つ考えます。具体的にはA={√a,√b},B={√a,√b} としてみると分かりやすいですか。この時、A,Bの要素の積の和（うえの問題で考えたようなこと）を考えます。ここでa≦bとしておきますと最大の値は貪欲法的に
このようにしてa+bだとわかりますね。最大値がこれなのでほかのどのような積の取り方であってもa+bをこえることができないわけです。まあ今回の場合は要素数が2つなのでこれ以外の取り方は√(ab)+√(ab)=2√(ab)以外なく、当然それらは貪欲法的に考えてa+bより小さくあるべきなので不等式は成り立ちます。
2も同様に見ればa≦b≦cとして一般性を失わず、Greadyに考えてa^2+b^2+c^2が最大であるとわかります。あ～等号の成立条件などは面倒なので述べません。
3は少しわかりにくいですがやはりa≦b≦cとしてみると
となるので今度は最小値の貪欲法を用いれば
最小値として3abcがなりたり、どのような組み合わせであれこれ以上にはなるわけですね。
4は3の別バージョンで最大値を取ります。解説は繰り返しますがa≦b≦cとしてみると
がなりたつので
最大値が以上のようになりどの組み合わせをとってもこれより大きくなることはないです。３，４はいずれもそのまんまをすればできる話でしたね。
5ですが、これは少々前処理がいります。a≦b≦cとしても一般性を失わず
この不等式がなりたち、因ってその逆数は
こんなかんじで不等号の向きが逆になった関係式をなします。これとa≦b≦cとを考えることで最大値の貪欲法で
こんなかんじで最大値をMとおくと、Mはどの様な組み合わせの式に対してもそれ以上の値であるので以下の二式がなりたち
これらを両辺足すことで
よって
このようにして不等式が導けましたね。言うまでもないですがこれはしっかりとコーナーケースまで詰めた証明ではありません。でかでかと書いておきましたがあくまでも説明なのでまあはい。
おわりに
今記事はじめてパソコンで書いているんですがめっちゃ書きやすくて感動しています。今回画像が記事内で使われていたり文字の大きさが変わっているのもそのためです。良い感じなのでこれからもパソコンで書いていきたいが。さてブログの内容としてはどうだったでしょうか。競プロerによっている僕としては数学野で貪欲法が使えると思っていなかったためこれを知った時結構新鮮でした。コンテストで出題されたらだいたいさっさと通してしまいそうな問題でしたが（300くらいかな）実際の不等式を証明説明するにはかなり強力だなと思いました。実際貪欲法は競プロ野でもかなり強力なアルゴであることは否めんけど空気みたいなレベルで使ってるから案外そのすごさ分からんよね。そういえば蟻本でも最初の方に書いてあるし。蟻本でにぶたんよりもDPのが先に載ってんのちょっと解せんけどまあいいや。
それではまた。PCK参加記も近いうちに書く気がします。あとこの記事どっか間違ってそうなところがあったら教えてください
追記：この記事を書くにあたって『解法へのアプローチ』栗田哲也・東京出版の第6章「欲張り者の不等式」を参考にしました。Amazonのリンク→
