SRM608 Div2 Hard "BigOEasy"
問題
TopCoder Statistics - Problem Statement
訳
猫のスヌークはプレゼントとして有向グラフを受け取った。
あなたはString[] graphが与えられる。graphの要素数は、彼が受け取ったグラフの頂点の数を表している。もしi番目の頂点からj番目の頂点へ、辺が伸びていた場合、graphのi番目の文字列のj番目の文字は'Y'となってる。辺がない場合、'N'となっている。
スヌークは、このグラフにおいて、距離L(Lは巨大)の歩き方はどれほどになるのか知りたくなった。Lだけ歩くとき、その方法(道筋の辿り方)の数は、はたしてLの多項式で表せるのか?表せるのであれば"Bounded"を、表せなければ"Unbounded"を返せ。
ほそく
距離Lの歩き方の数のオーダーが、O(L^n)に収まればオーケー らしい
考えたこと
i番目の頂点にスヌークがいたとして、もし道が二股に分かれていたとする。で、どっちの道を進んでもi番目の頂点に戻れたとする(いわゆる閉路になっている)。そうすると、2通りの歩き方がO(L)回だけ選択できるため、オーダーはO(2^L)となってしまう。
逆にそういった頂点がなければ、多項式に収まる。説明は以下にTopCoder SRM 608 Division II Level Three : BigOEasy - quniomの日記
実装としては、
1. ワーシャルフロイド法を変形して直接辺で繋がっていない2頂点について、到達することができれば'Y'としてグラフを更新する。
2.i -> jとなる道筋があって、j -> iとなる道筋がある。i -> kとなる道筋があって、k -> iとなる道筋がある。そんなiを探して、あればUnbounded
ソースコード
class BigOEasy { public: string isBounded(vector <string> graph) { int size = graph[0].size(); vector <string> G = graph; // ワーシャルフロイド法でグラフを更新する while (true){ bool update = false; for (int s = 0; s < size; s++){ for (int i = 0; i < size; i++){ if (G[s][i] == 'N') continue; for (int t = 0; t < size; t++){ if (G[i][t] == 'Y' && G[s][t] == 'N') { G[s][t] = 'Y'; update = true; } } } } if (!update) { break; } } // 複数の閉路に属している頂点がないか調べる。 bool bounded = true; for (int s = 0; s < size; s++){ int cnt = 0; // 頂点sが属す閉路の数 for (int t = 0; t < size; t++){ if (graph[s][t] == 'Y' && G[t][s] == 'Y'){ cnt++; } } if (2 <= cnt){ bounded = false; } } return bounded ? "Bounded" : "Unbounded"; } };