なんかC早解きで大幅にレートが上がってIGMになった。解く力はあまり上がってないので実感はない。
http://codeforces.com/contest/741/problem/A
問題
N頂点N有向辺のグラフがある。
i番の点はC[i]番の点に有向辺を張っている。
各頂点から、有向辺に沿ってT回移動することを考える。
各頂点頂点XからT回移動した到達点をYとしたとき、YからT回移動した場合にXに戻ってくるようにしたい。
最小のTを求めよ。
解法
まず全頂点が閉路上にない場合解はなし。
それ以外の場合、全頂点における移動回数の周期を求め、その最大公約数をAとすると、それが解。
ただし、Aが偶数なら半分にする。
int N; int C[1010]; int P[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>C[i], C[i]--; ll ret=1; FOR(i,N) { int cur=i; FOR(j,N+2) { cur=C[cur]; if(cur==i) { P[i]=j+1; break; } } if(j==N+2) return _P("-1\n"); if(P[i]%2==0) P[i]/=2; ret=ret/__gcd(ret,(ll)P[i])*P[i]; } cout<<ret<<endl; }
まとめ
まぁこれは定番か。