SRM586 Div1 Medium "History"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12692

訳

N個の古代国家があった。この国々を、大文字のアルファベット'A'から'A' + N - 1で表す事にする。（'A' + 1 = 'B', 'A' + 25 = 'Z')

全ての国家は同じカレンダーを使用していた。つまり、それぞれの国家で、同じ日で新しい年が始まっていた。しかし、それぞれの国家で、年数は独自のものだった。例えば、国家Aにおいて、47, 48, 49年は、国家Bでは123, 124, 125年に対応していたりした。

それぞれの国家では、その歴史において、幾人かの君主が統治していた。各国家において、君主は年代順に、0から番号付けされている。例えば、"C0"は国家Cで一番初めに統治していた君主の時代を表す。各君主は年の最初の日から統治を始めている。各君主が統治をし始めた（その国における）年が、正確に分かっている。

マナオはこれらの国々の年代が、互いにどのように対応しているのかを解明したい。これを行うにあたり、彼は歴史上のさまざまな戦争についての情報を集めた。それぞれの戦いは、２つの国家間で行われていた。例えば、"C0-D3"と言う情報は、"C0"と"D3"で戦いが起こっていたことを意味する。この戦争があったという情報は、"C0"と"D3"の２つの君主が、同じ年に統治していた事があった、と言う事を物語っている。

マナオは複数のクエリに答えなければならない。各クエリは"与えられた情報から、XnとYmの間で戦争が起こった可能性はあるか？"というものである。

あなたは３つのString[] dynasties, battles, queriesで表された、上記の情報が与えられる。

dynasitesのi番目の要素は、国家'A' + iの君主の統治をし始めた年数を表す。例えば、dynasites[ 0 ] = "42 47 55 63"であれば、国家'A'は"A0"が42-46年に、"A1"が47-54年に、"A2"が55-62年に統治をしていたことを表す。

battlesを連結して１つの文字列にしたとする。この文字列はスペース区切りで、歴史上起きた戦争の情報を、上記のフォーマットで表したものとなる。

queriesの各要素はbattlesと同じフォーマットで、１つの戦争を表す。

各クエリにおいて、その２つの国家間で、戦争が起こっていた可能性があるのなら'Y'を、そうでなければ'N'を返せ。

制約

2 <= 国家の数 <= 26
0 <= dynasites[i] <= 99999
1 <= battleの要素数 <= 50
1 <= queryの要素数 <= 50

考えた事

国家ABにおける、年のズレの可能性を、プラス方向とマイナス方向でそれぞれ計算する。もらった情報から、まず直接的なズレの範囲を計算し、それからワーシャルフロイドで間接的なもの含めて、ズレの範囲を狭めていく。

事後

通ったけど、なぜこれでいいのかよく分からないままである・・・

ソースコード

const int MAX_INF = (int)1e9;
const int MIN_INF = (int)-1e9;

int N;
int top[30][30];
int btm[30][30];

vector<int> ds[30];

class History {
public:

    string verifyClaims(vector <string> dynasties, vector <string> battles, vector <string> queries){
        // 入力
        N = dynasties.size();
        for( int i = 0; i < N; i++ ){
            ds[i].clear();
            stringstream ss;
            ss << dynasties[i];
            int t;
            while( ss >> t ){
                ds[i].push_back( t );
            }
        }

        // top bottom初期化
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < N; j++ ){
                top[i][j] = MAX_INF;
                btm[i][j] = MIN_INF;
            }
        }

        // 更新
        string bs;
        for( int i = 0; i < battles.size(); i++ ){
            bs += battles[i];
        }
        for( int i = 0; i < bs.length(); i += 6 ){
            int a = bs[i] - 'A';
            int an = bs[i+1] - '0';
            int ar = ds[a][an+1];
            int al = ds[a][an];
            int b = bs[i+3] - 'A';
            int bn = bs[i+4] - '0';
            int br = ds[b][bn+1];
            int bl = ds[b][bn];

            // a->b
            top[a][b] = min( top[a][b], br - 1 - al );
            btm[a][b] = max( btm[a][b], bl + 1 - ar );

            // b->a
            top[b][a] = min( top[b][a], ar - 1 - bl );
            btm[b][a] = max( btm[b][a], al + 1 - br );    
        }

        // ワーシャルたん
        for( int k = 0; k < N; k++ ){
            for( int i = 0; i < N; i++ ){
                for( int j = 0; j < N; j++ ){
                    top[i][j] = min( top[i][j], top[i][k] + top[k][j] );
                    btm[i][j] = max( btm[i][j], btm[i][k] + btm[k][j] );
                }
            }
        }

        // クエリ
        string ans;
        int M = queries.size();
        for( int i = 0; i < M; i++ ){
            int a = queries[i][0] - 'A';
            int an = queries[i][1] - '0';
            int b = queries[i][3] - 'A';
            int bn = queries[i][4] - '0';

            int al = ds[a][an];
            int ar = ds[a][an+1];
            int bl = ds[b][bn];
            int br = ds[b][bn+1];

            ar = ar + top[a][b];
            al = al + btm[a][b];

            if( br <= al || ar <= bl ){
                ans += 'N';
            }else{
                ans += 'Y';
            }
        }
            
        return ans;
    }
};