Codeforces #562 Div1 C. And Reachability

これはCの割には簡単。
https://codeforces.com/contest/1168/problem/C

問題

整数列Aが与えられる。
この整数列の部分列Pを考える。
この際隣接要素は2進数表記で1個以上同じbitが立ってないといけないとする。

以下のクエリに答えよ。

• 整数L,Rが与えられる。Pの部分列のうち先頭がA[L]で末尾がA[R]となるものが存在するか判定せよ。

解法

前処理として、PとしてAの各要素から開始したとき、あるビットが立った要素を含めるには最短でAのどの位置の要素を含めればよいか、を求めておこう。

あとは各クエリに対し、A[R]の各ビットを総当たりし、A[L]から開始したときそのビットが立つ要素をR以前に含められるか判定して、1個以上そのようなものがあるか確認すればよい。

int N,Q;
int A[303030];

int R[303030][20];
int la[20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,20) R[N][i]=la[i]=N;
	for(i=N-1;i>=0;i--) {
		FOR(j,20) R[i][j]=N;
		FOR(j,20) if(A[i]&(1<<j)) {
			
			if(la[j]!=N) {
				R[i][j]=min(R[i][j],la[j]);
				FOR(x,20) R[i][x]=min(R[i][x],R[la[j]][x]);
			}
			
			la[j]=i;
		}
	}
	
	while(Q--) {
		cin>>x>>y;
		x--,y--;
		FOR(i,20) if((A[y]&(1<<i)) && R[x][i]<=y) break;
		if(i==20) {
			cout<<"Fou"<<endl;
		}
		else {
			cout<<"Shi"<<endl;
		}
	}
	
	
	
}

まとめ

この回CとDの解けた人数の差が大きくて、Cが割と早く解けて助かった感じだ。