yukicoder : No.1355 AND OR GAME

これ系CodeforcesやCSAcademyで出そうな印象。
https://yukicoder.me/problems/no/1355

問題

整数Xと、N個の正整数P[i]が与えられる。
Xに対し、P[i]を順に以下のいずれかの処理を行える。

• X = X or P[i]
• X = X and P[i]
• X = P[i]

最終的にX=Yとすることができるか。
できるなら処理の一例を求めよ。

解法

後ろから順に、以降をandまたはor処理したときXに対し(1になるbit,0になるbit,変化しないbit)の組の集合を求めて行こう。
その際、後で復元できるように遷移元をたどれるようにしておこう。
この組み合わせはさほど数が増えない。

途中、P[i]に対し(1になるbit,0になるbit,変化しないbit)を適用するとYになるP[i]が見つかれば、そこをX=P[i]の処理を行い、あとは処理を復元するとよい。

int N;
ll X,Y;
ll A[202020];
map<pair<ll,ll>,pair<pair<ll,ll>,int>> M[202020];
int ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>X>>Y;
	FOR(i,N) cin>>A[i];
	M[N][{0,(1LL<<60)-1}]={{0,0},1};
	FOR(i,N) ret[i]=3;
	for(i=N-1;i>=0;i--) {
		FORR(m,M[i+1]) {
			ll o=m.first.first;
			ll a=m.first.second;
			if((Y&a)!=Y) continue;
			if((Y|o)!=Y) continue;
			if(((A[i]|o)&a)==Y) {
				i=i+1;
				while(i<N) {
					assert(M[i].count({o,a}));
					auto m2=M[i][{o,a}];
					o=m2.first.first;
					a=m2.first.second;
					ret[i]=m2.second;
					i++;
				}
				FOR(i,N) cout<<ret[i]<<" ";
				return;
			}
			//and
			ll am=(A[i]|o)&a;
			M[i][{o,am}]={{o,a},1};
			//or
			ll om=(A[i]&a)|o;
			M[i][{om,a}]={{o,a},2};
		}
	}
	FORR(m,M[0]) {
		ll o=m.first.first;
		ll a=m.first.second;
		if(((X|o)&a)==Y) {
			i=0;
			while(i<N) {
				auto m2=M[i][{o,a}];
				o=m2.first.first;
				a=m2.first.second;
				ret[i]=m2.second;
				i++;
			}
			FOR(i,N) cout<<ret[i]<<" ";
			return;
		}
	}
	cout<<-1<<endl;
	
	
}

まとめ

やりたいことは難しくないけど、実装がこんがらがる。