SRM 392 Div1 Medium RoundAboutCircle

問題

円周上にノードが配置してあり、時計回りに1からNまでの番号が振られている。数字iのノードからはiの各桁の数字の和だけ時計回りに進むことができる。あるノードからスタートして移動中にすでに訪れたノードについたら終わりとする。任意のノードからスタートできるとした時の最長の移動回数を求めよ。

N <= 200000

やりかた

個人的に好きな問題。

1から順に試行していく。過程で訪れたノードには印をつけておけばそれらのノードから出発するケースは考慮しなくていい。例えば1から始めれば1->2->4->8・・・と進むが、2から始めると2->4->8・・と同じ進み方になるので1から始めた時より長くなることは絶対ないから。
また、すでに訪れたノードにもう一度訪れると以降はずっといくつかの数字からなるループを回り出す。そのループの大きさをメモしておけば、ループをなす数字のノードに偶然訪れた場合、以降の計算を打ち切ることができる。

ループの大きさを計算するために、以下の処理を行った。
1周目：まだループしているかわからない。
2周目：すでに訪れたノードに訪れたためループしたことを検知、ループの大きさを計測していく(loop_cnt)
3周目：ループの大きさがわかったのでループをなすノード達にメモっていく
4周目：これ以降は調べない

大きさの判明したループに入ればそれまでの移動回数+ループサイズを求めればよいが、大きさを初めて計算する場合には訪問が1回目の時だけ計測していくようにする。

以下ソース。

int vis[200001];
int memo[200001];
int step[200001];
bool neednt[200001];

class RoundAboutCircle {
public:
  int maxScore(int N) {
    memset(step, 0, sizeof(step));
    memset(memo, -1, sizeof(memo));
    memset(neednt, false, sizeof(neednt));
    for(int i = 1; i <= N; i++){//各ノードからの移動数は前計算
      int t = i;
      while(t){
	step[i] += t % 10;
	t /= 10;
      }
    }
    int ans = 0;
    for(int i = 1; i <= N; i++){
      if(neednt[i]) continue;
     
      memset(vis, 0, sizeof(vis));
      int cnt = 0, loop_cnt = 0;
      int cur = i;
      while(1){
	vis[cur]++;
	neednt[cur] = true;
	if(memo[cur] != -1 && vis[cur] == 1){
	  cnt += memo[cur];
	  break;
	}
	if(vis[cur] == 4) break;
	if(vis[cur] == 3) memo[cur] = loop_cnt;
	if(vis[cur] == 2) loop_cnt++;
	if(vis[cur] == 1) cnt++;
	
	cur = (cur + step[cur]);
	while(cur > N) cur -= N;
      }
      ans = max(ans, cnt);
    }
    return ans;
  }
}

最悪ケースで1.4sほど

ところでここでいうループは複数個できるのだろうか。複数個できるものとして書いたが、ひとつの大きなループに収斂するようならもう少し短く書けそう。