AtCoder ARC #127 : E - Priority Queue

こっちは短く書けた。
https://atcoder.jp/contests/arc127/tasks/arc127_e

問題

2種類の命令からなる命令列が与えられる。
この命令列と、整数N、集合Sを用いて以下の処理を行う。

• 命令列にそって以下の手順を行う。
  • 今の命令が1なら、1～Nのうち未出の整数を1つ選び、Sに加える
  • 今の命令が2なら、Sのうち最大値を取り除く

解法

1の命令に対し、1から順に値を選んでみることを考える。
その最終的なSを小さい順に並べた数列をAとする。

選ぶ値の順番を変えると、得られる正整数列Bは

• 単調増加である
• B[i]≦A[i]

であるものすべてである。
これはBの各要素を先頭から順に決めていくことで、O(N^2)で数え上げ可能。

int A,B;
int num[5050];
const ll mo=998244353;
vector<int> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	int cur=1;
	
	FOR(i,A+B) {
		cin>>x;
		if(x==1) {
			V.push_back(cur++);
		}
		else {
			V.pop_back();
		}
	}
	
	ll from[5050]={1};
	FORR(v,V) {
		ll to[5050]={};
		ll ret=0;
		FOR(i,v+1) {
			to[i]=ret;
			(ret+=from[i])%=mo;
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(i,A+1) ret+=from[i];
	cout<<ret%mo<<endl;
	
	
	
}

まとめ

割とすんなり。