ABC390のB問は、与えられた整数の数列が等比数列であるかどうかを判断する問題です。
単純に求めようとするとWAになる
等比数列の問題ですので、「等比数列を求める計算をして、与えられた配列と比較して値が正しいかを判断する」が一番シンプルな考え方になります。
しかし上記の方法で実装するとエラーになります。
なぜか、そしてどうすれば回避できるかを解説します。
WAのコード
初項と公比を求めて、順番に計算し、各配列と比較して正しいかどうかを確かめるコードです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
n = int(input())
a_list = list(map(int, input().split()))
flg = True
a = a_list[0] # 初項
r = a_list[1] / a_list[0] # 公比
for i in range(n):
tmp = a * pow(r, i)
if a_list[i] != tmp:
flg = False
break
if flg:
print("Yes")
else:
print("No")
|
一見良さそうに見えますが、WAで通らない…
なぜダメなのか
浮動小数点演算 (r = a_list[1] / a_list[0] や pow(r, i)) を使うと、丸め誤差が発生する可能性があります。特に r が小数の場合、計算結果が誤差によって正確な整数にならず、a_list[i] と一致しないケースが考えられます。
コード修正後
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
n = int(input())
a_list = list(map(int, input().split()))
flg = True
a = a_list[0] #初項
r = a_list[1] / a_list[0] # 公比
for i in range(n-1):
tmp = a_list[i] * r
if tmp != a_list[i+1]:
flg = False
break
if flg:
print("Yes")
else:
print("No")
|
for文中の計算を修正しました。
配列に公比をかけた値を求めてtmpに代入します。このtmpは配列1つ後ろの数と合うはずなので、間違っていればflgをFalseにできます。
割り算を使わないようにしました。
無事にACできました。
まとめ
- 割り算を使うと丸め誤差が発生しWrong Answerになる可能性がある
- 割り算を使わずに、乗算で計算できるようなロジックを考えることがポイント