kmjp's blog

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

Codeforces #681 Div1 B. Identify the Operations

今年最後。
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;
	}
}

まとめ

今年もお疲れさまでした。