SRM392 div1 medium
ループの中にあるかどうかを調べて、あとは数えるだけ。
#include <string> #include <vector> #include <iostream> #include <sstream> #include <algorithm> #include <cstdio> using namespace std; class RoundAboutCircle { public: int loopSize[200010]; int nextCell[200010]; int DFS(int k) { if(loopSize[k]!=-6) return loopSize[k]; else return loopSize[k]=DFS(nextCell[k])+1; } int maxScore(int N) { for(int i=1;i<=N;i++) { int s=0,t=i; while(t!=0) s+=t%10,t/=10; nextCell[i]=((i+s)%N==0)?N:(i+s)%N; } for(int i=1;i<=N;i++) loopSize[i]=0; for(int i=1;i<=N;i++) if(loopSize[i]==0) { int t=i; while(loopSize[t]==0) loopSize[t]=-2,t=nextCell[t]; if(loopSize[nextCell[t]]==-2) { int sz=0; while(loopSize[t]==-2) loopSize[t]=-4,t=nextCell[t],sz++; while(loopSize[t]==-4) loopSize[t]=sz,t=nextCell[t]; } t=i; while(loopSize[t]==-2) loopSize[t]=-6,t=nextCell[t]; } for(int i=1;i<=N;i++) if(loopSize[i]==-6) DFS(i); return *max_element(loopSize,loopSize+200010-1); } };