kmjp's blog

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

TopCoder SRM 635 Div1 Easy SimilarRatingGraph

相変わらずSRMは不調で、1ChallengeしたもののEasy/Medium落としてレート減。
http://community.topcoder.com/stat?c=problem_statement&pm=13485

問題

N回分の日付けとその日付に対応したレートがdate[i]、rating[i]で与えられる。
この2軸の情報を元に、時系列のレート折れ線グラフを書くことを考える。

折れ線グラフの一部を平行移動および拡大縮小した場合に、グラフの他の部分と一致することはあるか。
あるなら、その辺総長を答えよ。

なお、グラフが一致するとは頂点同士が一致しなければならない。
(移動前の頂点が移動後は辺上にあったり、その逆は不可)

解法

N個の頂点から(N-1)個の線分が生成できる。
まずは(N-1)*(N-1)個の線分を総当たりし、傾きが等しいか、また傾きが等しいなら長さの倍率を求める。
なお、date[i]は各頂点異なるので、長さの倍率はdateの比率を取ると良い。ratingはゼロ除算の可能性がある。

あとは同じ長さの倍率が連続するセグメント群を求め、総長を求めればよい。
この際浮動小数点を使うのであれば誤差に注意。長さの倍率の差は1e-10程度に収まる可能性があるので、一致判定はかなり小さいEPSを用いる必要がある。

以下のコードはO(N^3)だが、O(N^2)に抑えることもできる。
むしろ自分は無駄に本番O(N^2)を頑張ったうえに、大き目のEPSを取って失敗した。

double mat[401][401];
double LS[402];
class SimilarRatingGraph {
	public:
	int N;
	double maxLength(vector <int> date, vector <int> rating) {
		N=date.size();
		int x,y,i;
		
		ZERO(mat);
		ZERO(LS);
		FOR(x,N-1) LS[x+1]=LS[x]+sqrt((date[x+1]-date[x])*1LL*(date[x+1]-date[x])+(rating[x+1]-rating[x])*1LL*(rating[x+1]-rating[x]));
		
		FOR(x,N-1) FOR(y,N-1) if(x!=y) {
			ll dx1=date[x+1]-date[x];
			ll dx2=date[y+1]-date[y];
			ll dy1=rating[x+1]-rating[x];
			ll dy2=rating[y+1]-rating[y];
			if(dx1*dy2==dx2*dy1) mat[x][y]=dx2*1.0/dx1;
		}
		
		double ma=0;
		FOR(x,N) FOR(y,N) if(x!=y && mat[x][y]>0) {
			FOR(i,N) {
				if(x+i>=N-1 || y+i>=N-1) break;
				if(fabs(mat[x][y]-mat[x+i][y+i])>1e-20) break;
			}
			ma=max(ma,LS[x+i]-LS[x]);
		}
		return ma;
	}
}

まとめ

誤差とかゼロ除算とか所々罠が多く、なんと本番正答率が35%。
これはひどい…。