TopCoder SRM 586 Div1 Medium History

さてMedium。
今回CFといいSRMといい問題文が読みにくいのが多いなぁ…。
http://community.topcoder.com/stat?c=problem_statement&pm=12692

問題

最大26個の王朝があり、それぞれ最大10人の王がいる。
それぞれの在位期間が年号で与えられる。
各王朝は１年の長さは同じだが、王朝ごとに暦が異なり異なる年号を用いているため、同じ数字でも異なる年となる。

ここで、ある王と別の王が戦争をした歴史記録が複数与えられる。
これは、その２人の王が同じ年に在位していたことを示す。

このとき、王２人からなるクエリが複数与えられる。
その王が互いに戦争をできた可能性があるかを返せ。

解法

歴史記録から、その両王朝の年号のずれの範囲を求めることができる。
あとはFloyd法の容量で、他の歴史記録や王朝間で矛盾が出ないよう年号のずれの最大・最小値の範囲を狭めていく。

最後のクエリにおいては、その２人の王が互いに戦争できたと仮定すると推測できる年号のずれと、Floyd法で求めた年号のずれの範囲に重複があるかどうかを変えればよい。
処理のオーダーとしてはFloyd法なので王朝数Nに対してO(N^3)なので時間は余裕。

下記は本番より少し整理したコード。

class History {
	public:
	int N;

	vector<int> D[51];
	int diff[26][26][2];
	
	void AddCons(int n1,int m1,int n2,int m2) {
		diff[n1][n2][0]=max(diff[n1][n2][0],D[n2][m2]-(D[n1][m1+1]-1));
		diff[n1][n2][1]=min(diff[n1][n2][1],D[n2][m2+1]-1-D[n1][m1]);
		diff[n2][n1][0]=max(diff[n2][n1][0],D[n1][m1]-(D[n2][m2+1]-1));
		diff[n2][n1][1]=min(diff[n2][n1][1],D[n1][m1+1]-1-D[n2][m2]);
	}
	
	string okok(int n1,int m1,int n2,int m2) {
		int d1=D[n2][m2]-(D[n1][m1+1]-1);
		int d2=D[n2][m2+1]-1-D[n1][m1];
		if(diff[n1][n2][1]<d1) return "N";
		if(diff[n1][n2][0]>d2) return "N";
		
		return "Y";
	}
	
	string verifyClaims(vector <string> dynasties, vector <string> battles, vector <string> queries) {
		int i,j,x,y,k;
		N=dynasties.size();
		FOR(i,N) {
			vector<int> VV=split_int(dynasties[i],' ');
			D[i].clear();
			FOR(j,VV.size()) D[i].push_back(VV[j]-VV[0]);
		}
		FOR(i,26) {
			FOR(j,26) diff[i][j][0]=-(1<<29),diff[i][j][1]=1<<29;
			diff[i][i][0]=diff[i][i][1]=0;
		}
		
		string B=concatvec(battles);
		for(i=0;i<B.size();i+=6) 
			AddCons(B[i]-'A',B[i+1]-'0',B[i+3]-'A',B[i+4]-'0');
		
		FOR(i,N) FOR(j,N) FOR(k,N) {
			diff[j][k][0]=max(diff[j][k][0], diff[j][i][0]+diff[i][k][0]);
			diff[j][k][1]=min(diff[j][k][1], diff[j][i][1]+diff[i][k][1]);
		}
		
		string r="";
		FOR(i,queries.size())
			r+=okok(queries[i][0]-'A',queries[i][1]-'0',queries[i][3]-'A',queries[i][4]-'0');
		return r;
	}
};

まとめ

アルゴリズムはともかく、細かい実装で凡ミスしそうな問題だっただけに解き切れてうれしい。