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

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

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

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

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

Q&A

解決済

1回答

1449閲覧

Atcoder ABC157 D問題 高速化の方法とWA回避

shake9

総合スコア19

Python

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

PyPy

PyPy(パイパイ)は、RPythonで記述されたPythonの実装のひとつです。CPythonとの互換性に重点を置いて開発されており、コードを必要に応じて機械語にコンパイルする「JITコンパイル機能」を備えています。

0グッド

1クリップ

投稿2020/07/02 15:34

発生している問題・実現したいこと

Atcoder157 ABC157 D問題にコードを提出したところ、28件中TLE11件、WA1件となってしまいました。
特にlargeとあるファイルは全てTLEでした。
https://atcoder.jp/contests/abc157/tasks/abc157_d

どこが原因でWAとなるのか、またどこを修正すればTLEとならないのかを教えていただきたいです。
よろしくお願い致します。

該当のソースコード

Python

1n,m,k = map(int,input().split()) 2ab = [[] for i in range(n)] 3for i in range(m): 4 a,b = map(int,input().split()) 5 ab[a-1].append(b-1) 6 ab[b-1].append(a-1) 7cd = [[] for i in range(n)] 8for i in range(k): 9 c,d = map(int,input().split()) 10 cd[c-1].append(d-1) 11 cd[d-1].append(c-1) 12 13ans = [0 for i in range(n)] 14data = [0 for i in range(n)] #見たら1 15for i in range(n): #自分がi 16 if(data[i] != 0): #もう見てたら必要なし 17 break 18 data[i] = 1 #iの人を見る 19 data2 = ab[i] + [i] #iが入るグラフを作る 20 for j in ab[i]: 21 data[j] = 1 22 new_friends = [ab[i]] 23 for fris in new_friends: 24 new = [] #次の深さのリスト 25 for fri in fris: #この層の友人を1人選ぶ 26 for frfr in ab[fri]: #その友人の友人 27 if(data[frfr] == 0): #見てなかったら加える 28 data[frfr] = 1 29 new.append(frfr) #次の深さのリストに足す 30 data2.append(frfr) #グラフに足す 31 if(len(new)==0): 32 break 33 else: 34 new_friends.append(new) 35 36 sam = len(data2) 37 for j in data2: 38 count = sam 39 for ng in cd[j]: 40 if(ng in data2): 41 count -= 1 #ngがいたら除く 42 ans[j] = count - len(ab[j]) -1 #自分と友達を除く 43 44 45print(*ans)

参考にしたファイル

https://atcoder.jp/contests/abc157/submissions/14492334
こちらの方のコードでは全てACでした。

試したこと

PyPyで提出しても結果は同じでした。
問題中のファイルは全てうまく行きました。

他に試した入力は以下などです。
####試行
入力
4 3 1
1 2
2 3
3 4
1 4
出力
1 1 1 1

入力
2 1 0
1 2
出力
0 0

入力
3 3 0
1 2
2 3
3 1
出力
0 0 0

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

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

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

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

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

guest

回答1

0

ベストアンサー

Python

1 if(data[i] != 0): #もう見てたら必要なし 2 break

breakではなくcontinueでしょう。

Python

1 if(ng in data2): 2 count -= 1 #ngがいたら除く

リストからデータを探すinは遅いです。それが2*k回行われるのでここだけで相当な時間です。

投稿2020/07/03 00:15

yudedako67

総合スコア2047

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

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

shake9

2020/07/03 14:28

ありがとうございます! continueの部分はうっかりしていました。 inを用いる代わりに、setの積集合を&でとって解決できました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問