問題
http://community.topcoder.com/stat?c=problem_statement&pm=12692&rd=15698
複数の王朝があり、各王朝ごとに皇帝ごとの在位期間がわかっている。
ただし王朝ごとに年号の割り振り方が違うので、年数は必ずしも一致していない。
ここで、王朝同士の戦いの記録がある。記録をもとに、王朝同士がどの年数に対応しているかわかるようになっている。
このとき、王朝同士の戦いのクエリが与えられた時、そのクエリが整合性がとれるものであればＹ，そうでなければＮを返す。
解き方
王朝ごとの年数の一致を全体でとる必要がある。
今回グローバルの年号を仮に考えたとき、グローバルと各王朝の年数のずれをXと考える。
つまり、王朝iのグローバルとの年数のずれはX[i]とする。
次に、戦いがあったときにどの導き出される制約は以下の通り。
王朝uにおけるa番目の皇帝の始まりの年数をp[u][a]とすると、
王朝uのa番目の年号と王朝vのb番目の年号との戦いは
x[u]+p[u][a] ～p[u][a+1]-1 対 x[v]+p[v][b] ～p[v][b+1]-1
x[u]+p[u][a+1]-1>=x[v]+p[v][b] かつ x[v]+p[v][b+1]-1>=x[u]+p[u][b]
x[u]-x[v]>=p[v][b]-p[u][a+1]+1 かつ x[v]-x[u]>=p[u][a]-p[v][b+1]+1
x[v]-x[u]>=p[u][a+1]-p[v][b]-1 かつ x[u]-x[v]>=p[v][b+1]-p[u][a]-1
これをワーシャルフロイド法を用いて全体の整合性を取る。
最後にクエリを加えたことで矛盾が生じる、つまり負の経路が発生した時はＮを返し
そうでなければＹを返せばよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[30][30],d[30][30];
class History {
public:
void Addbattle(string battle){
int u=battle[0]-'A';
int v=battle[3]-'A';
int a=battle[1]-'0';
int b=battle[4]-'0';
d[u][v]=min(d[u][v],p[u][a+1]-1-p[v][b]);
d[v][u]=min(d[v][u],p[v][b+1]-1-p[u][a]);
}
string verifyClaims(vector<string> dynasties, vector<string> battles, vector<string> queries) {
int n=dynasties.size();
FORE(i,0,n){
stringstream out(dynasties[i]);
for(int cnt=0;out>>p[i][cnt];)cnt++;
}
int q=queries.size();
string ret;
FORE(i,0,q){
FORE(j,0,n)FORE(k,0,n)d[j][k]=100000;
FORE(j,0,n)d[j][j]=0;
string allbattle=accumulate(all(battles),string());
stringstream out(allbattle);
for(string battle;out>>battle;)Addbattle(battle);
Addbattle(queries[i]);
FORE(l,0,n)FORE(j,0,n)FORE(k,0,n)d[j][k]=min(d[j][k],d[j][l]+d[l][k]);
ret+='Y';
FORE(j,0,n)if(d[j][j]<0)ret[i]='N';
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[30][30],d[30][30];
class History {
public:
void Addbattle(string battle){
int u=battle[0]-'A';
int v=battle[3]-'A';
int a=battle[1]-'0';
int b=battle[4]-'0';
d[u][v]=min(d[u][v],p[u][a+1]-1-p[v][b]);
d[v][u]=min(d[v][u],p[v][b+1]-1-p[u][a]);
}
string verifyClaims(vector<string> dynasties, vector<string> battles, vector<string> queries) {
int n=dynasties.size();
FORE(i,0,n){
stringstream out(dynasties[i]);
for(int cnt=0;out>>p[i][cnt];)cnt++;
}
int q=queries.size();
string ret;
FORE(i,0,q){
FORE(j,0,n)FORE(k,0,n)d[j][k]=100000;
FORE(j,0,n)d[j][j]=0;
string allbattle=accumulate(all(battles),string());
stringstream out(allbattle);
for(string battle;out>>battle;)Addbattle(battle);
Addbattle(queries[i]);
FORE(l,0,n)FORE(j,0,n)FORE(k,0,n)d[j][k]=min(d[j][k],d[j][l]+d[l][k]);
ret+='Y';
FORE(j,0,n)if(d[j][j]<0)ret[i]='N';
}
return ret;
}
};