Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋
Page content
このサイトはブログを書く練習用に作成されました．
問題概要
- Link
- \(n\)要素の数列\(h\)が与えられる．各\(i(0\leq i < n)\)について、\(0\leq j < i\)かつ、\(j < k < i\)を満たす全ての\(k\)について\(h_{j} > h_{k}\) を満たすものの個数を求めよ．
解法
まず、\(O(N^2)\)での解法を考える．
- \(i\)番目の要素について考えたときに、\(i-1\)番目の要素から順に、自分より左にあり、自分より高い要素に移動していくことを考えると、この移動回数(\(i-1\)への移動も1と数える)が答えである．
- よって、\(i-1\)から初めて、最大値を保持しながら左の要素を見ていけば\(O(N^2)\)で計算できる．
次に、上の解法の計算量を改善することを考える．
- 自分より左にあって自分より高い要素を順に全て数えていくのは無駄で、自分の左にある次に大きい要素が\(k\)番目だとすると、答えは\(k\)番目の答えに1を足したものになる．
- あとは自分より左にあって自分より大きい最左の要素が分かればよく、セグメントツリーかsetを用いて、大きい要素から見ていけば達成できる．