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の正答率低かったんだろ。