SRM 635 DIV1 Easy - SimilarRatingGraph (×)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13485&rd=16078

日付とその日付に行われたコンテストの後のレーティングが時系列で与えられる。
そのグラフのうち2つの似通ったサブグラフを探し、最大の長さのサブグラフを求める。
サブグラフは各点が連続していなければならない。
似通ったサブグラフ同士は、同じ長さで片方に係数をかけるもしくはスライドすると同一になるものを言う。

解き方


問題文を正確に読めてなかったのが反省点。

・サンプルを見ると、同じ傾きのサブグラフを求めることになりそう。
・同じ傾きのサブグラフのうち、切片が異なるサブグラフの集合の有無で答えが異なりそう。
・上記の条件ではコードに落とし込むのが複雑そう

ここで解き方に困ってしまい、他の人のコードをみる。

コードをみてから問題文を改めてみると、似通ったグラフとは同じ長さでなければならないこと、さらに連続するという条件がわかれば簡単に求められる。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class SimilarRatingGraph {

public: double maxLength(vector<int> date, vector<int> rating) {
double ans=0;
int n=date.size();

FORE(a,0,n-1)FORE(b,0,n-1)if(a!=b){
double l=0;
long long d1=date[a+1]-date[a];
long long d2=date[b+1]-date[b];
for(int i=0;a+i<n&&b+i<n;i++){
long long f1=date[a+i+1]-date[a+i];
long long r1=rating[a+i+1]-rating[a+i];

long long f2=date[b+i+1]-date[b+i];
long long r2=rating[b+i+1]-rating[b+i];

if(f1*d2==f2*d1 && r1*f2==r2*f1)l+=sqrt(f1*f1+r1*r1);
else break;
}
ans=max(ans,l);
}

return ans;
}

};

このエントリーをはてなブックマークに追加