Pの競プロ記

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

CODE FESTIVAL 2014 予選B D 登山家

概要

ある山脈にN個の山小屋が東西に一直線に並んでいる。それぞれの山小屋は標高H[i]に建てられている。

それぞれの山小屋から東西を見渡したときに、何個の山小屋が見えるか求めたい。

山小屋が見える条件は以下の通り。

  • 現在の山小屋をi、見たい山小屋をjとする
  • H[i]<=H[j]
  • 山小屋iと山小屋jの間にある山小屋をkとすると、全ての山小屋kに対してH[i]<=H[k]

http://code-festival-2014-qualb.contest.atcoder.jp/tasks/code_festival_qualB_d

解法

Donutsプロコンチャレンジ2015 C 行列のできるドーナツ屋 - ぱーぽーのぷろぐらみんぐ記
これの類題。

基本的に上の問題と似たようなやり方で解くことができる。

自分のいる山小屋から東西を見た時に、自分より高い山小屋が見つかるまでに見つけた山小屋は全て見ることができる。

だから自分の山小屋より高い山小屋の中で最も近いものを東西それぞれ1つずつ探すことができればよいことになる。

山小屋の高さをvector等で管理し、自分より高い山小屋が見つかるまで値を削除していく。
そのときに山小屋の位置も一緒に管理しておくことで、何個の山小屋を見ることができたかを簡単に求めることができる。

これを東から西へ、西から東への2方向から求め、それぞれの山小屋に対してその和をとれば良い。

ソースコード

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long int lli;
typedef pair<int, int> Pii;

int main() {
  // ios_base::sync_with_stdio(false);
  int N;
  cin >> N;

  vector<int> h(N);
  rep(i, N) cin >> h[i];

  vector<Pii> hut;
  vector<int> ans(N, 0);

  // 西から東へ
  rep(i, N) {
    while(hut.size() > 0 && hut.back().F <= h[i]) hut.pop_back();
    ans[i] = i;
    if(hut.size()) ans[i] -= (hut.back().S + 1);
    hut.push_back(mp(h[i], i));
  }
  
  hut.clear();
  reverse(h.begin(), h.end());

  // 東から西へ
  rep(i, N) {
    while(hut.size() > 0 && hut.back().F <= h[i]) hut.pop_back();
    ans[N - i - 1] += i;
    if(hut.size()) ans[N - i - 1] -= (hut.back().S + 1);
    hut.push_back(mp(h[i], i));
  }

  rep(i, N) cout << ans[i] << endl;
  
  return 0;
}