yukicoder : No.2423 Merge Stones

難易度は高くないけど、AC数が少な目。
https://yukicoder.me/problems/no/2423

問題

N個の石が円周上に並んでおり、それぞれ魔力と色が与えられる。
隣接する石の色の差がK以下の時、2つの石を合成できる。
合成すると、魔力は元の石の魔力の和となり、色は元の石のいずれかの色を取れる。

最適な合成を行うと、1つの石で得られる魔力の最大値はいくつか。

解法

まずN要素の数列を2倍に伸ばし、円周の考慮を楽にしよう。
以下を考える。
dp(L,R,C) := L番目からR番目までを合成し、色Cの1つの石を作れるかどうかの真偽値
これはR-Lの小さい順に求めて行けば、P(N^3*max(C)*K)で求めることができる。
max(C)が50以下と小さいことを利用し、bitmaskで表現して高速化しよう。

int N,K;
ll A[606],C[605];
ll mask[606][606];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>C[i];
	ll ma=0;
	FOR(i,N) {
		A[i+N]=A[i];
		ma=max(ma,A[i]);
		mask[i][i+1]=mask[i+N][i+N+1]=1LL<<C[i];
	}
	for(int len=2;len<=N;len++) {
		for(x=0;x+len<=2*N;x++) {
			for(int sl=1;sl<len;sl++) {
				FOR(k,K+1) {
					mask[x][x+len]|=mask[x][x+sl]&(mask[x+sl][x+len]<<k);
					mask[x][x+len]|=mask[x][x+sl]&(mask[x+sl][x+len]>>k);
					mask[x][x+len]|=(mask[x][x+sl]>>k)&mask[x+sl][x+len];
					mask[x][x+len]|=(mask[x][x+sl]<<k)&mask[x+sl][x+len];
				}
			}
			if(mask[x][x+len]) {
				ll sum=0;
				FOR(i,len) sum+=A[x+i];
				ma=max(ma,sum);
			}
		}
	}
	cout<<ma<<endl;
	
	
}

まとめ

割と短く書けた。