SRM635 Div1E

家にいるとイカやっちゃうから大学行く日の方が精進できるね(?)

・SRM635 Div1E SimilarRatingGraph

二次元平面上にn個の点がある.i個目の点の座標は(x[i],y[i])である(xは単調増加).l番目の点からr番目の点まで順次結んで出来る図形を区間[l,r]のグラフと呼ぶ.二つのグラフが相似であるとは,一方のグラフを平行移動して正の実数倍拡大すると他方に重なることを意味する.またグラフの長さとは,グラフに含まれる線分の長さの和のことである.このとき,その区間のグラフと区間[l',r'](l≠l')のグラフが相似となるような区間[l',r']が存在する全ての区間[l,r]についての,グラフの長さの最大値を求めよ,という問題.

日本語がややこしい.異なる区間の選び方を全て試してグラフが相似かどうかチェックする,ということをやりたいが,区間はO(n^2)通りあってそこから二つの区間を選ぶ方法はO(n^4)通りあるのでさすがに無理.そこで区間の始点だけ固定してみる.つまり異なるl,l'(0≦l<l'<n)を選び,そこからどこまで区間を伸ばせるかを調べる.平行移動してもかわらないのはグラフ上の隣り合う二点の座標の差である.これに注目して頑張ると区間を一つ伸ばしたときグラフが相似なままかが判定できる(例えば拡大率がr倍,つまり隣り合う二点間の座標の差がr倍になっているという関係がわかっているとすると次の点を追加してもそれが成り立っているか調べればいい).

ソースコード

class SimilarRatingGraph {
    public:
    double maxLength(vector<int> date, vector<int> rating) {
        int N=date.size();
        double ans=0;
        for(int i=0;i<N;i++) {
            for(int j=i+1;j<N;j++) {
                int len=1;
                double r;
                while(j+len+1<=N) {
                    double dx1=date[i+len]-date[i+len-1];
                    double dx2=date[j+len]-date[j+len-1];
                    double dy1=rating[i+len]-rating[i+len-1];
                    double dy2=rating[j+len]-rating[j+len-1];
                    if(dy2/dx2!=dy1/dx1) break;
                    if(len==1) r=dx2/dx1;
                    else if(r!=dx2/dx1) break;
                    len++;
                }
                double sum1=0;
                double sum2=0;
                for(int k=1;k<len;k++) {
                    sum1+=sqrt(pow(date[i+k]-date[i+k-1],2)+pow(rating[i+k]-rating[i+k-1],2));
                    sum2+=sqrt(pow(date[j+k]-date[j+k-1],2)+pow(rating[j+k]-rating[j+k-1],2));
                }
                ans=max(ans,sum1);
                ans=max(ans,sum2);
            }
        }
        return ans;
    }
};