前提・実現したいこと
AtCoder Beginner Contest 159 D 問題をPythonで解いているのですが,TLEになってしまいます。
このコードはforループが2つ,どちらもO(n)なので,全体としてもO(n)のはずなのですが,なぜTLEになってしまうのでしょうか。
見たところ,.countが負荷が大きいコマンドなのでしょうか。
他の方の解答を見て,この問題の解法は分かったのですが,なぜ自分のコードでTLEになってしまうのかが良く分かりません。
発生している問題・エラーメッセージ
O(n)のはずなのにTLEを起こしてしまう。
そもそもO(n)でないのか,何かのコマンドが負荷が大きいものなのか,原因を教えてください。
該当のソースコード
Python
1n = int(input()) 2a = list(map(int, input().split())) 3 4def cmb(n): 5 return int(n*(n-1)/2) 6 7goukei = 0 8count = 0 9 10for i in range(n): 11 if a[i] in a[:i]: 12 continue 13 else: 14 count = a.count(a[i]) 15 goukei += cmb(count) 16 17for i in range(n): 18 print(goukei - (a.count(a[i]) - 1)) 19
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。