TopCoder SRM 808 : Div1 Easy Div2 Hard IOIVoting

問題文が妙に長いしなんなんだ今回。
https://community.topcoder.com/stat?c=problem_statement&pm=17039&rd=18705

問題

N個の選択肢がある選挙が行われる。
2次元配列Pが与えられる。
P[a][b]は選択肢bよりaを好む有権者の人数を示す。
P[a][b]＞P[b][a]なら、有権者全体でbよりaが好まれることを意味する。
その差P[a][b]-P[b][a]は、直接的な好みの強さと呼ぶことにする。

もし(仮に直接的にaよりbが好まれたとしても)aがcより好まれ、cがdより好まれ…、yがzより好まれ、zがbより好まれるなら、aは間接的にbより好まれたということができるとする。
この時の好みの強さは、それぞれの直接的な好みの強さの最小値である。
このような好みの列における、好みの強さをS(a,b)とする。

選択肢aがbより有力であるとは、S(a,b)≧S(b,a)であることを意味する。
また、選択肢aが最有力候補であるとは、任意の選択肢xに対しS(a,x)≧S(x,a)であることを意味する。

Pに対し、最有力候補を求めよ。

解法

まずPを以下のように変形しておく。

• P[x][x]=inf
• P[x][y]とP[y][x]から、min(P[x][y],P[y][x])を引く。つまりいずれかを0にしておく。

このPに対し、Warshall-Floyd法の要領でP[x][y]=max(P[x][y],min(P[x][z],P[z][y]))で状態を更新するとSが得られる。

class IOIVoting {
	public:
	vector <int> winners(int N, vector <int> votes) {
		int A[55][55];
		int y,x;
		int i;
		FOR(y,N) FOR(x,N) A[y][x]=votes[y*N+x];
		FOR(y,N) FOR(x,y) {
			int z=min(A[x][y],A[y][x]);
			A[x][y]-=z;
			A[y][x]-=z;
		}
		FOR(i,N) A[i][i]=10000;
		int z;
		FOR(z,N) FOR(x,N) FOR(y,N) A[x][y]=max(A[x][y],min(A[x][z],A[z][y]));
		
		vector<int> ret;
		FOR(y,N) {
			int ok=1;
			FOR(x,N) if(A[y][x]<A[x][y]) ok=0;
			if(ok) ret.push_back(y);
		}
		return ret;
		
	}
}

まとめ

解法より問題文の要約を書くのに疲れた。