yukicoder : No.930 数列圧縮

地味に手間取りそう。
https://yukicoder.me/problems/no/930

問題

1～NのPermutationである数列Aが与えられる。
隣接する2要素を選択し、左側が右側より小さいときに、好きな片方を消す、という作業を繰り返す。
数列長を1にする手順が存在するならば答えよ。

解法

A[0]＜A[N-1]なら解がある。
まずstackにA[0]～A[N-2]を積んでいくことを考える。
この際、新たに積んだ方の値が、stackのtopより大きいなら、積まずに消す。
そうすると、stackに残る値はいずれもA[0]以下である。

ということは残されたA[N-1]より小さいので、A[N-1]に近い順に全部消していける。

int N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	if(A[0]>A[N-1]) return _P("No\n");
	cout<<"Yes"<<endl;
	vector<int> V;
	V.push_back(A[0]);
	for(i=1;i<N-1;i++) {
		if(V.back()<A[i]) {
			cout<<A[i]<<" ";
		}
		else {
			V.push_back(A[i]);
		}
	}
	while(V.size()) {
		cout<<V.back()<<" ";
		V.pop_back();
	}
	
}

まとめ

本番これさっと思いつける気がしないなぁ。