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

意外とあっさり。
http://donuts-2015.contest.atcoder.jp/tasks/donuts_2015_3

問題

N人が順に１列に並んでおり、それぞれの身長はH[i]である。
x番の人がまえを向くと、1～(x-1)番の人が並んでいる。

しかし背の高い人より前にいる人のことは見えない。
より正確には、i＜j＜xとなるi,jにおいてH[i]＜H[j]であるとき、i番の人はx番の人から見えない。

各人が前に何人の人が見えるか答えよ。

解法

1～(x-1)番の人のうち、後ろから見える人の身長の集合をSとする。
x番の人からは|S|人分を見ることができる。

1～(x-1)番の人の後ろにx番の人が並ぶ場合、SからH[x]以下の要素をすべて取り除き、H[x]を追加する、ということを繰り返せばよい。
以下のコードではSをsetを使って管理しているが、スタックでも同じことができる。

int N;
set<int> S;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		_P("%d\n",S.size());
		while(!S.empty() && *S.begin()<x) S.erase(S.begin());
		S.insert(x);
	}
}

まとめ

最初もっとややこしいコードを書いてしまっていたが、書き直したらだいぶすっきりした。