提出 #44634563

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 51;
const int M = 1<<18;

ll n,l;
string s,t;
ll to[M][2][2];
ll dp[N][M];

void init(){
	// to_{msk,a,b}: you have msk, you want to get one a, you add b.
	for (ll msk=1; msk<(1<<l); msk++){
		ll len=0;
		while ((msk^(1<<len))>(1<<len)){
			len++;
		}
		len--;
//		de(len);
		// len=msk: first 1
		ll cur=len;
		while (~cur && (msk&(1ll<<cur))>0){
			cur--;
		}
//		cout<<"0: "<<cur<<endl;
		if (~cur){
			to[msk][0][0]=((msk&((1ll<<cur)-1))^(1ll<<cur));
			to[msk][0][0]<<=1ll;
			to[msk][0][1]=to[msk][0][0]^1;
		}
		cur=len;
		while (~cur && (msk&(1ll<<cur))==0){
			cur--;
		}
//		cout<<"1: "<<cur<<endl;
		if (~cur){
			to[msk][1][0]=((msk&((1ll<<cur)-1))^(1ll<<cur));
			to[msk][1][0]<<=1ll;
			to[msk][1][1]=to[msk][1][0]^1;
		}
//		cout<<msk<<": "<<to[msk][0][0]<<","<<to[msk][0][1]<<","<<to[msk][1][0]<<","<<to[msk][1][1]<<endl;
	}
}

void print(ll x){
	ll len=0;
	while ((x^(1ll<<len))>(1ll<<len)){
		len++;
	}
	len--;
	for (ll i=len; i>=0; i--){
		int t=(x>>i)&1;
		if (t){
			cout<<"X";
		}
		else{
			cout<<"Y";
		}
	}
	cout<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

//	freopen("denverjin.in","r",stdin);
//	freopen("denverjin.out","w",stdout);
	cin>>n>>s>>t;
	l=(n+2)/3+1;
	init();
	// push
	dp[0][1]=1;
//	de(l);
	for (int i=0; i<n; i++){
		for (int msk=0; msk<(1ll<<l); msk++){
			if (dp[i][msk]==0){
				continue;
			}
			if (s[i]=='X' && t[i]=='X'){
				// use this
				dp[i+1][1]=max(dp[i+1][1],dp[i][msk]<<1ll|1);
				if (to[msk][1][1]!=0){
					// use before
					dp[i+1][to[msk][1][1]]=max(dp[i+1][to[msk][1][1]],dp[i][msk]<<1ll|1);
				}
				if (msk<(1<<l-1)){
					// no use
					dp[i+1][msk<<1ll|1]=max(dp[i+1][msk<<1ll|1],dp[i][msk]);
				}
			}
			else if (s[i]=='Y' && t[i]=='Y'){
				// use this
				dp[i+1][1]=max(dp[i+1][1],dp[i][msk]<<1ll);
				if (to[msk][0][0]!=0){
					// use before
					dp[i+1][to[msk][0][0]]=max(dp[i+1][to[msk][0][0]],dp[i][msk]<<1ll);
				}
				if (msk<(1<<l-1)){
					// no use
					dp[i+1][msk<<1ll]=max(dp[i+1][msk<<1ll],dp[i][msk]);
				}
			}
			else{
				// use x
				if (to[msk][1][0]!=0){
					dp[i+1][to[msk][1][0]]=max(dp[i+1][to[msk][1][0]],dp[i][msk]<<1ll|1);
				}
				// use y
				if (to[msk][0][1]!=0){
					dp[i+1][to[msk][0][1]]=max(dp[i+1][to[msk][0][1]],dp[i][msk]<<1ll);
				}
				// no use
				if (msk<(1<<l-1)){
					dp[i+1][msk<<1ll]=max(dp[i+1][msk<<1ll],dp[i][msk]);
					dp[i+1][msk<<1ll|1]=max(dp[i+1][msk<<1ll|1],dp[i][msk]);
				}
			}
		}
	}
	ll mx=0;
	for (int msk=1; msk<(1ll<<l); msk++){
		mx=max(mx,dp[n][msk]);
	}
//	de(mx);
	print(mx);
	return 0;
}

// don't waste time!!!

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:93:18: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
   93 |     if (msk<(1<<l-1)){
      |                 ~^~
./Main.cpp:105:18: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
  105 |     if (msk<(1<<l-1)){
      |                 ~^~
./Main.cpp:120:18: warning: suggest parentheses around ‘-’ inside ‘<<’ [-Wparentheses]
  120 |     if (msk<(1<<l-1)){
      |                 ~^~

ジャッジ結果