結果

問題 No.1173 Endangered Species
ユーザー koprickykopricky
提出日時 2020-04-29 06:42:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,119 bytes
コンパイル時間 1,252 ms
コンパイル使用メモリ 91,144 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-19 07:26:36
合計ジャッジ時間 4,848 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 -
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <iomanip>
#include <string>
#include <utility>
#include <cassert>
#include <algorithm>
#include <cmath>

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= 60000;    // 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 = 10000;
    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;
}
0