相変わらず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%。
これはひどい…。