#546359 (C++17) No.731 等差数列がだいすき

提出ソース
結果

問題	No.731 等差数列がだいすき
ユーザー	mugen_1337
提出日時	2020-09-03 14:22:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,500 ms
コード長	14,530 bytes
コンパイル時間	3,154 ms
コンパイル使用メモリ	233,020 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-23 17:30:59
合計ジャッジ時間	3,939 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	1 ms 6,816 KB
testcase_09	AC	1 ms 6,820 KB
testcase_10	AC	1 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	1 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	1 ms 6,820 KB
testcase_17	AC	0 ms 6,816 KB
testcase_18	AC	2 ms 6,816 KB
testcase_19	AC	2 ms 6,820 KB
testcase_20	AC	2 ms 6,820 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
 
struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

//////////////////////////////////////////////////////
using Real=double;
using Point=complex<Real>;
const Real EPS=1e-10;
const Real pi=acosl(-1);
//入出力補助
istream &operator>>(istream &is,Point &p){
    Real a,b;
    is>>a>>b;
    p=Point(a,b);
    return is;
}
ostream &operator<<(ostream &os,Point &p){
    return os<<fixed<<setprecision(12)<<p.real()<<' '<<p.imag();
}
 
inline bool eq(Real a,Real b){
    return fabs(a-b)<EPS;
}
Point operator*(const Point &p,const Real &d){
    return Point(real(p)*d,imag(p)*d);
}
struct Line{
    Point p1,p2;
    Line()=default;
    Line(Point p1,Point p2):p1(p1),p2(p2){}
 
    //Ax + By = C
    Line(Real A,Real B,Real C){
       if(eq(A,0))     p1=Point(0,C/B),p2=Point(1,C/B);
       else if(eq(B,0))p1=Point(C/A,0),p2=Point(C/A,1);
       else            p1=Point(0,C/B),p2=Point(C/A,0);
    }
};
struct Segment:Line{
   Segment()=default;
   Segment(Point p1,Point p2):Line(p1,p2){}
};
struct Circle{
    Point center;
    Real r;
    Circle()=default;
    Circle(Point center,Real r):center(center),r(r){}
};
/////////////////////////////////////////////////////////
 
 
// 点 p を反時計回りに theta 回転
Point rotate(Real theta,const Point &p) {
    return Point(cos(theta)*p.real()-sin(theta)*p.imag(),sin(theta)*p.real()+cos(theta)*p.imag());
}
 
Real radian_to_degree(Real r){
    return r*180.0/pi;
}
 
Real degree_to_radian(Real d){
    return d*pi/180.0;
}
 
//三角形の面積，サラスの公式
Real area_triangle(Point a,Point b,Point c){
    Point x=b-a,y=c-a;
    return fabs(x.real()*y.imag()-x.imag()*y.real())/2;
}
 
//v
//外積
Real cross(Point a,Point b){
    return real(a)*imag(b)-imag(a)*real(b);
}
//v
//内積
Real dot(Point a,Point b) {
    return real(a)*real(b)+imag(a)*imag(b);
}
 
//v
//平行判定，外積0かをみる
bool parallel(Line a,Line b){
    return eq(cross(a.p1-a.p2,b.p1-b.p2),0.0);
}
//v
//垂直判定，内積0かをみる
bool orthogonal(Line a,Line b){
    return eq(dot(a.p1-a.p2,b.p1-b.p2),0.0);
}
 
//v
//正射影，pからlに下した垂線の足を求める
Point projection(Line l,Point p){
    //ベクトルl上のどの位置に垂線の足が来るか求める
    Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
    return l.p1+(l.p1-l.p2)*k;
}
Point projection(Segment l,Point p){
    Real k=dot(l.p1-l.p2,p-l.p1)/norm(l.p1-l.p2);
    return l.p1+(l.p1-l.p2)*k;
}
 
//v
//反射，直線lに関し点pと線対称な点を返す
Point reflection(Line l,Point p){
    Point h=projection(l,p);
    return (p+(h-p)+(h-p));
}
Point reflection(Segment l,Point p){
    Point h=projection(l,p);
    return (p+(h-p)+(h-p));
}
 
//二点間の距離
Real dis(Point a,Point b){
    return abs(a-b);
} 
//点と直線の距離
Real dis(Line l,Point p){
    return abs(p-projection(l,p));
}
 
//v
//COUNTER CLOCKWISE，返す値は↓を参照
//https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_1_C
int ccw(Point a,Point b,Point c){
    b-=a;c-=a;
    if(cross(b,c)>EPS)       return  1;//COUNTER CLOCKWISE
    else if(cross(b,c)<-EPS) return -1;//CLOCKWISE
    else if(dot(b,c)<0)      return  2;//c--a--b ONLINE BACK
    else if(norm(b)<norm(c)) return -2;//a--b--c ONLINE FRONT
    else                     return  0;//a--c--b ON SEGMENT
}
 
//v
//3点が作る三角形の外心
//面積0の三角形を渡すと分母に面積があるので壊れるかも
Point circumcenter(Point A,Point B,Point C){
    Real S=area_triangle(A,B,C);
    Real a=dis(B,C),b=dis(A,C),c=dis(A,B);
    return A*(a*a*(b*b+c*c-a*a)/(16*S*S))+B*(b*b*(c*c+a*a-b*b)/(16*S*S))+C*(c*c*(a*a+b*b-c*c)/(16*S*S));
}
 
//交差判定
//直線状に乗るか
bool intersect(Line l,Point p){
    return abs(ccw(l.p1,l.p2,p))!=1;
}
//直線の交差判定，外積
bool intersect(Line l1,Line l2){
    return abs(cross(l1.p2-l1.p1,l2.p2-l2.p1))>EPS or
        abs(cross(l1.p2-l1.p1,l2.p2-l1.p1))<EPS;
}
//線分に点が乗るかの判定，ccw
bool intersect(Segment s,Point p){
    return ccw(s.p1,s.p2,p)==0;
}
//直線と線分の交差判定
bool intersect(Line l,Segment s){
    return cross(l.p2-l.p1,s.p1-l.p1)*cross(l.p2-l.p1,s.p2-l.p1)<EPS;
}
//円と直線の交差判定
bool intersect(Circle c,Line l){
    return dis(l,c.center)<=c.r+EPS;
}
//円上かどうか，内部かどうかではない
bool intersect(Circle c,Point p){
    return abs(abs(p-c.center)-c.r)<EPS;
}
//v
//線分と線分の交差判定
bool intersect(Segment s,Segment t){
    return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <=0 and
        ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2)<=0;
}
//線分と円の交差判定，交点の個数を返す
int intersect(Circle c,Segment l){
    Point h=projection(l,c.center);
    //直線まるっと円の外側
    if(norm(h-c.center)-c.r*c.r>EPS)    return 0;
    Real d1=abs(c.center-l.p1),d2=abs(c.center-l.p2);
    //線分が円内
    if(d1<c.r+EPS and d2<c.r+EPS) return 0;
    if((d1<c.r-EPS and d2>c.r+EPS) or (d2<c.r-EPS and d1>c.r+EPS)) return 1;
    //円の外部にまるまるはみ出ていないか
    if(dot(l.p1-h,l.p2-h)<0) return 2;
    return 0;
}
//円と円の位置関係，共通接線の個数を返す
int intersect(Circle c1,Circle c2){
    if(c1.r<c2.r) swap(c1,c2);
    Real d=abs(c1.center-c2.center);
    //2円が離れている
    if(c1.r+c2.r<d)     return 4;
    //2円が外接する
    if(eq(c1.r+c2.r,d)) return 3;
    //2円が交わる
    if(c1.r-c2.r<d)     return 2;
    //円が内接する
    if(eq(c1.r-c2.r,d)) return 1;
    //内包
                        return 0;
}
 
//交点
//線分の交点はintersectをチェックしてokなら直線の交点をやる
//intersectをチェックすること
//v
Point crosspoint(Line l,Line m){
    Real A=cross(m.p2-m.p1,m.p1-l.p1);
    Real B=cross(m.p2-m.p1,l.p2-l.p1);
    if(eq(A,0) and eq(B,0)) return l.p1;
    if(eq(B,0))             throw "NAI";
    return l.p1+A/B*(l.p2-l.p1);    
}
Point crosspoint(Segment l,Segment m){
    return crosspoint(Line(l),Line(m));
}
vector<Point> crosspoint(Circle c,Line l){
    vector<Point> ret;
    Point h=projection(l,c.center);
    Real d=sqrt(c.r*c.r-norm(h-c.center));
    Point e=(l.p2-l.p1)*(1/abs(l.p2-l.p1));
    if(c.r*c.r+EPS<norm(h-c.center)) return ret;
    if(eq(dis(l,c.center),c.r)){
        ret.push_back(h);
        return ret;
    }
    ret.push_back(h+e*d);ret.push_back(h-e*d);
    return ret;
}
//要verify，
vector<Point> crosspoint(Circle c,Segment s){
    Line l=Line(s.p1,s.p2);
    int ko=intersect(c,s);
    if(ko==2) return crosspoint(c,l);
    vector<Point> ret;
    if(ko==0) return ret;
    ret=crosspoint(c,l);
    if(ret.size()==1) return ret;
    vector<Point> rret;
    //交点で挟める方を返す
    if(dot(s.p1-ret[0],s.p2-ret[0])<0)  rret.push_back(ret[0]);
    else                                rret.push_back(ret[1]);
    return rret;
}
//v
vector<Point> crosspoint(Circle c1,Circle c2){
    vector<Point> ret;
    int isec=intersect(c1,c2);
    if(isec==0 or isec==4) return ret;
    Real d=abs(c1.center-c2.center);
    Real a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
    Real t=atan2(c2.center.imag()-c1.center.imag(),c2.center.real()-c1.center.real());
    ret.push_back(c1.center+Point(cos(t+a)*c1.r,sin(t+a)*c1.r));
    ret.push_back(c1.center+Point(cos(t-a)*c1.r,sin(t-a)*c1.r));
    return ret;
}
 
//v
//点pから引いた円cの接線の接点を返す
vector<Point> tangent(Circle c,Point p){
    return crosspoint(c,Circle(p,sqrt(norm(c.center-p)-c.r*c.r)));
}
//v
//二円の共通接線，Lineの2点は接点を表す
vector<Line> tangent(Circle c1,Circle c2){
    vector<Line> ret;
    if(c1.r<c2.r) swap(c1,c2);
    Real g=norm(c1.center-c2.center);
    //中心が一致するならない
    if(eq(g,0)) return ret;
    Point u=(c2.center-c1.center)/sqrt(g);
    Point v=rotate(pi*0.5,u);
    for(int s:{-1,1}){
        Real h=(c1.r+s*c2.r)/sqrt(g);
        if(eq(1-h*h,0)){
            ret.push_back(Line(c1.center+u*c1.r,c1.center+(u+v)*c1.r));
        }
        else if(1-h*h>0){
            Point uu=u*h,vv=v*sqrt(1-h*h);
            ret.push_back(Line(c1.center+(uu+vv)*c1.r,c2.center-(uu+vv)*c2.r*s));
            ret.push_back(Line(c1.center+(uu-vv)*c1.r,c2.center-(uu-vv)*c2.r*s));
        }
    }
    return ret;
}
 
//v
//最小包含円を返す　計算量は期待値O(n)
Circle MinimumBoundingCircle(vector<Point> v){
    int n=v.size();
  
    //ランダムシャッフル．いぢわるされたくないもんだ
    mt19937 mt(time(0));
    shuffle(v.begin(),v.end(),mt);
    Circle ret(0,0);
    //2点で円を作る
    auto make_circle2=[&](Point a,Point b){
        return Circle((a+b)*0.5,dis(a,b)/2);
    };
    //3点で円を作る
    auto make_circle3=[&](Point A,Point B,Point C){
        Point cent=circumcenter(A,B,C);
        return Circle(cent,dis(cent,A));
    };
    auto isIn=[&](Point a){
        return dis(ret.center,a)<ret.r+EPS;
    };
 
    ret=make_circle2(v[0],v[1]);
    for(int i=2;i<n;i++){
        //v[i]が円に入っていないなら
        if(!isIn(v[i])){
            //円内にないなら点v[i]は必ず円周上に来る
            ret=make_circle2(v[0],v[i]);
            for(int j=1;j<i;j++){
                if(!isIn(v[j])){
                    //この時iとjが円周上を考える
                    ret=make_circle2(v[i],v[j]);
                    //最後の1点の決定
                    for(int k=0;k<j;k++){
                        if(!isIn(v[k])){
                            ret=make_circle3(v[i],v[j],v[k]);
                        }
                    }
                }
            }
        }
    }
    return ret;
}
 
// v
// 最近点対
Real closest_pair(vector<Point> ps){
    sort(ALL(ps),[&](Point a,Point b){
        return real(a)<real(b);
    });
 
    function<Real(int,int)> rec=[&](int l,int r){
        if(r-l<=1) return 1e18;
        int m=(l+r)/2;
        Real x=real(ps[m]);
        Real ret=min(rec(l,m),rec(m,r));
        inplace_merge(begin(ps)+l,begin(ps)+m,begin(ps)+r,[&](Point a,Point b){
            return imag(a)<imag(b);
        });
        // 分割を跨いで最小距離があるか調べる
        vector<Point> b;
        for(int i=l;i<r;i++){
            if(abs(real(ps[i])-x)>=ret) continue;
            for(int j=(int)b.size()-1;j>=0;j--){
                if(abs(imag(ps[i]-b[j]))>=ret) break;
                ret=min(ret,abs(ps[i]-b[j]));
            }
            b.push_back(ps[i]);
        }
        return ret;
    };
    return rec(0,(int)ps.size());
}
 
// 凸多角形系統
// 凸多角形の頂点は反時計周りに訪れる順序
 
// v
// 頂点は反時計周りに訪れる順序，時計回りとなるような3点があるとfalse
bool is_convex(const vector<Point> &ps){
    int n=(int)ps.size();
    for(int i=0;i<n;i++)if(ccw(ps[(i+n-1)%n],ps[i],ps[(i+1)%n])==-1)return false;
    return true;
}
 
// 凸包，あんまりよくわかってない．直線状に頂点をのせない場合(↑)，のせる場合(↓)
vector<Point> convex_hull(vector<Point> p){
    int n=(int)p.size(),k=0;
    if(n<=2)return p;
    sort(begin(p),end(p),[](Point a,Point b){
        return real(a)!=real(b)?real(a)<real(b):imag(a)<imag(b);
    });
    vector<Point>ch(2*n);
    for(int i=0;i<n;ch[k++]=p[i++]){
        // while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
        while(k>=2 and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
    }
    for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
        // while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<EPS)k--;
        while(k>=t and cross(ch[k-1]-ch[k-2],p[i]-ch[k-1])<0)k--;
    }
    ch.resize(k-1);
    return ch;
}
 
// // v 整数で凸法
// using P=pair<int,int>;
// vector<P> convex_hull(vector<P> p){
//     int n=(int)p.size(),k=0;
//     if(n<=2)return p;
//     sort(begin(p),end(p));
//     vector<P> ch(2*n);
//     auto crf=[&](P u,P v){return u.first*v.second-u.second*v.first;};
//     auto dff=[&](P u,P v){return make_pair(u.first-v.first,u.second-v.second);};
//     for(int i=0;i<n;ch[k++]=p[i++]){
//         while(k>=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--;
//         // while(k>=2 and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--;
//     }
//     for(int i=n-2,t=k+1;i>=0;ch[k++]=p[i--]){
//         while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<0)k--;
//         // while(k>=t and crf(dff(ch[k-1],ch[k-2]),dff(p[i],ch[k-1]))<=0)k--;
//     }
//     ch.resize(k-1);
//     return ch;
// }

// 傾き，切片を返す
// 傾きがバカデカくなるような時，知らん
pair<Real,Real> least_square_method(vector<Point> p){
    Real xy=0,x=0,y=0,x_2=0;
    int n=(int)p.size();
    for(int i=0;i<(int)p.size();i++){
        xy+=p[i].real()*p[i].imag();
        x+=p[i].real();
        y+=p[i].imag();
        x_2+=p[i].real()*p[i].real();
    }
    Real a=(n*xy-x*y)/(n*x_2-x*x);
    Real b=(x_2*y-xy*x)/(n*x_2-x*x);
    return make_pair(a,b);
}


signed main(){
    int n;cin>>n;
    vector<Point> v;
    rep(i,n){
        int a;cin>>a;
        v.push_back(Point(i,a));
    }
    auto [a,b]=least_square_method(v);
    Real x=b;
    Real cost=0;
    rep(i,n){
        cost+=(v[i].imag()-x)*(v[i].imag()-x);
        x+=a;
    }
    cout<<b<<" "<<a<<endl;
    cout<<cost<<endl;
    return 0;
}
yukicoder

結果

テストケース

ソースコード
