TopCoder SRM 659 Div2 Med: PublicTransit

制限が5secな珍しい問題。ネスト深すぎなので分離すればよかったかな。

問題はこちら。

問題

R×Cの2次元セルがある。あるセルからは上下左右のセルにコスト1で移動できるとする。またテレポーターを1組置くことができ、片方のテレポーターからもう一方へコスト0で移動できる。テレポーターのあるマスに移動したときにはテレポーターを使うかそのままそのセルにとどまるか選択できる。任意のセル間の移動コストの最大値を最小化するようにテレポーターを設置したときの、最小化された移動コストの最大値を答えよ。

解法

2点間距離はワーシャルフロイドで求め、テレポーターの設置場所は重複の無い全探索をすればいい。
オーダーはO((RC)⁵)になるがR,Cが最大10で制限が5secなのでこれでも間に合う。
R = C = 1のコーナーケースに注意するのを忘れない。

const int inf = 1 << 28;
int dxy[] = {1, 0, -1, 0, 1};
class PublicTransit {
public:
    int minimumLongestDistance(int R, int C) {
        if (R == 1 && C == 1) return 0;
        int G[101][101];
        
        for (int y = 0; y < 101; y++)
            for (int x = 0; x < 101; x++) G[y][x] = inf;
            
        for (int y = 0; y < R; y++) {
            for (int x = 0; x < C; x++) {
                for (int i = 0; i < 4; i++) {
                    int nx = x + dxy[i], ny = y + dxy[i + 1];
                    if (0 <= nx && nx < C && 0 <= ny && ny < R)
                        G[x + C * y][nx + C * ny] = G[nx + C * ny][x + C * y] = 1;
                }
            }
        }
        
        int ans = inf;
        for (int y = 0; y < R / 2 + 1; y++) {
            for (int x = 0; x < C / 2 + 1; x++) {
                for (int cy = R / 2; cy < R; cy ++) {
                    for (int cx = C / 2; cx < C; cx++) {
                        if (x == cx && y == cy) continue;
                        int tmp = 0;
                        int g[101][101];
                        for (int r = 0; r < 101; r++)
                            for (int c = 0; c < 101; c++) g[r][c] = G[r][c];

                        g[x + C * y][cx + C * cy] = g[cx + C * cy][x + C * y] = 0;

                        for (int k = 0; k < R * C; k++) 
                            for (int i = 0; i < R * C; i++) 
                                for (int j = 0; j < R * C; j++)
                                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

                        for (int i = 0; i < R * C; i++)
                            for (int j = i + 1; j < R * C; j++)
                                if (g[i][j] < inf) tmp = max(tmp, g[i][j]);
                                
                        ans = min(ans, tmp);
                    }
                }
            }
        }
        return ans;
    }
};

まとめ

Div2Medにしては難易度高い方な気がする