ROOTS (중, p. 472)

문제#

image.png


어떻게 풀었나?#

주어진 방정식 $f(x)=0$ 을 미분하여 $f'(x)=0$ 에서 극대값을 구하고, 각 극대값 간의 구간에서 $f(x)=0$ 이 되는 $x$를 binary search로 찾았다.


정답 코드#

#include <bits/stdc++.h>
using namespace std;
using pdd = pair<double, double>;
void Dif(vector<double> & cof, vector<double> & ret) {
    if(cof.size()==1) 
    ret.clear();
    ret.resize(cof.size());
    bool flag = true;
    for(int i=cof.size()-1; i>0; i--) {
        ret[i-1] = cof[i]*i;
    }
    for(int i=ret.size()-1; i>=0; i--) {
        if(ret[i]==0) ret.pop_back();
        else break;
    }
    if(ret.empty()) ret.push_back(0);
}
void MakeIntv(vector<pdd> & intv_list, const vector<double> & ex) {
    intv_list.emplace_back(-11.0,ex[0]);
    for(int i=0; i<ex.size()-1; i++) {
        intv_list.emplace_back(ex[i],ex[i+1]);
    }
    intv_list.emplace_back(ex.back(),11.0);
}
double Pow(double x, int n) {
    if(n==0) return 1.0;
    double ret = Pow(x, n / 2);
    if(n%2==0) return ret*ret;
    else return ret*ret*x;
}

double Eq(const vector<double> & cof, double x) {
    double ret = 0;
    for(int i=cof.size()-1; i>=0; i--) {
        ret += cof[i]*Pow(x,i);
    }
    return ret;
}

inline bool Is0(double x) {
    return fabs(x)<1e-9;
}

void Solve(vector<double> & cof, vector<double> & sol) {
    if(cof.size()==2) {
        sol.push_back(-cof[0]/cof[1]);
        return;
    }
    else if(cof.size()<2) return;
    vector<double> dif_cof;
    Dif(cof, dif_cof);

    vector<double> ex; //extremum
    Solve(dif_cof, ex);

    if(ex.empty()) return;

    vector<pdd> intv_list;
    MakeIntv(intv_list, ex);
    for(int i=0; i<intv_list.size(); i++) {
        double lo = intv_list[i].first;
        double hi = intv_list[i].second;
        double flo = Eq(cof,lo);
        double fhi = Eq(cof,hi);

        //실수 오차 때문에 아래 flo, fhi값이 0인지 따로 체크하지 않으면,
        //중근 데이터에서 터질 수 있다.
        if(Is0(flo)) sol.push_back(lo);
        if(Is0(fhi)) sol.push_back(hi);
        if (flo * fhi < 0) {
            if (flo < 0) swap(lo, hi);
            for (int z = 0; z < 100; z++) {
                double mid = (lo + hi) / 2;
                if (Eq(cof, mid) >= 0) lo = mid;
                else hi = mid;
            }
            if (Is0(Eq(cof, lo))) sol.push_back(lo);
        }
    }
}
bool chk[7];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    vector<double> cof,sol;
    while(tc--) {
        int n; cin >> n;
        cof.clear(); cof.resize(n+1);
        for(int i=n; i>=0; i--) {
            cin >> cof[i];
        }
        sol.clear();
        Solve(cof, sol);

        if (!sol.empty()) {
            memset(chk, true, sizeof(chk));
            sort(sol.begin(), sol.end());
            for (int i = 1; i < sol.size(); i++) {
                if (Is0(sol[i] - sol[i - 1])) chk[i] = false;
            }
            n = sol.size();
            for (int i = 1; i < n; i++) {
                if (!chk[i]) sol[i] = sol[--n];
            }
            for(int i=0; i<n; i++) if(Is0(sol[i])) sol[i]=0.0;

            sort(sol.begin(), sol.begin()+n);
            for (int i = 0; i < n; i++) {
                printf("%.10lf ", sol[i]);
            }
            puts("");
        }
    }
    return 0;
}

Comment#

문제 자체는 쉬운데, WA를 엄청 받아서 고통받았다. 나중에 알고보니 Is0()에서 실수 값이 0임을 판단할 때 1e-15로 체크했더니 0인데도 0으로 판단하지 못하는 경우가 있었다. 해당 기준을1e-9, 1e-10수준으로 변경하니 AC를 받았다.

image1.png

알고스팟 채점 데이터는 항상 약하다. 해당 문제의 채점 데이터는 중근 데이터를 포함하지 않는 것 같다. 요즘 알고스팟 OJ는 관리가 전혀 안돼서 고쳐줄리 없겠지만, 문제 푸는 다른 사람들이 볼 수 있지 않을까 해서 아래와 같이 댓글을 남겼다.

image2.png