SRM 405 Div1 Medium AllCycleLengths

問題

連結な有向グラフが与えられる。ある頂点から再びその頂点に戻るような長さxのパスが存在するときxはvacation friendlyであるという。途中で頂点に一度戻るようなパスも可とする。
xを1から無限まで調査し、vacation friendlyなら1、そうでないなら0とする数列を作る。数列は途中から周期的になるのでその部分については()で挟んで全体の長さが最短になる形で出力せよ。
たとえば010110111111111・・・は010110(1)や01011011(11)などと書けるが、この場合出力するべきは前者の表現となる。

やりかた

Editorialを参考にしました。
グラフがそれほど大きくないので虱潰しでいけるそうだ。各頂点についてxを1000くらいまで調べてみてvacation friendlyの数列を更新していき、調べ終わったら周期を調べていく。

以下ソース。

const int NUM = 1000;
bool reach[51][NUM + 10]; //reach[i][j] 頂点iにj回の移動でたどり着くか

class AllCycleLengths {
public:
  string findAll(vector <string> arcs) {
    int N = arcs.size();

    bool xholiday[NUM + 1] = {false}; //vacation friendlyの数列

    for(int i = 0; i < N; i++){//頂点iから出発するケースを探索
      memset(reach, false, sizeof(reach));
      reach[i][0] = true;
      for(int j = 0; j <= NUM; j++){
	if(reach[i][j]) xholiday[j] |= true; //頂点iはj-day vacation
	
	for(int k = 0; k < N; k++) 
	  if(reach[k][j])
	    for(int l = 0; l < N; l++)
	      reach[l][j + 1] |= (arcs[k][l] == 'Y');
      }
    }

    int start = 1;
    string ans;
    while(1){
      for(int w = 1; w <= (NUM - start) / 2; w++){//周期長
	bool canon = true;
	for(int j = start; j < NUM; j++)
	  if(xholiday[j] != xholiday[(j - start) % w + start])
	    canon = false;
	
	if(canon){
	  ans.push_back('(');
	  for(int k = 0; k < w; k++) 
	    ans.push_back(xholiday[k + start] ? '1' : '0');
	  ans.push_back(')');
	  return ans;
	}
      }
      ans.push_back(xholiday[start] ? '1' : '0');
      start++;
    }
    return ans;
  }