TopCoder SRM 584: Egalitarianism

ぐぐってみたら、Egalitarianism = 平等主義 だった。

市民同士の所持金の差の最大値は、市民同士の最短距離 * dに等しい。もしそれ以上になってしまうと、最短距離上の辺の「所持金の差」のうちの１つが d を上回ってしまう。

よって、市民同士の最短距離の中で最大のものが答えになる。
最短距離を求める方法はいろいろあるが、Warshall-Floydを使った場合は、distance [i,i] = 0 にしておかないと、最終的に distance[i,i] には最小のループの長さが入ってしまってそれが誤爆する場合があるので注意。

多次元配列では LINQ を使用しづらいが、Cast<int>() で IEnumerable<int>に変換することで最大値を求めることができた。

public class Egalitarianism {
    public int maxDifference(string[] isFriend, int d) {
        int n = isFriend.Length;
        var distance = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i, j] = isFriend[i][j] == 'Y' ? 1 : 1 << 28;
            }
            distance[i, i] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    distance[j, k] = Math.Min(distance[j, k], distance[j, i] + distance[i, k]);
                }
            }
        }
        int ans = distance.Cast<int>().Max();
        if (ans >= (1 << 28)) return -1;
        return ans * d;
    }
}