公式

A - Approximation 解説 by MMNMM

初心者の方へ

大きく分けて、次の \(2\) つの方針があります。

  1. 浮動小数点数（float や double, Decimal など）の演算を用いる方法
  2. 整数の演算のみを用いる方法

\(2\) つの方針それぞれについて解説します。

1. 浮動小数点数の演算を用いる方法

浮動小数点数を扱うことができる多くの言語には、「四捨五入を行う」もしくはそれに類する処理を行う関数があります。

この問題は、そのような関数を使うことで解くことができます。

浮動小数点数どうしの四則演算には一般に誤差が含まれますが、今回の問題の制約のもとで（自然な実装を行えば）正しい答えを求められることが示せます。

証明の概略

割り算の結果、\(\dfrac AB\) の小数部分が \(\dfrac12\) 未満なのに結果の小数部分が \(\dfrac12\) 以上になったり、その逆が起きたりすると誤った答えが出てしまいます（入力に含まれる誤差を考えなければ、round 関数は正確な値を返します）。

\(A,B\) は多くの浮動小数点数で正確に表現できるため、誤差が生じうるのは割り算のみです。

（IEEE 754 に従っていれば）浮動小数点数の割り算は真の値を正しく丸めたものが得られることが保証されています。 ここから、特に割り算の結果の真の値とある浮動小数点数 \(\alpha\) の間に別の浮動小数点数がある場合、結果が \(\alpha\) に丸められることはないことが示せます。

制約の範囲内で \(\dfrac AB\) と整数 \(n\) に対する \(n+\dfrac 12\) との間には必ず別の浮動小数点数が（十分な仮数部の長さがあれば）存在することが示せるので、常に正しい答えが得られることが示せます。

実装例は以下のようになります。

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    // A / B を四捨五入して整数にしたものを出力
    cout << round(static_cast<double>(A) / B) << endl;

    return 0;
}

A, B = map(int, input().split())

# A / B を四捨五入して整数にしたものを出力
print(round(A / B))

2. 整数の演算のみを用いる方法

\(\dfrac AB\) に最も近い整数は、\(\dfrac AB+\dfrac12\) 以下の最大の整数です。

整数を整数で割った値を切り捨てて整数にしたものを求める方法は多くのプログラミング言語に用意されているため、\(\dfrac AB+\dfrac12=\dfrac{2A+B}{2B}\) を切り捨てて整数にしたものを求めればよいです。

実装例は以下のようになります。

#include <iostream>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    // (2A + B) / 2B を切り捨てたものが答え
    cout << (2 * A + B) / (2 * B) << endl;

    return 0;
}

A, B = map(int, input().split())

# (2A + B) / 2B を切り捨てたものが答え
print((2 * A + B) // (2 * B))

\(\left\lfloor\dfrac{\lfloor a/b\rfloor}c\right\rfloor=\left\lfloor\dfrac a{bc}\right\rfloor\) や、\(\left\lfloor\dfrac{ab+c}a\right\rfloor=b+\left\lfloor\dfrac ca\right\rfloor\) などを用いることで（ここで、\(\lfloor x\rfloor\) は \(x\) 以下の最大の整数です）、次のような実装でも正しい答えが得られることが示せます。

#include <iostream>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;

    // (A + B / 2) / B を切り捨てたものが答え
    cout << (A + B / 2) / B << endl;

    return 0;
}

A, B = map(int, input().split())

# (A + B / 2) / B を切り捨てたものが答え
print((A + B // 2) // B)

投稿日時:
最終更新: