ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

貪欲

CODE FESTIVAL 2014 予選B D 登山家

概要ある山脈にN個の山小屋が東西に一直線に並んでいる。それぞれの山小屋は標高H[i]に建てられている。それぞれの山小屋から東西を見渡したときに、何個の山小屋が見えるか求めたい。山小屋が見える条件は以下の通り。 現在の山小屋をi、見たい山小屋をjと…

Donutsプロコンチャレンジ2015 C 行列のできるドーナツ屋

概要N人が一列に並んでいて、それぞれの身長H[i]である。自分より前に何人見えるのかを知りたい。”見える”とは、以下の条件を満たす場合のことをいう。 自分がi番目に並んでいてj番目の人が見えるとき、j&lti 自分とj番目の人(身長H[j])の間にj番目の人より…