TopCoder SRM608: BigOEasy

どういう場合にパターン数が指数関数オーダーになるかというと、それは

• ある点に対して複数ループが存在する場合

という条件を満たすときになる。ループが１つしかない場合は、線形オーダーでしかパターンが増えないが、２つ以上ある場合はループで戻るたびに選択肢ができるため、指数関数的にパターンが増大することになる。

よって、各点からスタートしてもとの点に戻るような経路が２つ以上ないかどうかを探索すればよい。
以下のコードでは、複数ループが存在するどうかの判定にベルマンフォード風の動的計画法を使っている。

dp[i] := i にいる経路のパターン数

ただし、そのまま適用するとループ２周目以降の経路も重複して数えられてしまうので、元の地点も戻った時点で dp[start] に 0 を設定する必要がある。

また、この問題は、 Div1 Medium BigO の部分問題であるのため、そちらの解法を切り出しても解くことができる。

public class BigOEasy {
    bool HasMultiplePathLoop(string[] graph, int pos) {
        int n = graph.Length;
        var dp = new int[n];
        dp[pos] = 1;
        int loopPattern = 0;

        for (int loop = 0; loop < n; loop++) {
            var next = new int[n];
            for (int i = 0; i < n; i++) {
                if (dp[i] == 0) continue;
                for (int j = 0; j < n; j++) {
                    if (graph[i][j] == 'Y') {
                        next[j] += dp[i];
                        if (next[j] >= 10) next[j] = 10; // オーバーフロー防止
                    }
                }
            }
            loopPattern += next[pos];
            if (loopPattern >= 2) return true;
            next[pos] = 0; // ２周目以降をカウントしないようにここでリセット
            dp = next;
        }
        return false;
    }

    public string isBounded(string[] graph) {
        int n = graph.Length;
        for (int i = 0; i < n; i++) {
            if (HasMultiplePathLoop(graph, i))
                return "Unbounded";
        }
        return "Bounded";
    }
}