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問目はだいぶ楽。