貪欲法
最近は、ABC089
AtCoder Beginner Contest 089 - AtCoder
に参加しました。実装にあたふたしつつ、とりあえずA,Bの二問は解けました。
Cは、バグがうまくとれず解けませんでした。まだまだC++に慣れていない。
といいつつ、実際解説など見るとそもそも問題を勘違いしていたのでそれ以前の問題ですね。。。
問題を解く以前に、しっかり問題を読み込んで理解することが必要だと思いました。（慣れていないと案外これが難しかったりする）
そんなこんなで、強くなりたい！といろいろネットを漁っているとこんなものを見つけました。
ICPC Challenge | 実践的プログラミング (全学自由研究ゼミナール)
東大の競技プログラミングの大会に出ていくゼミ？のHPだそうで。そこに自学用の資料を発見しました。AOJのオンラインジャッジの問題を例に解説していく流れで構成されており、ヒントや回答の流れなども載っているので実装のテクニックも習得できそうな感じを受けます。（いうまでもなく実際に習得できるかは自分にかかっていますが）
ちょうど、そっけなさすぎでもなく、詳しすぎもせず、個人的にはなかなかちょうどいい粒度ではないかと感じ、さっそく読み進めています。
昨日はここの３．２「貪欲法」を少し読んでいました。
なかなか応用が利くレベルで理解できていない感じがします。とりあえず、何かの最小を求めるときに使えばよいのかな？
などと考えていたら、こんなページも見つけました。
上の記事の中から言える、貪欲法の特徴をいくつか。
・（解説の流れ上）動的計画法と対比させて書かれている→動的計画法と対比させることで理解が深まる？
・端的に言うと貪欲法とは、「適当な基準を用いて、局所的に最適なケースを連続して選択する」方法。そして、「貪欲法の方が（動的計画法よりも）単純で分かりやすく、しかも計算時間は非常に短い」。
・しかし、「貪欲法で最適な答えが求まる保証がない」。「貪欲法を用いて最適解が導けるケース」と「貪欲法では近似解しか導けないケース」の2通りが存在し、どちらであるかを見極めることは簡単ではないことも多い。
つまり、貪欲法を用いるべきかどうかは慎重になるべきということでしょう。もしかすると、貪欲法を使えるかどうかきちんと見極められる程度には問題の内容を深く理解する必要があるのかもしれません。
まだ貪欲法をきちんと解説できるには至っていない（のにまたこうやってブログを書いてしまう）のですがまた記事を更新できればいいなと思います。
とりあえず、動的計画法を勉強してみよう。
それにしても、先ほどとりあげた
このシリーズはAtCoderのchokudaiさんが学生時代に書かれたものなんですね。勉強になりそうだし積極的にレファレンスしていきたいと思います。
