FよりEに手間取った。
https://codeforces.com/contest/1823/problem/E
問題
N頂点の無向グラフが与えられる。
全ての点の次数は2である。
ここで以下の2人ターン制ゲームを行う。
整数L,Rが与えられるので、自分のターンではL以上R以下の整数Kを選ぶ。
そして連結するK点を選んで削除する。
この操作が先に行えなくなった方が負けである。
両者最適手を取ると勝者はどちらか。
解法
長さL+R以上の閉路のGrundy数は0である。
そうでない場合長さnに対しn/Lが閉路のGrundy数となる。
int N,L,R; int vis[202020]; template<int um> class UF { public: vector<int> par,rank,cnt,G[um]; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<202020> uf; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>L>>R; FOR(i,N) { cin>>x>>y; uf(x-1,y-1); } int nim=0; FOR(i,N) if(uf[i]==i) { x=uf.count(i); if(x<L+R) nim^=x/L; } if(nim==0) { cout<<"Bob"<<endl; } else { cout<<"Alice"<<endl; } }
まとめ
これ考察そんな簡単かな…実験で解いてるのかな。
意外と解いてる人多いな。