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

提出ソース

結果

問題	No.1173 Endangered Species
ユーザー	kopricky
提出日時	2020-05-09 19:24:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	85 ms / 2,000 ms
コード長	6,124 bytes
コンパイル時間	910 ms
コンパイル使用メモリ	98,532 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-06 04:13:22
合計ジャッジ時間	2,209 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	7 ms 6,944 KB
testcase_15	AC	6 ms 6,940 KB
testcase_16	AC	41 ms 6,944 KB
testcase_17	AC	66 ms 6,944 KB
testcase_18	AC	80 ms 6,940 KB
testcase_19	AC	79 ms 6,940 KB
testcase_20	AC	81 ms 6,944 KB
testcase_21	AC	85 ms 6,940 KB

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

ソースコード

raw source code

#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 = 100000;
    static const int NUM_DECIMAL_P = 6;
    static const int NUM_DECIMAL_Q = 6;
    static const int MIN_P = 1;    // depends on NUM_DECIMAL_P
    static const int MAX_P = 1000000;    // depends on NUM_DECIMAL_P
    static const int SUM_P = 1000000;    // depends on NUM_DECIMAL_P
    static const int MIN_Q= 600000;    // depends on NUM_DECIMAL_Q
    static const int MAX_Q = 900000;    // 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;
}

yukicoder

結果

テストケース

ソースコード