Pythonの小数計算について

Question

#AtcoderのGrand Contest（8月9日開催）のA問題について
問題）
N個の実数A1,A2,...ANが与えられます。添字のペア（i,j）(i<j)であって、積Ai,Ajが整数であるようなものの個数を求めてください。
#入力

N
A1
A2
.
.
.
AN

#例

#入力
11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001
#出力
8

これに対しての私のコードはこれです。

from decimal import Decimal
n=int(input())
A=[float(input()) for _ in range(n)]
multiple=[]
for i in range(1,n):
    for j in range(n-i):
        ans=Decimal(A[i-1])*Decimal(A[i+j])
        if float(ans).is_integer():
            multiple.append(ans)
print(len(multiple))

このコードを例をテストケースにして実行すると９になってしまいます。どのようにすればいいでしょうか？小数の積の問題なのでしょうか？
また実行時間超過については十分承知です。」実行時間をこのコードを改造して短くすにはどうすればよいでしょうか？

Comments

[tiitoi]

問題の URL を追記できますか?

[Charowan]

https://atcoder.jp/contests/agc047/tasks/agc047_a

Answer 1

動かしたところ、0.999999999 * 1.000000001を整数と判断していました。
この手の挙動はfloatが怪しいです。floatを使わないようにすれば治りそう。

1. inputは文字列として受け取ってDecimalにキャストする
2. 整数判定はDecimalの機能(Inexact)で判定する

Charowanさんのコードに↓のようにちょっと手を入れたら私の環境では8になりました。

from decimal import Decimal, Inexact
from decimal import localcontext

# いちいちinputを打つのが面倒臭いのでハードコーディング
n=11
target=[
  "0.9",
  "1",
  "1",
  "1.25",
  "2.30000",
  "5",
  "70",
  "0.000000001",
  "9999.999999999",
  "0.999999999",
  "1.000000001",
]
A=[Decimal(x) for x in target]
count=0
for i in range(1,n):
  for j in range(n-i):
    with localcontext() as ctx:
      ans=A[i-1]*A[i+j]
      ans.to_integral_exact()
      count += 1 if not ctx.flags[Inexact] else 0 
print(count)

Comments

[Charowan]

回答ありがとうございます。
localcontext() とctx.flags[Inexact]はどのような役割なのでしょうか？

[Thrush]

localcontext()はDecimalを使った直前の計算についての情報(桁溢れがあった、0割だった、など)を取得する関数です
https://docs.python.org/ja/3/library/decimal.html#decimal.localcontext

ctx.flags[Inexact]はlocalcontext()で取得した情報のうち、Inexact(=値の丸め込みがあったかどうか)のフラグを参照しています
https://docs.python.org/ja/3/library/decimal.html#decimal.Inexact

したがって、以下のようなロジックになります
* A[i-1]*A[i+j]を掛け算し、結果をansとする
* ansを整数に変換する(=to_integral_exact())
* 整数の変換で値の丸め込みがなければcountに+1する

[Charowan]

分かりやすい解説有難うございました！