Q&A
C - Don’t be cycle
単純無向グラフから辺を取り除き、木にする課題です
https://atcoder.jp/contests/abc288/tasks/abc288_c
以下のコードを提出したのですが、WAになります
なぜなのか教えてほしいです
プログラムの説明
まず入力された情報を、頂点Aがつながっている頂点のリストを、辞書pのp[A]に入れます(#1)
DFSでグラフを探索していき、通ったことのある頂点につけば、その最後の辺を削除し、削除した辺の数cntを1増やします (#2)
最後にcntを出力します (#3)
python
1import sys 2def search(l): #2 3 global cnt 4 if len(p[l[-1]])==1: 5 return 6 for x in p[l[-1]]: 7 if x in l: 8 if x != l[-2]: 9 cnt+=1 10 if l[-1] in p[x]: 11 p[l[-1]].remove(x) 12 p[x].remove(l[-1]) 13 else: 14 search(l+[x]) 15 16n,m=map(int,input().split()) 17sys. setrecursionlimit(10**9) 18p={} 19cnt=0 20for i in range(m): #1 21 a,b=map(int,input().split()) 22 if a not in p: 23 p[a]=[b] 24 else: 25 p[a]+=[b] 26 if b not in p: 27 p[b]=[a] 28 else: 29 p[b]+=[a] 30#print(p) 31if n>0: 32 search([1]) 33#print(p) 34print(cnt) #3
また、なぜか1つREも出します
これもなぜだかわかりません
D - Range Add Query
与えられた数列が、説明されている"いい数列"かどうか判定する課題です
https://atcoder.jp/contests/abc288/tasks/abc288_d
以下のコードを提出したのですが、TLEになります
なぜか教えてほしいです
プログラムの説明
ここでの"いい数列"は、例えばk=3の時、aは1,3,3,2など、1,1,1をうまく位置をずらしながら足すことによって作れる数字です
つまり、その数列を数とみなすと、その数が11...1で割り切れるということです
先程のたとえの場合、1332=111×12ということです
しかし、十進法の場合、1,3,114,2という数列でも、数にすると2442となり、111で割れてしまいます
なので、与えられた数列の絶対値の最大の数をmとし(#1)、十進法ではなくm進法にします
この課題では、数列の、指定された範囲の部分を調べるのをq回行うため、毎回数列をm進法に変換するのは非効率なので、最初に全体をm進法に一文字ずつ変換し、それをリストsに保存しています(#2)
これによって、xからyの範囲の数列を調べたいときは、s[y]からs[x-1]を引けば、その間の数のm進法にした値が素早く得られます(#3)
python
1n,k=map(int,input().split()) 2a=list(map(int,input().split())) 3q=int(input()) 4m=max(max(a),-min(a)) #1 5w=0 6t=1 7for i in range(k): 8 w+=t 9 t*=m 10s=[0] 11t=1 12t2=0 13for i in range(n): #2 14 t2+=(a[i]*t)%w 15 s+=[t2] 16 t*=m 17#print(s) 18for i in range(q): 19 l,r=map(int,input().split()) 20 if (s[r]-s[l-1])%w==0: #3 21 print("Yes") 22 else: 23 print("No")
計算量は O(k+n+q) になるはずなのですが、どうしてもTLEになってしまいます
pythonがCやC++と比べ遅いのは知っていますが、この量の掛け算はやはりpythonでは遅くなってしまうのでしょうか
片方のみの原因でも、お願いします
また、WA,TLEの原因でなくとも、高速化するテクニックや、他にもなにかコメントがあれば、お願いします
回答1件
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
2023/02/05 04:07