Codeforces ECR #140 : E. Algebra Flash

Eまでは割とすんなり解いてる。
https://codeforces.com/contest/1767/problem/E

問題

Nマスの双六があり、各マスの色が与えられる。色はM通りある。
1番のマスから、1マスまたは2マス前方へのジャンプを繰り返し、N番のマスに到達したい。

その際、各色のマスに対しコストが設定されており、ある色のマスに対応するコストを一度払うと、同色のマスにすべて移動可能となる。
N番のマスに到達可能な最小コストを求めよ。

解法

半分全列挙で解く。
隣接するマスのうちどちらかは必ず踏まなければいけない。
このことから、2色間に「このうちどちらかはコストを支払わなければならない」という条件が付く。

これをもとに半分全列挙しよう。
前半20色・後半20色のコスト支払い有無をそれぞれ総当たりする。
その際「前半20色の支払い有無を決めると後半のうち最低この色は塗らないといけない」という条件が決まるので、高速ゼータ変換の要領で、塗らなければならない後半の色を含むパターンの最小コストを当たっていこう。

int N,M;
int C[303030];
int X[55];
int A[55][55];
int S[1<<20],T[1<<20];
int need[1<<20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>C[i];
		C[i]--;
		if(i) A[C[i]][C[i-1]]=A[C[i-1]][C[i]]=1;
	}
	A[C[0]][C[0]]=1;
	A[C[N-1]][C[N-1]]=1;
	
	FOR(i,M) cin>>X[i];
	int mask;
	FOR(mask,1<<20) {
		ll sum=0;
		FOR(i,20) if(mask&(1<<i)) sum+=X[i];
		FOR(x,20) FOR(y,20) if(A[x][y]&&(mask&(1<<x))==0&&(mask&(1<<y))==0) sum=(1<<30)-1;
		S[mask]=sum;
		FOR(x,20) FOR(y,20) if(A[x][y+20]&&((mask&(1<<x))==0)) need[mask]|=1<<y;
		sum=0;
		FOR(i,20) if(mask&(1<<i)) sum+=X[i+20];
		FOR(x,20) FOR(y,20) if(A[x+20][y+20]&&(mask&(1<<x))==0&&(mask&(1<<y))==0) sum=1LL<<30;
		T[mask]=sum;
	}
	
	FOR(i,20) {
		FOR(mask,1<<20) if(mask&(1<<i)) {
			chmin(S[mask^(1<<i)],S[mask]);
			chmin(T[mask^(1<<i)],T[mask]);
		}
	}
	int ret=1<<30;
	FOR(mask,1<<20) ret=min(ret,S[mask]+T[need[mask]]);
	cout<<ret<<endl;
	
	
	
}

まとめ

こちらはすんなり解けて良かったね。