C++|逆数の総和の逆数

Question

問題

AtCorderの過去問です。
N個の整数の列
A1~AN
が与えられます。

これらの逆数の総和の逆数
1/(1/A1 + ... + 1/AN)
を求めてください。 という問題です

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,b = 0;
  cin >> N;

  int arr[N];

  for(int j = 0; j < N; j++){
    cin >> arr[j] ;

    b += arr[j];
  }
  cout << 1/(1/b) << endl;

  return 0;
}

課題

上のようなコードを書いたが実行時にa.exeが動作を終了してしまう。

環境

エディタ　Atom
コンパイラ　MinGW

Answer 1

1/bの結果が0になっているため0除算が発生しています。途中の計算式も間違っています。
正しくは下記のようになるのではないでしょうか。

  double b = 0.0;

  for(int j = 0; j < N; j++){
    cin >> arr[j] ;

    　b += (double)1/arr[j];
  }
  cout << 1/b << endl;

Comments

[yshk0402]

そうでした。
ありがとうございました

[Zuishin]

途中の計算で double を使うと誤差が出るので、これでは通らないと思います。

[kazuma-s]

N = 2, arr[0] = 100000, arr[1] = 100000 のとき、
cout << 1/b で 50000 と表示されますが、
if (1/b == 50000) cout << "OK\n"; else cout << "NG\n"; では、
NG と表示されますね。

[ikadzuchi]

> Zuishinさん
この手の問題はたいてい誤差の許容範囲があります。探したら見つかりましたがやはりこれも誤差を許容しますね。
https://atcoder.jp/contests/abc138/tasks/abc138_b?lang=ja

[Zuishin]

小数を使う以上、誤差の許容があるのは当然ですが、この計算方法だと入力によっては誤差が大きくなりすぎて通らないのではないかと思います。

なぜ思うのかというのは、勘です。これが正解ならあまりに簡単すぎます。

簡単な問題なのだとしたら、この限りではありませんが、合計を求めるロジックとほぼ同じものを問題にするでしょうか？ また一つの数字につき二回も割り算させている意味は？ この辺り、臭いませんか？

式を変形させると割り算は一度で済みます。つまり誤差が少なくなります。その代わりに桁溢れに対処しなくてはならなくなり、問題点が高度になります。ゆえにこちらが正解だと思いました。

ただの勘ですから、簡単な問題だという可能性はもちろん否定できませんが、私なら後者の方法で提出します。

[ikadzuchi]

多倍長演算を自作ですか。
あまりそのような問題が出るとは思いませんね。勘ですが。

[Zuishin]

何度も当たったことがあります。経験ですが。
多倍長とメモ化と順列組み合わせの用意は競技プログラミングをする前には準備をしておくものなんじゃないんでしょうか？

[asm]

Beginner問題だったら多倍長必要なのは珍しいですね

[Zuishin]

ああ、見落としていました。Beginner 問題だったんですね。
それならコードにそこまでの精度は必要ありませんね。
単に簡単な問題だったということですか。

Answer 2

1 / b が 0 になるため、0 除算で落ちているのでしょう。

Comments

[yshk0402]

bをint型からfloat型に変えると普通に実行できました。
ありがとうございました。