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微減で済んだ。