Posted by 概要
本記事は、2020/5/31に開催されたABC169のB,C問題を整理した内容を記載します。D問題までの回答を目指しているにもかかわらず、まさかのB,C問題でつまづいてしまいました。非常に不甲斐ない結果ですが、しっかりできなかったポイントを整理していきたいと思います。ただ、TwitterやYoutubeのコメントを見ていると同じようにB,Cで苦戦している人が多かったようなので、少しだけほっとしていました。
B – Multiplication2
問題
https://atcoder.jp/contests/abc169/tasks/abc169_b
解説
https://img.atcoder.jp/abc169/editorial.pdf
Youtube
理解
N個の整数Ajを全て掛け合わせして解を求めるという非常にシンプルな問題です。ポイントは2つあって、まず1つはAjは0になることがあるということ。もう1つはAjは最大で10の9乗であり、そのまま全てをかけるとオーバーフローを起こしてしまうということです。python3.0の場合は、int型が多倍長整数であるので基本的にメモリがある分は桁数を使用することができます。なので、単純に毎回掛けて10の18乗を超えていないかをチェックする処理で動作します。
実装
N = int(input())
Aj = list(map(int, input().split()))
ans = 1
ng = False
max = 10**18
for A in Aj:
if A == 0:
ans = 0
break
if ng or ans*A > max:
ans = -1
ng = True
else:
ans *= A
print(ans)参考 – 任意精度演算
https://ja.m.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97
C – Multiplication3
問題
https://atcoder.jp/contests/abc169/tasks/abc169_c
解説
https://img.atcoder.jp/abc169/editorial.pdf
Youtube
理解
与えられたAとBの2つの整数をかけて、解は小数点以下を切り捨てて表示するというC問題にしては簡単すぎる問題だと思って解いたところ、しっかりと罠が仕掛けられていました。それはfloat型の浮動小数点により掛け算を行うと精度が足りず、誤差が発生してしまうというものです。したがって、安全な方法としてはfloatからDecimalに変換して掛け算を行うことで誤差をなくすことができます。注意点としてはpythonのDecimal関数の引数は誤差をなくすためにはStringで引数を指定する必要があるということがあります。
実装
from decimal import Decimal
A, B = map(float, input().split())
ans = int(int(A)*Decimal(str(B)))
print(ans)参考 – 浮動小数点数
https://ja.m.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0