なぜiの条件式がこうであるとうまくいくのか

Question

理解したいこと

自分の書いたコードの中でi<25という条件式が出てくるのですが、なぜ25未満の数だとうまくいかないのかを理解したいです。

前提

「競技プログラミングの鉄則」という本を使って学習していて、B12の問題を解いていました。i < 10000などと大きな値をとってACしたのですが、i < xのxの部分をコードが機能する最小の値にしたいと考えいじっていたら、x >= 25で機能することが分かりました。しかし、なぜx >= 25で機能するのか分からなかったので、質問したいと考えました。

以下B12の問題です。

問題文---
正の整数 N が与えられます。
x^3+x=N を満たす正の実数
x を出力してください。ただし、相対誤差または絶対誤差が 0.001 以下であれば正解とします。

制約
1≤N≤100000
N は整数

入力
入力は以下の形式で標準入力から与えられます。

N

※「競技プログラミングの鉄則　米田優峻[著]」問題B12　から引用

問題:https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ck
解答コード:https://github.com/E869120/kyopro-tessoku/blob/main/editorial/chap03/cpp/answer_B12.cpp

--

該当のソースコード

#include <bits/stdc++.h>
using namespace std;

double N, m;
int main() {
    cin >> N;
    double L = 0, R = 100;
    for (int i = 0; i < 25; i++) {
        m = (L + R) / 2;
        if (N < (m * m * m + m)) R = m;
        else L = m;
    }
    cout << m << endl;
}

環境

環境は以下のものを使用しています。
https://atcoder.jp/contests/tessoku-book/custom_test

Answer 1

i < xのxの部分をコードが機能する最小の値にしたい

そもそも目指すべきものが違うのではないでしょうか。「相対誤差または絶対誤差が 0.001 以下」かどうかそのものを検証するのが適当ではないかと考えます。

Comments

[FIREMAX]

ACの基準について再認識するきっかけになりました。ご回答ありがとうございます。

Answer 2

i < xのxの部分をコードが機能する最小の値にしたい

「コードが機能する」かどうかを「以下の環境で標準出力に表示される値が変わらない」かどうかで判断していないでしょうか。

環境は以下のものを使用しています。
https://atcoder.jp/contests/tessoku-book/custom_test

こちらの環境だと有効数字6桁までしか表示されませんが、実際の値はもっと下の桁まで数字が続いています。例えば、表示部分を以下のように変更すると、有効数字8桁まで表示されます。

    cout << setprecision(8) << m << endl;

こちらで試すと、「x >= 25で機能する」というのも変わってくると思います。

追記

ご提示のコードの場合、初期状態で入り込む可能性のある絶対誤差の最大値は100で、ループを1回回すごとにその最大値が半分になります。ループ17回目で0.00076...となり0.001を下回るので、17回やれば確実に問題の条件を満たせます。ただし、ここで求めた値はあくまで絶対誤差の最大値ですし、問題では相対誤差0.001も許容するので、実際にはループ16回で題意を満たす回答となります(以下のコードで確認)。

#include <bits/stdc++.h>
using namespace std;

double f(double m) {
    return m * m * m + m;
}

double inv(double N, int x) {
    double L = 0, R = 100, m = 0;
    for (int i = 0; i < x; i++) {
        m = (L + R) / 2;
        if (N < f(m)) R = m;
        else L = m;
    }
    return m;
}

bool valid(int x) {
    for (int N = 1; N <= 100000; ++N) {
        double m = inv(N, x);
        if (!(f(m - 0.001) <= N && N <= f(m + 0.001) || f(m / 1.001) <= N && N <= f(m / 0.999)))
            return false;
    }
    return true;
}

int main() {
    int ok = 50, ng = 0;
    while (ok - ng > 1) {
        int mid = ng + (ok - ng) / 2;
        if (valid(mid)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

Comments

[FIREMAX]

1つの問題で多くのことを学ぶことができました。最後まで丁寧に教えてくださり、ありがとうございました。

Answer 3

回答ではありません

このまま終わると最後まで理解されないままになりそうですね。

f(x) = x^3 + x

という式はdf/dx = 3x^2 + 1なので常に正です。単調増加であることが分かります。
なので、L≦x≦Rの範囲に、f(x)=Nを満たすxを探すには、f(L)≦N≦f(R)となるL,Rを1つ探してその後二分探索でL,Rの範囲を絞ればいいということになります。
その際、単調増加である以上、絞った範囲では誤差が単調減少していきます。

そこまでわかっていれば、L,M,Rの誤差を計算したときの最も低い誤差がその試行回数での一番正解に近いxなので、それが相対誤差または絶対誤差が 0.001 以下になったら探索を終了することで、最短で正解を得ることが出来ます。

あとは初期値を考えるわけですが、x>0のときf(x)>xなので単純に整数を仮定し、Lは0、R=N(適当)が妥当と分かります。

問題と解法が分かったので、コードにすると、

#include <bits/stdc++.h>
using namespace std;

double f(double x) {
    return x * x * x + x;
}

double binsearch(int N, int& count) {
    count = 1;
    double L = 0, R = N;
    while (R - L > 0.001 && (L>0 ? (R-L)/L : 1) > 0.001) {
        double M = (L + R) / 2;
        double fm = f(M);
        if (fm >= N) R = M;
        else L = M;
        ++count;
    }
    if (N - f(L) < f(R) - N) return L;
    else return R;
}

int main() {
    int N, count;
    cin >> N;
    auto result = binsearch(N, count);
    cout << result << endl;
    cerr << "count: " << count << ", f(x) = " << f(result) << endl;
    return 0;
}

Comments

[FIREMAX]

貴重なご意見ありがとうございます。内容を拝見させていただいた上で、お聞きしたいことが2つございます。
①私の理解がなぜ完璧でないのか。どこで間違っているのか。
②dameoさんの言う、「最短で正解を得る」というのはどういった意味で最短なのか。
以上2点について詳しく説明してくださるとありがたいです。

[退会済みユーザー]

①今聞いているところです
②処理手順が最短ということです

Answer 4

maisumakunさん、actorbugさんご指摘ありがとうございました。自分自身が混乱していました。確かに「コードが機能する」かどうかを「以下の環境で標準出力に表示される値が変わらない」かどうかで判断していて、この問題を解くうえでACとなる基準を見失っていました。相対誤差または絶対誤差が 0.001 以下であれば正解となるので、2の累乗では14乗で10000を超えるので、i < 14でもACとなるのですね。

#include <bits/stdc++.h>
using namespace std;

double N, m;
int main() {
    cin >> N;
    double L = 0, R = 100;
    for (int i = 0; i < 14; i++) {
        m = (L + R) / 2;
        if (N < (m * m * m + m)) R = m;
        else L = m;
    }
    cout << m << endl;
}

Comments

[actorbug]

i < 14 の場合、用意されているテストケースは通るようですが、入力に「1」を与えた場合に絶対誤差・相対誤差ともに0.001を超えます。正しい値は 0.6823... ですが、i < 14 だと 0.6774... ですし、 i < 15 でも 0.6805... なので条件を満たしません。i < 16 で 0.6820... となり、ようやく条件を満たすことができます。

[FIREMAX]

返信ありがとうございます。actorbugさんの回答の追記を拝見しました。ACになったので、てっきり安心してしまっていましたが、確かによくよく考えてみたら、2の累乗では14乗で10000を超えるけど、それだと小数点第三位までの精度で計算できず(0.001が100になるには100000個必要で最小の目盛りが0.001にならなければならないので)、絶対誤差が0.001以下に収まりませんね。そして、相対誤差のことをすっかり意識していませんでした。actorbugさんは絶対誤差・相対誤差の問題を二分探索法を利用して検出し、i<16で条件を満たすと考えられたのですね。しかし、私には2つの疑問が残ります。それを以下に示します。
①i < 16のときどんな場合でも絶対誤差・相対誤差も0.001以下になると言えるのか。
②競技プログラミングという視点で見たとき、どのように解くのが得策なのか(わざわざforループの回数を算出するのは面倒だから、または、①のようなことを競技時間内に証明することは難しいので、確実に大丈夫な大きな値をとるという手法で解くのがよいのか)。
この2点についてお答えいただけるとありがたいです。また、私の発言に間違っていることや、気になることがありましたらその点についてもご指摘いただけると幸いです。

[actorbug]

> ①i < 16のときどんな場合でも絶対誤差・相対誤差も0.001以下になると言えるのか。

「どんな場合でも」成り立つとは言っていません。問題の制約「1≤N≤100000」「Nは整数」の範疇で成り立つという主張です。
上記コメントについては、「入力に「1」を与えた場合」の話しかしていませんし、私の回答の追記については、問題の制約「1≤N≤100000」「Nは整数」を満たすすべてのNで検証しています。(だから「題意を満たす回答」という言い方をしている)
そもそも、L = 0, R = 100で初期化しているのだから、結果がこの範囲に収まらない入力だった場合(-1など)には、正しい出力になりません。

> ②競技プログラミングという視点で見たとき、どのように解くのが得策なのか(わざわざforループの回数を算出するのは面倒だから、または、①のようなことを競技時間内に証明することは難しいので、確実に大丈夫な大きな値をとるという手法で解くのがよいのか)。

競技プログラミングという視点で見るなら、問題の制約を満たす入力に対して時間内に正しい出力をするコードを作れればよいので、わざわざ最小のループ回数を求める必要はありません。証明する時間がもったいないので、確実に大丈夫な大きな値を使うのが望ましいでしょう。(その大きな値で時間超過にならないのであれば)

[FIREMAX]

返信ありがとうございます。2つの質問に丁寧にご回答してくださり、ありがとうございました。