#471530 (C++17) No.1173 Endangered Species

提出ソース

結果

問題	No.1173 Endangered Species
ユーザー	kopricky
提出日時	2020-04-26 22:14:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	RE (最新) AC (最初)
実行時間	-
コード長	6,271 bytes
コンパイル時間	872 ms
コンパイル使用メモリ	97,976 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-05 19:25:34
合計ジャッジ時間	4,431 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <string>
#include <utility>
#include <cassert>
#include <algorithm>
#include <cmath>
#define show(x) std::cout<<#x<<" = "<<(x)<<std::endl
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define sar(a,n) {std::cout<<#a<<":";rep(pachico,n)std::cout<<" "<<a[pachico];std::cout<<std::endl;}

class Solver
{
private:
    static const int MIN_N = 1;
    static const int MAX_N = 10000;
    static const int NUM_DECIMAL_P = 5;
    static const int NUM_DECIMAL_Q = 5;
    static const int MIN_P = 0;    // depends on NUM_DECIMAL_P
    static const int MAX_P = 100000;    // depends on NUM_DECIMAL_P
    static const int SUM_P = 100000;    // depends on NUM_DECIMAL_P
    static const int MIN_Q= 10000;    // depends on NUM_DECIMAL_Q
    static const int MAX_Q = 90000;    // depends on NUM_DECIMAL_Q
    static const int MIN_A = 0;
    static const int MAX_A = 1000;
    enum message
    {
        CORRECT, ERROR
    };
    int N;
    double *p, *q;
    int *A;
    double answer;

public:
    Solver(){}
    ~Solver();
    void operator()();

private:
    void input();
    message check_int_range(const int value, const int MIN_VAL, const int MAX_VAL);
    // [MIN_VAL, MAX_VAL]
    std::pair<int, message> scan_integer(const int MIN_VAL, const int MAX_VAL);
    // [MIN_VAL, MAX_VAL]
    std::pair<double, message> scan_floating_point
        (const int NUM_DECIMAL, const int MIN_VAL, const int MAX_VAL, int& check_sum);
    message scan_N();
    message scan_p();
    std::pair<double, message> scan_p_element(int& sum);
    message scan_q();
    std::pair<double, message> scan_q_element();
    message scan_A();
    void solve();
    double solve_impl();
    void output();
};

Solver::~Solver()
{
    delete[] p;
    delete[] q;
    delete[] A;
}

void Solver::operator()()
{
    solve();
}

void Solver::input()
{
    const auto flag_N = scan_N();
    if(flag_N == ERROR)
        assert(false);
    const auto flag_p = scan_p();
    if(flag_p == ERROR)
        assert(false);
    const auto flag_q = scan_q();
    if(flag_q == ERROR)
    {
        delete[] p;
        assert(false);
    }
    const auto flag_A = scan_A();
    if(flag_A == ERROR)
    {
        delete[] p;
        delete[] q;
        assert(false);
    }
}

Solver::message Solver::check_int_range(const int value, const int MIN_VAL, const int MAX_VAL)
{
    return (value < MIN_VAL || value > MAX_VAL) ? ERROR : CORRECT;
}

std::pair<int, Solver::message> Solver::scan_integer(const int MIN_VAL, const int MAX_VAL)
{
    std::string s;
    std::cin >> s;
    const int value = std::stoi(s);
    const Solver::message mes = check_int_range(value, MIN_VAL, MAX_VAL);
    return {value, mes};
}

std::pair<double, Solver::message> Solver::scan_floating_point
    (const int NUM_DECIMAL, const int MIN_VAL, const int MAX_VAL, int& check_sum)
{
    std::string s;
    std::cin >> s;
    if((int)s.size() != NUM_DECIMAL + 2)
        return {0.0, ERROR};
    double value = 0.0, digit = 1.0;
    int check_value = 0;
    Solver::message mes = CORRECT;
    for(int i = 0; i < (int)s.size(); ++i)
    {
        if(i == 1)
        {
            if(s[i] != '.')
            {
                mes = ERROR;
                break;
            }
        }
        else
        {
            if(isdigit(s[i]))
            {
                value += digit * (int)(s[i] - '0');
                digit *= 0.1;
                check_value = check_value * 10 + (int)(s[i] - '0');
            }
            else
            {
                mes = ERROR;
                break;
            }
        }
    }
    if(check_int_range(check_value, MIN_VAL, MAX_VAL) == ERROR)
        mes = ERROR;
    check_sum += check_value;
    return {value, mes};
}

Solver::message Solver::scan_N()
{
    const auto [value, mes] = scan_integer(MIN_N, MAX_N);
    if(mes == CORRECT)
        N = value;
    return mes;
}

Solver::message Solver::scan_p()
{
    p = new double[N];
    int sum = 0;
    Solver::message mes = CORRECT;
    for(int i = 0; i < N; ++i)
    {
        const auto [value, tmp_mes] = scan_p_element(sum);
        if(tmp_mes == ERROR)
        {
            mes = ERROR;
            break;
        }
        p[i] = value;
    }
    if(sum != SUM_P)
        mes = ERROR;
    if(mes == ERROR)
        delete[] p;
    return mes;
}

std::pair<double, Solver::message> Solver::scan_p_element(int& sum)
{
    return scan_floating_point(NUM_DECIMAL_P, MIN_P, MAX_P, sum);
}

Solver::message Solver::scan_q()
{
    q = new double[N];
    int ignore = 0;
    Solver::message mes = CORRECT;
    for(int i = 0; i < N; ++i)
    {
        const auto [value, tmp_mes] = scan_q_element();
        if(tmp_mes == ERROR)
        {
            mes = ERROR;
            break;
        }
        q[i] = value;
    }
    if(mes == ERROR)
        delete[] q;
    return mes;
}

std::pair<double, Solver::message> Solver::scan_q_element()
{
    int ignore = 0;
    return scan_floating_point(NUM_DECIMAL_Q, MIN_Q, MAX_Q, ignore);
}

Solver::message Solver::scan_A()
{
    A = new int[N];
    Solver::message mes = CORRECT;
    for(int i = 0; i < N; ++i)
    {
        const auto [value, tmp_mes] = scan_integer(MIN_A, MAX_A);
        if(tmp_mes == ERROR)
        {
            mes = ERROR;
            break;
        }
        A[i] = value;
    }
    if(mes == ERROR)
        delete[] A;
    return mes;
}

void Solver::solve()
{
    int N;
    double *p, *q;
    int *A;
    input();
    answer = solve_impl();
    output();
}

double Solver::solve_impl()
{
    double l = 0.0, r = 1.0;
    auto f  = [&](const double x)
    {
        double result = x;
        for(int i = 0; i < N; ++i){
            result -= p[i] * (1 - q[i]) / (1 - q[i] * x);
        }
        return result;
    };
    for(int i = 0; i < 60; ++i){
        double mid = (l + r) / 2;
        if(f(mid) < 0.0){
            l = mid;
        }else{
            r = mid;
        }
    }
    double result = 0.0;
    for(int i = 0; i < N; ++i){
        result += A[i] * log((1 - q[i]) / (1 - q[i] * l));
    }
    return result;
}

void Solver::output()
{
    std::cout << std::fixed << std::setprecision(12) << answer << std::endl;
}

void func()
{
    class Solver solver;
    solver();
}

int main()
{
    func();
    return 0;
}

yukicoder

結果

テストケース

ソースコード