atcoder.jp 解法 最大値の最小化と聞くと二分探索が思い浮かぶ。 そこで答えで二分探索できないか考えてみることにする。 修行なしでメンバーと食べ物を最適にマッチングするには、食べ物を昇順、メンバーを降順に並び替えて同じ番号を組み合わせれば良い。 …

atcoder.jp 木を切る問題が出ると二分探索を思い出す。 解法 データ構造に切断点の位置を挿入しながら、二分探索をする。 二分探索をして、切断点の左端と右端がどこかを高速に調べることができる。 二分探索をするにはソートされている必要があるので、挿入…

atcoder.jp 解法 s’を文字の配列とみて、前からイテレータを動し、tと一致する文字を１文字ずつ探すことを考える。 最小値を求めたいので、一回一回のイテレータの移動は小さい方がよい。 この最小の移動を高速に求めるには、事前処理＋二分探索が有効になる…

atcoder.jp 解法 DPがしたくなる見た目をしているが、O(NM)になって間に合いそうにない。 あまり気が乗らないのだが、貪欲法で解けないかどうか考えてみることにする。 報酬を最大化したいので、なるべく報酬が大きい労働を優先的に選択したくなる。 かつ、…

atcoder.jp 解法 類題1 蟻本にのっているAOJの問題。 poj.org 類題2 典型90問の1問目。 atcoder.jp 最大値の最小化をしろということなので、二分探索を考える。 探索する条件としては、「K以下の切断回数で答えをXにできるか？」 なぜK以下でよいかというと…

問題へのリンク 解法 区間の和を求めるということでまずしゃくとり法が思いついた。 全体の総和をsumとして、x = sum/10 とすると、区間の総和がx以上になるまで右端を動かし続け、x以上になった時点で区間の総和がsumと等しいかを確認すれば良い。 また、su…