Pの競プロ記

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

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

概要

N人が一列に並んでいて、それぞれの身長H[i]である。

自分より前に何人見えるのかを知りたい。

”見える”とは、以下の条件を満たす場合のことをいう。

  • 自分がi番目に並んでいてj番目の人が見えるとき、j<i
  • 自分とj番目の人(身長H[j])の間にj番目の人より身長の高い人kがいない。
    • j<k<i、H[j]<H[k]を満たすkは存在しない。

例えば、身長2,5,3,4,1の5人が並んでいたとする。
身長1の人は身長5,4の2名を見ることができる。

N人それぞれが自分より前に何人いるか求めよ。

http://donuts-2015.contest.atcoder.jp/tasks/donuts_2015_3

解法

知っている人は一瞬で解けるっぽい問題。

人の列をstackやvector,set等で管理する。
i番目の人に着目しているとき、それより前にいる人で自分より小さい身長を人を削除していく。(自分より後ろに並んでいる人は自分より身長の低い人は見れない)
これを繰り返していけば良い。

ソースコード

#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;

  stack<int> H;
  rep(i, N) {
    int h;
    cin >> h;

    cout << H.size() << endl;
    while(!H.empty() && H.top() < h) H.pop();
    H.push(h);
  }
  
  return 0;
}

余談

DonutsプロコンやSHIROBAKOの影響で非常にドーナツを食べたくなっていたので、今日ミスドに行ってドーナツ食べました。

どんどんドーナツどーんといこー