Codeforces ECR #100 : F. Max Correct Set

シンプルな問題設定。
https://codeforces.com/contest/1463/problem/F

問題

整数N,X,Yが与えられる。
以下を満たす集合Sの最大サイズを求めよ。

• Sは1～Nの範囲の整数を含む
• Sから2要素取ったとき、その差がXまたはYとなることがない。

解法

ある値aをSに含めるかどうかは、P=X+Y周期で決めてよい。

f(s, mask) := (Pk+t) (0≦t＜s)のうちmaskに対応するtについてのみをSに含めるときの最大個数。
としてf(P,*)の最大値を求めればよい。

maskは実際にはO(2^P)通り取る必要はなく、sの直前O(2^max(x,y))個分だけ覚えておけばよい。

int N,X,Y;
int nseg[45];
ll from[1<<22];
ll to[1<<22];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	int mask;

	int P=X+Y;
	int rep=N/P,lef=N%P;
	FOR(i,P) {
		if(i<lef) nseg[i]=rep+1;
		else nseg[i]=rep;
	}
	
	FOR(mask,1<<22) from[mask]=-1<<28;
	from[0]=0;
	
	FOR(i,P) {
		FOR(mask,1<<22) to[mask]=-1<<28;
		FOR(mask,1<<22) {
			int nmask=(mask<<1)&((1<<22)-1);
			chmax(to[nmask],from[mask]);
			if((mask&(1<<(X-1))) || (mask&(1<<(Y-1)))) continue;
			chmax(to[nmask|1],from[mask]+nseg[i]);
		}
		swap(from,to);
	}
	
	ll ret=0;
	FOR(mask,1<<22) ret=max(ret,from[mask]);
	cout<<ret<<endl;
}

まとめ

1行目に気付くかどうかが鍵。
ECRの最終問にしては実装が軽め。