kmjp's blog

競技プログラミング参加記です

Codeforces ECR #089 : E. Two Arrays

EとF,Gで難易度差があった回。
http://codeforces.com/contest/1366/problem/E

問題

整数列A,Bが与えられる。Bは昇順である。
Aをいくつかの連続部分列に分解し、各部分列の最小値をもとの順で並べた数列A'を考える。
A'=Bとなる分割の仕方はいくつか。

解法

Aについて、後ろからみて最小値を更新する要素のみを取り出した数列Cを考える。
まず、CはBを含んでいなければ解なし。

そうでない場合、C[i]=B[j]であるときは、Aを分解したi番目の部分列には、C[i-1]より大きい値を入れなければいけないので、部分列の左端を定めることができる。
よってその左端の分だけ、分割位置の候補として掛け合わせていく。

int N,M;
int A[202020],B[202020];
const ll mo=998244353;
int NG[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	
	int mi=(1<<30);
	vector<pair<int,int>> V;
	for(i=N-1;i>=0;i--) {
		if(A[i]>=mi) A[i]=1<<30;
		else {
			mi=A[i];
			V.push_back({A[i],i});
		}
	}
	reverse(ALL(V));
	if(V.size()<M) return _P("0\n");
	if(V[0].first!=B[0]) return _P("0\n");
	ll ret=1;
	j=0;
	for(x=1;x<M;x++) {
		j++;
		while(1) {
			if(j>=V.size()) return _P("0\n");
			if(V[j].first>B[x]) return _P("0\n");
			if(V[j].first==B[x]) break;
			j++;
		}
		(ret*=V[j].second-V[j-1].second)%=mo;
		
	}
	cout<<ret<<endl;
	
}

まとめ

今回なんでこんなF,Gの正答率低かったんだろ。