WARush

SRMの結果とか、解けた問題のコードを書いていきます

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";
    }
};