AtCoder ABC 172 D問題

Question

前提・実現したいこと

TLEを無くしたい

発生している問題・エラーメッセージ

cnt = (n*(2*i + (n-1) *i))//2
のコードを
cnt = i*n*(n+1)//2
のように書き換えるとTLEではなくなりました
たったこれだけでなぜ計算量が大幅に変わるのでしょうか？

該当のソースコード

N = int(input())
ans = 0
for i in range(1, N+1):
  n = N//i
  cnt = (n*(2*i + (n-1) *i))//2
  ans += cnt
print(ans)

Comments

[maai]

問題URL、TLEになった提出URL、ACだった提出URLを貼っていただけると助かります

Answer 1

たったこれだけでなぜ計算量が大幅に変わるのでしょうか？

大幅では無いですね。この問題は入力が短く、最大ケースも容易に試せるので、試したほうが良いです。
コードテストで確認しましたが、3196ms と 2587msでした。
なので、「式が短くなったから」しか理由が無さそうです。

あと、Python3とは若干異なるのですが、JITコンパイル機能が効く PyPy3 を使うともっと速いです。
PyPy3はPython3とある程度互換があります。
コードテストで 166ms でした。

Comments

[petrabaron]

ありがとうございます、とてもよくわかりました。
１点質問があるのですが、maaiさんが確認した実行時間はどのように確認するのでしょうか？
下記URLのようなtime関数を活用しますか？それとも別の方法がありますか？
https://www.sejuku.net/blog/23955

[maai]

time等で手元で確認する方法も良いですが、
コードテストという機能がatcoderにあります。
問題とは別にTLEが10秒くらいに設定されていた気がするので、ギリギリ間に合いそうなのか、全く間に合わないのかここで判断できます
https://atcoder.jp/contests/abc172/custom_test

[petrabaron]

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