今年最後。
https://codeforces.com/contest/1442/problem/B
問題
N要素のdistinctな整数列Aと、Aのうち異なるK要素からなる整数列Bが与えられる。
Aに対し、以下の手順をK回行うことでBを構築したとする。
- Aのある要素A[i]を選ぶ。
- A[i-1]またはA[i+1]のいずれかを(存在するなら)選び、Bの末尾に追加する
- AからA[i]を取り除き、空いた箇所を詰める。
Bを構築する操作手順を求めよ。
解法
j回目の手順を行う場合、AにおいてB[j]の両隣の要素を選ぶことができるので、基本的に手順毎に選択肢は2つある。
ただし、j回目以降にB中に隣の値が出る場合、j回目でそれを消してしまうことはできない。
そこで、「今後この値が使われるか」を管理し、そうでない両隣を選んでいくことにしよう。
int T; int N,K; int A[202020],B[202020],P[202020],Q[202020]; int NG[202020]; const ll mo=998244353; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>K; FOR(i,N) { cin>>A[i]; A[i]--; P[A[i]]=i; NG[i]=0; } set<int> ok; FOR(i,N) ok.insert(i); FOR(i,K) { cin>>B[i]; B[i]--; Q[i]=P[B[i]]; NG[Q[i]]=1; } ll ret=1; FOR(i,K) { x=Q[i]; ok.erase(x); auto it=ok.lower_bound(x); int num=0; if(it!=ok.end()&&NG[*it]==0) num++; if(it!=ok.begin()&&NG[*prev(it)]==0) num++; ret=ret*num%mo; } cout<<ret<<endl; } }
まとめ
今年もお疲れさまでした。