質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.46%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

753閲覧

Atcoder ABC294-DのTLEの解消方法を教えてください

FGcoder

総合スコア2

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2023/03/19 14:10

ABC294-DのTLEの解消

AtcoderのABC294のD問題 (https://atcoder.jp/contests/abc294/tasks/abc294_d) に以下のコードを提出したのですが、どうしてもTLEになります
問題の説明は実際の問題を見たほうがわかりやすいので省きます

プログラムの説明
l1で呼ばれたけど行っていない人、l0で呼ばれてない人を管理しています
入力の1文字目が1の時はl0の最小値をheappopしてl1に加えます
1文字目が3の時はl1の最小値を出力します
1文字目が2の時はそれに続く数字をl1からremoveします

python

1import heapq 2n,q=map(int,input().split()) 3l1=set([]) 4l0=list(range(1,n+1)) 5for j in range(q): 6 a=input().split() 7 if a[0]=="1": 8 x=heapq.heappop(l0) 9 l1.add(x) 10 elif a[0]=="3": 11 print(min(l1)) 12 else: 13 l1.remove(int(a[1]))

頑張ってTLEを減らしたんですが、どうしても 01_random_06.txt と 01_random_09.txt という二つのケースのみでTLEが出ます
A, B, CとACしてそのあと80分くらいずっとこのTLE解消しようとしていて(絶対E問題を見るべきだった)コンテスト終了したので、結構悔しいです
なぜTLEになるのか、どうしたら解決できるのか、教えていただきたいです
よろしくお願いします

捕捉
以下のコードでも同じケースのTLEで引っかかりました

python

1n,q=map(int,input().split()) 2l=[0]*n 3p=[] 4l0m=1 5l1=set([]) 6for j in range(q): 7 a=input().split() 8 if a[0]=="1": 9 l1.add(l0m) 10 while l0m in l1: 11 l0m+=1 12 elif a[0]=="3": 13 print(min(l1)) 14 else: 15 l1.remove(int(b))

できればこのTLEの解説もお願いしたいです

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2023/03/19 14:28

set が hashtable なので、min に時間がかかっています。
FGcoder

2023/03/19 15:09

コメントありがとうございます listに変えてみましたが、なぜかわかりませんがむしろTLEが11に増えてしまいます
Zuishin

2023/03/19 15:13

list だと remove に時間がかかります。
melian

2023/03/19 22:26

for j in range(q): を for j in range(q//10): に変更して実行してみてください。すべて WA になりますが、01_random_06.txt と 01_random_09.txt の実行時間が 200 ms を超えていることが判るかと思います。
Zuishin

2023/03/19 23:19

というより、せっかくヒープを使っているのになぜわざわざ他の構造に移すのかわかりません。 受付に足を運ぶ時も、再度呼ばれる時も、既に一度呼ばれていることが保証されているのだから、l0 を丸々 l1 として使用して最初から全員呼ばれたものとして扱い、1 の入力を無視すればいいのでは?
FGcoder

2023/03/21 22:43

返答遅れてすみません list だと remove に時間がかかります。 >>なるほどです このあたりが参考になりませんかね。... >>資料をありがとうございます、勉強させていただきます for j in range(q): ... >>やってみましたがその通りでした というより、... >>これは目からうろこでした 不必要な情報を処理していたんですね
guest

回答2

0

私は普段pythonを使っているわけではないので,完全な答えではないかもしれません。その点ご了承ください。
計算量を悪化させているのはprint(min(l1))の部分だと思われます。setは順序を記憶しないため,最小値を返そうとするとどうしてもすべての要素を見る必要があるからです。
以下のコードはAtCoder上のコードテストにて10秒以上要します。(終了コード9,すなわちTLEが出ます。)

python

1l1=set([]) 2 3for i in range(100000): 4 l1.add(i) 5 6for _ in range(100000): 7 print(min(l1))

一方,以下のコードはTLEになりません。(70ms程度でした)

python

1l1=list([]) 2 3for i in range(100000): 4 l1.append(i) 5 6for _ in range(100000): 7 print(l1[0])

(添え字によるO(1)アクセスは違うだろと思うかもしれませんが,単にmin()がネックになっていると言いたいだけです。)
解決策としては,actorbugさんの回答を参考にするとよいと思います。

投稿2023/03/21 12:28

inthebloom

総合スコア2

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

FGcoder

2023/03/21 22:45

ありがとうごぜいます minの扱いには注意します
guest

0

ベストアンサー

TLE の理由については、コメントで Zuishin さんがおっしゃっている通りで、set の min が遅いからです。
より詳しくは、「特集!知らないと損をする計算量の話」を参照してください。同ページの「3-4. 様々な言語での事情」に、様々なデータ構造における計算量がまとめられています。

解決方法については、コメントで伝えた「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】」を参照してください。試しに、同ページの「解決法3: 優先度付きキュー」からコードを(変数名だけ変えて)コピペして、l1の代わりにそちらを使ったところ、ACになりました。

python

1import heapq 2hp = list() 3hq = list() 4 5def insert(x): 6 heapq.heappush(hp, x) 7 return 8 9def erase(x): 10 heapq.heappush(hq, x) 11 return 12 13def minimum(): 14 while hq and hp[0] == hq[0]: 15 heapq.heappop(hp) 16 heapq.heappop(hq) 17 return hp[0] 18 19n,q=map(int,input().split()) 20l0=list(range(1,n+1)) 21for j in range(q): 22 a=input().split() 23 if a[0]=="1": 24 x=heapq.heappop(l0) 25 insert(x) 26 elif a[0]=="3": 27 print(minimum()) 28 else: 29 erase(int(a[1]))

それ以外にも、公式の解説で説明されている「解法 2 (線形時間で解く方法)」をPythonで実装する方法もあります。

追記

AtCoderだと、sortedcontainers というライブラリが使えるそうです。(atcoder新ジャッジのpypy3.10で入っているライブラリたちを確認より)
こちらでもACできることを確認しました。

python

1from sortedcontainers import SortedList 2import heapq 3n,q=map(int,input().split()) 4l1=SortedList() 5l0=list(range(1,n+1)) 6for j in range(q): 7 a=input().split() 8 if a[0]=="1": 9 x=heapq.heappop(l0) 10 l1.add(x) 11 elif a[0]=="3": 12 print(l1[0]) 13 else: 14 l1.remove(int(a[1]))

投稿2023/03/20 15:04

編集2023/11/19 01:00
actorbug

総合スコア2231

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

FGcoder

2023/03/21 22:48

具体的な解決のコードまで乗せてくださりありがとうございます
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.46%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問