SRM 405: AllCycleLengths
(問題概要)
有向グラフが与えられる(ノード数<=30)。
好きなところからスタートしてi回(i = 1, 2, ...)の移動後最初の地点に戻れるか。
各iに対して戻れるなら1戻れないなら0を並べたものを計算せよ。
ただし結果は以下の一番短くなるフォーマットで
010(110) (意味: 010110110110110... (010の後に110がループ)
(解法)
分からんので解説読んだ。
解説「ループの長さはそんなに長くないので、全通り試せ」
なんとなくループの長さ長くないとは思ってたけど、証明わからないからその発想には至らなかった…
#define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class AllCycleLengths { public: string findAll(vector <string> arcs); }; inline bool cango(vector<string> &arcs, int from, int to){ return arcs[from][to] == 'Y'; } string AllCycleLengths::findAll(vector <string> arcs){ const int n = arcs.size(); const int MAX = 1000; const int LMAX = 50; vector<int> ans(MAX); REP(i,n){ vector<int> flag(n); flag[i] = 1; REP(j,MAX + 1){ vector<int> next(n); if(j != 0 && flag[i]) ans[j - 1] = 1; REP(k,n) if(flag[k]){ REP(l,n) if(cango(arcs, k, l)){ next[l] = 1; } } flag.swap(next); } } stringstream ss; REP(i,MAX){ for(int len = 1; len <= LMAX; len++){ bool ok = true; for(int p = 0; i + p < MAX; p++) if(ans[i + p] != ans[i + (p % len)]) ok = false; if(ok){ REP(j,i) ss << ans[j]; ss << '('; REP(j,len) ss << ans[i + j]; ss << ')'; goto end; } } } end: return ss.str(); }