Codeforces #208 Div2. C. Dima and Containers

CF208はDiv2なので後日練習のみ。
難易度はさほど高くないが、正解までかなりのWAを出してしまった。
http://codeforces.com/contest/358/problem/C

問題

0～10^5の数値が並んだコマンドが与えられるので、これらをstack,queue,dequeを使い、下記の手順で管理する。

• 0以外のコマンドに対して、その数値をstackにpush・queueに追加・dequeの両端のどちらかに追加、のいずれかを行う。
• 0に対して、stack,queue,dequeから最大１個ずつ値を取得することができる。

取得できる値の和が最大となるよう、コマンドに対する最適な操作を示せ。

解法

コマンド0が１回呼ばれるごとに３個まで数値が取れる。
コマンド0の回数が少ないと、コンテナに突っ込んだまま残る数値が出てしまう。

そこで、まずコマンドを１周たどり、「0が来るたびに上位３つの数値を取り除く」と考えて最終的に取り除くコマンドと、最後までコンテナに残る数値を求める。
次に、最終的に取り除く予定のコマンドはstack,queue,dequeの先頭に１個ずつ順に入れ、最終的にコンテナに残るコマンドはdequeの後ろに入れて放置すればよい。

int N,A[100001],B[100001];
vector<pair<int,int> > P;

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N){
		cin>>A[i];
		if(A[i]!=0) P.push_back(make_pair(A[i],i));
		else {
			sort(P.begin(),P.end());
			FOR(j,3) {
				if(!P.empty()) {
					B[P.back().second]=1;
					P.pop_back();
				}
			}
			P.clear();
		}
	}
	
	j=0;
	FOR(i,N) {
		if(A[i]==0) {
			_P("%d",j);
			if(j==3) _P(" popStack popQueue popFront");
			else if(j==2) _P(" popStack popQueue");
			else if(j==1) _P(" popStack");
			_P("\n");
			j=0;
		}
		else if(B[i]) {
			if(j==0) _P("pushStack\n");
			if(j==1) _P("pushQueue\n");
			if(j==2) _P("pushFront\n");
			j++;
		}
		else{
			_P("pushBack\n");
		}
	}
}

まとめ

なんか変な設定の問題だな。