WARush

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

SRM692 Div1 Easy "HardProof"

解法(一番早かった人のをカンニング)

通過する辺の重みにて、下回ってはいけない最小値ラインを決め打ちする。

辺それぞれの重みから、決め打ちした最小値を差し引く。

0 -> 1へ移動するために通る最大の重みの最小値
1 -> 0へ移動するために通る最大の重みの最小値
0 -> 2へ移動するために通る最大の重みの最小値
2 -> 0へ移動するために通る最大の重みの最小値
0 -> 3へ移動するために通る最大の重みの最小値
3 -> 0へ移動するために通る最大の重みの最小値
・・・
これらの最大値を取る(うーんとても分かりにくい説明だ・・)

これらをそれぞれの最小値ラインで行い、その最小値をとれば答え

事後

全点最短経路問題であるため、ワーシャル-フロイドさんを使うと効率が良い。
しかしそれでも計算量はO(50^5) = 3億超と微妙である。
Systestは一応1秒切ったから、単純な計算を3億回とかならSRM的には問題ないっぽい。

ソースコード

int f[55][55];
int g[55][55];

class HardProof {
    public:

    int minimumCost(vector<int> D) {
        int n = sqrt(D.size()) + 0.5;

        // サイズ1なら0
        if (n == 1) return 0;

        // f[i][j]にi->jへのコストを入れる
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = D[i * n + j];
            }
        }

        int INF = 200000;
        int ans = INF;

        // f[i][j]を最小値ラインとする
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                // 最小値ラインを加味してグラフを作成
                for (int u = 0; u < n; u++) {
                    for (int v = 0; v < n; v++) {
                        if (f[u][v] < f[i][j]) {
                            g[u][v] = INF;
                        } else {
                            g[u][v] = f[u][v] - f[i][j];
                        }
                    }
                }
                // 変形ワーシャル-フロイドさん
                for (int w = 0; w < n; w++) {
                    for (int u = 0; u < n; u++) {
                        for (int v = 0; v < n; v++) {
                            g[u][v] = min(g[u][v], max(g[u][w], g[w][v]));
                        }
                    }
                }
                // 0 -> 1へ移動するために通る最大の重みの最小値
                // 1 -> 0へ移動するために通る最大の重みの最小値
                // ・・・
                // の最大値をとる
                int cand = 0;
                for (int u = 1; u < n; u++) {
                    cand = max(cand, g[0][u]);
                    cand = max(cand, g[u][0]);
                }

                // それぞれの最小値ラインで算出したもので最小値を取る
                ans = min(ans, cand);
            }
        }
        return ans;
    }
};