yukicoder : No.318 学学学学学

★３だけど実装は軽め。
http://yukicoder.me/problems/899

問題

N要素の数列A[i]が与えられる。
この数列をもとに別の数列B[i]を作る。

1～10^9の各tにおいて順に以下の処理を行う。

• A[i]=tとなるようなiの最小値をL(t),最大値をR(t)とする。
• そのようなiが存在する場合、その時、B[L(t)...R(t)]をtとする。

最終的なB[i]を出力せよ。

解法

まずAを一回なめ、map等で各数値が最後に出てくる位置を確認しよう。
次にsetを使いつつこの数列をもう1回舐めながらBを作成する。

このsetは、その時点を通過する段階で、B[i]=tとなる過程があるtを含む。
すなわちL(t)≦i≦R(t)であるようなtの集合とする。
とすると、B[i]はこのsetの最大値となる。

上記処理を整理すると、iごとに順に以下の操作を行えばよい。

1. setにA[i]を加える
2. B[i]はset中最大値を設定
3. iがA[i]の値が最後に出てくる位置であれば、setからA[i]を消す

int N,A[101010];
map<int,int> last;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], last[A[i]]=i;
	
	set<int> S;
	FOR(i,N) {
		S.insert(A[i]);
		_P("%d",*S.rbegin());
		if(last[A[i]]==i) S.erase(A[i]);
		_P("%c",(i==N-1)?'\n':' ');
	}
}

まとめ

最初A自体を更新していくのかと思ってタイムロス。
Aは上書きせず、あくまでBに上書きを繰り返すのね。