TopCoder SRM586 Div1 Mid History

はじめに

クソみたいな情報の知識しかないので、条件とか間違えてると思います

概要

サイト参照　幾つかの国があり、それぞれ何人かの国王が支配していた それぞれの国は独自の年号を持っている 国の国王が変わった年と、戦いの記録(ex. A国2人目の王とB国1人目の王が戦った) 戦いが与えられる(ex. C国2人目の王とB国1人目の王の戦い)ので、その戦いが起きた可能性があるかを調べる

入力形式がクソ(入力形式がクソ)

解法

界隈では牛ゲーと呼ばれているらしい、蟻本の最短経路の牛の例題の類題である
負閉路があるかを調べる問題に帰着できるが、解説が結構めんどくさい

解法は2つのプロセスに分けられる 1 入力からグラフへの変換(入力形式がクソ) 2 グラフに負閉路があるかを調べる 僕は2はワーシャルフロイド法を使いました、深く説明はしません

まず、A国とB国が戦ったという情報から、 A国の西暦1年を基準とした時のBの西暦1年のズレはは何年以上何年以下なら良いのか という情報が得られます

上図での、+1~+2という情報から、次のようなグラフを作ります

このグラフは最短経路を持ちます Aの西暦1年を基準としたBの西暦1年のズレをbと置くと(ex. Aの西暦2年=Bの西暦1年->b=+1) bの必要十分条件(たぶん)は b ≦ 2 b ≧ 1 Aを始点としたBの最短経路をb'と置くと(もちろん2ではあるが)、b'の必要条件(たぶん)は b' ≦ 2 b' ≧ 1 なぜなら、b'が2より大きければAから長さ2の道が延びている事に矛盾し、1より小さければAに長さ-1に道が延びている事に矛盾するから(負閉路が存在してしまう) この2つの条件が等しい事に気づくでしょう よって、b'が存在すればbも存在します(たぶん) bが存在するのにb'が存在しない場合は、グラフが分割されている場合ですが、これも含めてbが存在する必要十分条件はグラフに負閉路が存在しない事となります(たぶん) これを応用すると国の数が増えても大丈夫ですが、自分で考えてみてください(投げやり)

解答

const int INF = 1e9;
class History {
    public:
    string verifyClaims(vector<string> dynasties, vector<string> battles, vector<string> queries) {
        int d[50][11];
        int CN = dynasties.size(), EN;
        for (int i = 0; i < CN; i++) {
            istringstream ist(dynasties[i]);
            int j;
            for (j = 0; j < 50; j++) {
                ist >> d[i][j];
                if (ist.eof()) break;
            }
            EN = j+1;
        }
        int dis[50][50];
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 50; j++) {
                if (i == j) {
                    dis[i][j] = 0;
                } else {
                    dis[i][j] = INF;
                }
            }
        }
        string longS;
        for (int i = 0; i < battles.size(); i++) {
            longS += battles[i];
        }
        istringstream ist(longS);
        while (!ist.eof()) {
            char buff[100];
            ist >> buff;
            char c1, c2;
            int d1, d2;
            sscanf(buff, "%c%d-%c%d", &c1, &d1, &c2, &d2);
            int b1 = c1 - 'A', b2 = c2 - 'A';
            dis[b2][b1] = min(dis[b2][b1], d[b2][d2+1] - d[b1][d1] - 1);
            dis[b1][b2] = min(dis[b1][b2], d[b1][d1+1] - d[b2][d2] - 1);
        }
        string res;
        for (int i = 0; i < queries.size(); i++) {
            int disb[50][50];
            copy(dis[0], dis[0]+50*50, disb[0]);
            char c1, c2;
            int d1, d2;
            sscanf(queries[i].c_str(), "%c%d-%c%d", &c1, &d1, &c2, &d2);
            int b1 = c1 - 'A', b2 = c2 - 'A';
            disb[b2][b1] = min(disb[b2][b1], d[b2][d2+1] - d[b1][d1] - 1);
            disb[b1][b2] = min(disb[b1][b2], d[b1][d1+1] - d[b2][d2] - 1);
            for (int k = 0; k < CN; k++) {
                for (int l = 0; l < CN; l++) {
                    for (int j = 0; j < CN; j++) {
                        disb[l][j] = min(disb[l][j], disb[l][k] + disb[k][j]);
                    }
                }
            }
            int j;
            for (j = 0; j < CN; j++) {
                if (disb[j][j] < 0) {
                    res += 'N';
                    break;
                }
            }
            if (j == CN) {
                res += 'Y';
            }
        }
        return res;
    }
};