TopCoder SRM 392 Div1 Medium RoundAboutCircle

問題

1〜Nの数字が円周上にならんでいる。
マークを使って次のような操作を行う。

• 数字ひとつにマークを置く。
• マークが置かれている数字の、各桁の和を求め、その分だけマークを進める。
• 同じ数字に2度訪れた時点で終了する。
• これまでに訪れた数字の個数が得点になる

このとき、得られる最大の得点はいくつか求めよ。

制約条件

N≦200000

方針

数字を頂点として、マークが移動する数字から数字へ辺を張ったグラフを考える。
ある数字がループに含まれていたら、その数字からスタートしたときの得点はそのループの大きさになる。

ループの外にある数字は、ループまでの距離+ループの大きさが得点になる。
なのでループ検出を実装すればよい。

自分の実装は、深さ優先探索をしながら、今までに訪問した頂点および、
訪問した頂点を何番目に訪れたかを記憶しておいて、
同じ頂点に2度きたらそこまでがループなので、訪問順からループに含まれる頂点の得点を決めるという感じ。

ソースコード

int N;
int d(int n){
  int res=0;
  for(;n;n/=10)res+=n%10;
  return res;
}
int sc[200001],ord[200001],q[200001],sz;
int calc(int n,int len){
  if(sc[n]>0)return sc[n];
  if(ord[n]>0){
    for(int i=sz-1;;i--){
      sc[q[i]]=len-ord[n];
      if(q[i]==n)break;
    }
    return sc[n];
  }
  ord[n]=len;
  q[sz++]=n;
  int tmp=calc((n+d(n+1))%N,len+1);
  if(sc[n]>0)return sc[n];
  return sc[n]=tmp+1;
}
class RoundAboutCircle {
  public:
  int maxScore(int N) {
    memset(sc,0,sizeof(sc));
    ::N=N;
    int ans=0;
    rep(i,N){
      ans=max(ans,calc(i,1));
      rep(j,sz)ord[q[j]]=0; //探索した頂点は訪問順を初期化
      sz=0;
    }
    return ans;
  }
};