読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 584 Div1 Easy Egalitarianism

SRM584に参加。
Easyがあっさり解けた、と思ったら後でしょうもない変数名ミスをやらかしてResubmit。
Mediumも解けたと思ったら詰めが甘くてWA。
Mediumの正答率が低かったので、EasyのResubmitが無ければそれだけで上位に入れたのに…。
http://community.topcoder.com/stat?c=problem_statement&pm=12613

問題

N人が互いに友人かどうかが行列で与えられる。
また金額Dが与えられる。
友人同士の持ってるお金の差がD円以内の場合、最もお金持ちの人とお金のない人の差額の最大値を求めよ。
ただし、差額が無限大になる場合は-1を返せ。

解法

まず、友人同士の距離を1、それ以外を無限大として、任意の人同士の最短距離が求まる。
N<=50なのでこの処理はWFで行ってしまおう。

もし最短距離が無限大のペアがある場合、そこの差額は任意になるので-1を返す。
そうでない場合、最短距離が最長のペアに対し、その距離にDを返せばよい。

class Egalitarianism {
	public:
	int N;
	int dist[51][51];
	int maxDifference(vector <string> F, int d) {
		int N=F.size();
		int i,j,k;
		
		FOR(i,N) FOR(j,N) dist[i][j]=(F[i][j]=='Y')?1:1000;
		FOR(i,N) dist[i][i]=0;
		FOR(i,N) FOR(j,N) FOR(k,N) dist[j][k] = min(dist[j][k], dist[j][i]+dist[i][k]);
		
		int ma=0;
		FOR(i,N) FOR(j,N) ma=max(ma,dist[i][j]);
		if(ma>=1000) return -1;
		return ma*d;
		
	}
}

まとめ

dist[i][i]=0を忘れてる人がいて、その場合dist[i][i]=2となってしまいWAになるケースがあった。
チャレンジケースでその可能性を思いついたけど、1ミスで大きく順位を落とす状態だったので手が出せなかった。

そんな自分はdist[i][i]=0をdist[i][j]=0と書いてしまっていてResubmit。
ミスに気付いたおかげでrate微減で済んだ。

広告を非表示にする