AtCoder Beginner Contest 177 問題C 間違った理由を調べてみた

はじめに

2020/8/29に行われたContest177の問題Cで、絶望するほどハマったので、調べてみました。

問題

考えたこと

まともに計算すると、多分TLEになると思った。
でもちょっと工夫すればなんとかなりそう。

しばし熟考。

求める和が、{(A1+A2+…＋An)^2-(A1^2+A2^2+…+An^2)}÷2 だという結論に達し、コード化。
およそ10分後、完成。

c.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
tmp2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    tmp2 += int(a[i])*int(a[i])

print(int((tmp*tmp-tmp2)/2)%1000000007)

よっしゃ、今日は調子ええで！４問いけるかもしれんな！
と思った矢先、無常の判定が。

ここでフリーズしてしまい、この日は２問で終了。

なんで

コンテスト終了後、解説を見る。わからない。なんで？累積和でもこの計算方法でも、数学的には同じ値になるはずやん。
土曜日はとにかく納得いかなかったので、寝て、心を落ち着かせ、
日曜日に累積和バージョンを書いて、提出してみた。

c_.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
total2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    total2 += int(a[i])*(tmp-int(a[i]))
    tmp -= int(a[i])

print(total2%1000000007)

えええええええええええええ

なんで？なんで同じことをしているのに、片方はWAで片方はACなん？？？

色々試してみた

まずpythonでint型の数字が、どれぐらい大きな数字を扱えるか確認した。
結果、pythonのver3では、メモリが許す限りいくらでも大きな値が使えるとのことだった。
とすると、おかしいのは÷2のところ？
きっと大きな数字の時に、変なことが起きているに違いない。

適当な大きさの数字を10個入力して、２で割る前の数字と２で割った時の数字を表示させてみた。

input_data1

10
1234567 2345678 3456789 4567890 5678901 6789012 7890123 8901234 9012345 1111111

2257615544087530
1128807772043765

これは大丈夫そう。もうちょっと大きくしてみる。

input_data2

10
12345678 23456789 34567890 45678901 56789012 67890123 78901234 89012345 90123456 11111111

225761590208477104
112880795104238560

１の位を見ると、２で割る前が４だから、２で割ったものは２か７になるはず。
なのに０。
ということで、大きな数字を２で割ると、どうもおかしな事が起こるらしい。

どうして２で割れないの

「python 割り算 おかしい」でググったら、以下の記事を見つけました。

Python3で巨大な浮動小数計算の結果が変だったので理由を調べてみた
https://paiza.hatenablog.com/entry/2017/08/01/Python3%E3%81%A7%E5%B7%A8%E5%A4%A7%E3%81%AA%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E8%A8%88%E7%AE%97%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%8C%E5%A4%89%E3%81%A0%E3%81%A3%E3%81%9F%E3%81%AE%E3%81%A7%E7%90%86

うーん、分かったような・・・でもやっぱり分からない。。。
ただ大きい数字は、割り算するとおかしな事が起こりうる、ということなんですね。
一つ賢くなりました。ありがとうございました。

・・・ああああ、悔しい。