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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

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

Q&A

解決済

1回答

242閲覧

Atcoder ABC282 D問題 TLEの原因が分かりません

pythonbeginner

総合スコア2

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

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

0グッド

0クリップ

投稿2023/06/07 06:30

編集2023/06/07 19:27

Atcoder ABC282 D問題
https://atcoder.jp/contests/abc282/tasks/abc282_d
TLEの原因が分かりません

以下のコードに対して、
(100000 0)のような(nの大きい)入力をするとTLEします。
col関数で計算量が多くなってしまっているのだろうとは思うのですが、
この入力に対して、各colは計算量O(1)ではないのでしょうか?

どなたか回答よろしくお願いします。

プログラムの概要:
・入力に対して、グラフの作成とunion-find木の作成を同時に行う。
・col関数で、各独立した木に対して(union-findで取得した根が属する木に対して)二分グラフの判定および白黒の割り当てを行う
・n*(n-1)//2から、辺の本数であるmと二分グラフで得た白同士黒同士で結ぶことのできない組み合わせを引く

試したこと:
・sampleはすべて通る
・提出の結果、半分ほどがTLEになり、他はAC
・10000 0などの入力に対してTLEになることから、nが大きい場合に失敗すると考えている
・入力(10 0)でcol関数のwhileの直後にprint(keep)を行っても、無駄なループが発生している様子はない

Python

1from collections import deque 2 3def col(graph,x,size): #二分グラフの判定 4 l=[0,0] 5 check=[False]*size 6 color=[False]*size 7 check[x]=True 8 color[x]='b' 9 l[0]+=1 10 keep=deque([x]) 11 while keep: 12 k=keep.popleft() 13 for i in graph[k]: 14 if check[i]: 15 if color[k]==color[i]: 16 return(0) 17 else: 18 check[i]=True 19 if color[k]=='w': 20 color[i]='b' 21 l[0]+=1 22 elif color[k]=='b': 23 color[i]='w' 24 l[1]+=1 25 keep.append(i) 26 return(l) 27 28def find(x): #union-find 29 if roots[x]<0: 30 return(x) 31 else: 32 roots[x]=find(roots[x]) 33 return(roots[x]) 34 35def union(x,y): 36 x=find(x) 37 y=find(y) 38 if x==y: 39 return 40 else: 41 if roots[x]>roots[y]: 42 x,y=y,x 43 roots[x]+=roots[y] 44 roots[y]=x 45 46n,m=map(int,input().split()) 47graph=[[] for _ in range(n)] 48roots=[-1]*n 49 50for _ in range(m): #グラフの作成 51 x,y=map(int,input().split()) 52 x-=1 53 y-=1 54 graph[x].append(y) 55 graph[y].append(x) 56 union(x,y) 57 58ans=n*(n-1)//2-m 59for i in range(n): #根なら二分グラフ判定 60 if roots[i]<0: 61 l=col(graph,i,n) 62 if l==0: 63 print(0) 64 exit() 65 else: 66 ans-=l[0]*(l[0]-1)//2+l[1]*(l[1]-1)//2 67print(ans)

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

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

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

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

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

1T2R3M4

2023/06/07 06:34

プロファイリング結果を質問に追記していただけませんか。
guest

回答1

0

自己解決

リストの作成にも計算量が存在することを知らなかった。
リストの作成は関数の外でよかった。

投稿2023/06/07 10:27

pythonbeginner

総合スコア2

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問