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で一番初めに統治していた君主の時代を表す。各君主は年の最初の日から統治を始めている。各君主が統治をし始めた(その国における)年が、正確に分かっている。
マナオはこれらの国々の年代が、互いにどのように対応しているのかを解明したい。これを行うにあたり、彼は歴史上のさまざまな戦争についての情報を集めた。それぞれの戦いは、2つの国家間で行われていた。例えば、"C0-D3"と言う情報は、"C0"と"D3"で戦いが起こっていたことを意味する。この戦争があったという情報は、"C0"と"D3"の2つの君主が、同じ年に統治していた事があった、と言う事を物語っている。
マナオは複数のクエリに答えなければならない。各クエリは"与えられた情報から、XnとYmの間で戦争が起こった可能性はあるか?"というものである。
あなたは3つの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を連結して1つの文字列にしたとする。この文字列はスペース区切りで、歴史上起きた戦争の情報を、上記のフォーマットで表したものとなる。
queriesの各要素はbattlesと同じフォーマットで、1つの戦争を表す。
各クエリにおいて、その2つの国家間で、戦争が起こっていた可能性があるのなら'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; } };