これこそ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; }
まとめ
簡単ではあるけどちょっと安直で残念な回。