Pinely Round 3 : E. Multiple Lamps

変わった問題。
https://codeforces.com/contest/1909/problem/E

問題

1～N番のランプがある。
i番のスイッチを押すと、iの倍数の番号のランプが、点灯/消灯が入れ替わる。

加えて、「このボタンを押すならこのボタンも押してないとダメ」という条件が与えられる。

全体の1/5以上を点灯させるのに必要なボタンの押し方があれば、一例を答えよ。

解法

Nが20以上の時、全ボタンを押せばよい。
Nが19未満の場合、ボタンの押し方全パターンを列挙し、全体の1/5以上を押せるパターンを求めよう。
あとは、その中で同時に押すボタンの条件を満たすものを1つ選ぶと良い。

int T,N,M;
vector<int> E[202020],RE[202020];
int num[202020];

int mc[20];
int tmask[1<<19];


vector<int> ok[20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	/*
	cin>>N;
	int ret=0;
	for(i=1;i<=N;i++) {
		for(j=i;j<=N;j+=i) num[j]^=1;
		ret+=num[i];
		if(ret>i/5) cout<<i<<" "<<ret<<endl;
	}
	return;
	*/
	int mask;
	FOR(i,19) {
		for(x=i+1;x<=19;x+=(i+1)) mc[i]|=1<<(x-1);
	}
	FOR(mask,1<<19) if(mask) {
		int total=0;
		FOR(i,19) if(mask&(1<<i)) total^=mc[i];
		for(i=1;i<=19;i++) if(mask<(1<<i)) {
			int t=total&((1<<i)-1);
			if(__builtin_popcount(t)*5<=i) ok[i].push_back(mask);
		}
	}
	
	//for(i=1;i<=19;i++) cout<<i<<" "<<ok[i].size()<<endl;
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N+1) E[i].clear(),RE[i].clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
		}
		
		if(N>=20) {
			cout<<N<<endl;
			for(i=1;i<=N;i++) cout<<i<<" ";
			cout<<endl;
		}
		else {
			int must[22]={};
			for(i=1;i<=N;i++) FORR(e,E[i-1]) must[i-1]|=1<<e;
			int ret=0;
			FORR(cand,ok[N]) {
				
				FOR(i,N) if(cand&(1<<i)) if((cand&must[i])!=must[i]) break;
				if(i==N) {
					ret=cand;
					break;
				}
			}
			if(ret==0) {
				cout<<-1<<endl;
			}
			else {
				cout<<__builtin_popcount(ret)<<endl;
				FOR(i,N) if(ret&(1<<i)) cout<<i+1<<" ";
				cout<<endl;
			}
		}
		
		
		
	}
}

まとめ

本番結構苦戦してるな…。