kmjp's blog

競技プログラミング参加記です

Codeforces #533 Div2 E. Helping Hiasat

これこそECRでいいんじゃないか…。
https://codeforces.com/contest/1105/problem/E

問題

自分の名前を変更できる、あるWebサービスがある。
自分のプロフィールを、計M人の友人が見に来るとする。

ここで、名前変更および友人のプロフィール閲覧の履歴が与えられる。
ある友人を満足させるとは、閲覧時に常に自身の名前が友人の名前と一致することである。

最適に名前を変更させた場合、満足する人数の最大値を求めよ。

解法

各友人に対し、閲覧直前の名前変更の契機の集合を持たせよう。
友人の対にたいし、この集合の積を考える。この積が空集合でない場合、両者を同時に満たすことはできない。

逆に、空集合なら両者を同時に満たすことができる。
あとは、そのような友人対に辺を張り、その最大クリークを求める問題となる。
Mは最大40なので、半分全列挙と高速ゼータ変換で間に合う。

int N,M;
set<int> V[101010];
map<string,int> mp;
ll ok[40];
int dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int pre=0;
	FOR(i,N) {
		cin>>x;
		if(x==1) {
			pre=i;
		}
		else {
			cin>>s;
			if(mp.count(s)==0) {
				x=mp.size();
				mp[s]=x;
			}
			V[mp[s]].insert(pre);
		}
	}
	
	FOR(x,M) {
		FOR(y,M) if(x!=y) {
			i=x,j=y;
			if(V[i].size()>V[j].size()) swap(i,j);
			r=1;
			FORR(v,V[i]) if(V[j].count(v)) {
				r=0;
				break;
			}
			if(r) ok[x] |= 1LL<<y;
		}
		ok[x] |= 1LL<<x;
	}
	int mask;
	for(mask=1;mask<1<<20;mask++) {
		ll ma=(1LL<<40)-1;
		FOR(i,20) if(mask&(1<<i)) ma &= ok[20+i];
		ma>>=20;
		if((mask&ma)==mask) dp[mask]=__builtin_popcount(mask);
	}
	FOR(i,20) {
		FOR(mask,1<<20) if(mask&(1<<i)) dp[mask]=max(dp[mask],dp[mask^(1<<i)]);
	}
	int best=0;
	for(mask=0;mask<1<<20;mask++) {
		ll ma=(1LL<<40)-1;
		FOR(i,20) if(mask&(1<<i)) ma &= ok[i];
		if((mask&ma)!=mask) continue;
		
		best=max(best,__builtin_popcount(mask)+dp[ma>>20]);
		
	}
	
	
	cout<<best<<endl;
	
	
}

まとめ

簡単ではあるけどちょっと安直で残念な回。