WAがもったいなかった。
http://arc079.contest.atcoder.jp/tasks/arc079_d
問題
N頂点N有向辺のグラフが与えられる。
各辺iはP[i]→iを結んでいるとする。
各頂点vに非負整数A[v]を振るとき、下記条件を満たす振り方は可能か。
- 辺でつながる頂点の両端は同じ値を持ってはいけない。
- 0≦x<A[v]となる各整数xについて、v→wに辺がありかつA[w]=xとなるものがなければある。
解法
出る辺のない頂点は値が確定するので、トポロジカルソートでそのような頂点は値を確定させていこう。
そうすると閉路中の頂点群は値を確定できない。
さて、両端が循環する数列についてDP等を行う定番テクとして、1箇所値を総当たりで確定させ、以後順次値を確定させていく手法がある。
今回もそれを使おう。
閉路中の頂点vを一つ選択する。
A[v]は実は以下の2つしか候補がない。
Sをvから辺をはられた閉路外の頂点wに置けるA[w]の集合とする。また、閉路内でvから辺を張った先の頂点をxとする。
- A[v]はSに含まれない最小の非負整数
- この時、A[x]はA[v]以外の値でなければならない
- A[v]はSに含まれない最小から2番目の非負整数
- この時、A[x]はSに含まれない最小の非負整数でなければならない
A[v]の値として上記2つを両方ためし、A[x]が条件を満たすか判定すればよい。
int N; int R[202020]; int G[202020]; set<int> S[202020]; int in[202020]; int dfs(int cur,int tar,int cand,int pre,int fir) { int hoge=0; while(S[cur].count(hoge) || hoge==cand) hoge++; if(R[cur]==tar) return (pre==-1 || pre==hoge) && (hoge!=fir); return dfs(R[cur],tar,hoge,pre,fir); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x; in[x-1]++; R[i]=x-1; } MINUS(G); queue<int> Q; FOR(i,N) if(in[i]==0) Q.push(i); while(Q.size()) { x=Q.front(); Q.pop(); G[x]=0; while(S[x].count(G[x])) G[x]++; y=R[x]; in[y]--; S[y].insert(G[x]); if(in[y]==0) Q.push(y); } FOR(i,N) if(G[i]==-1) { int cand=0,pre=-1; for(j=0;cand<2;j++) { if(S[i].count(j)) continue; if(dfs(R[i],i,j,pre,j)) return _P("POSSIBLE\n"); pre=j; cand++; } } _P("IMPOSSIBLE\n"); }
まとめ
ARCとはいえ、いつもより赤い参加者が少ない?