Google Code Jam 2022 Round 1B : A. Pancake Deque

ABはRound1Aより簡単な気がするけど、Cがしんどい。
https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd59d

問題

整数が入ったdequeが与えられる。
これらの両端のいずれかから数値を抜き出し、並べていくことで数列を作ることを考える。
各要素に対し、そのprefixのいずれよりも大きいような場合にスコアが1得られるとする。
総スコアの最大値を求めよ。

解法

両端のうち、先に大きい方を抜き出す利点はない。
なので、dequeの左右を見て小さい順に抜き出していけばよい。
左右同値の場合はどちらから抜き出してもよい。

int N;
int D[101010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	deque<int> D;
	FOR(i,N) {
		cin>>x;
		D.push_back(x);
	}
	int pre=0;
	int ret=0;
	while(D.size()) {
		if(D.front()<=D.back()) {
			if(D.front()>=pre) ret++;
			pre=max(pre,D.front());
			D.pop_front();
		}
		else {
			if(D.back()>=pre) ret++;
			pre=max(pre,D.back());
			D.pop_back();
		}
	}
	
	cout<<"Case #"<<_loop<<": "<<ret<<endl;
}

まとめ

1問目はだいぶ楽。