ABC187 E Through Path
内容
Atcoder 187 E問題(500) Through Pathをpython で 解説AC
問題
ポイント
- 木の上で、imos法を使う。
- 適当に頂点を置くと、queryは、次のどちらかに言い換えができる。
- ある頂点 k の子孫に xを足す
- ある頂点 kの子孫以外にxを足す
- rootの子孫にxを足して、kの子孫からxを引く。 *query type2は、a,bをswapすることで、type1と同じになる。
実装
N = int(input()) edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)] Q = int(input()) queries = [list(map(int, input().split())) for _ in range(Q)] # 隣接リスト adjes = [[] for _ in range(N)] for a, b in edges: adjes[a].append(b) adjes[b].append(a) # node 0 を rootとする。 ROOT = 0 # root_ptr[i]: node i の 親の node root_ptr = [-1]*N root_ptr[ROOT] = ROOT # dfs Q = [ROOT] while Q: cur = Q.pop() for nex in adjes[cur]: if root_ptr[nex] != -1: continue root_ptr[nex] = cur Q.append(nex) # queryを捌く ans = [0]*N for t, e, x in queries: e -= 1 a, b = edges[e] # t=2 and swap a,b <=> t=1 if t == 2: a, b = b, a if root_ptr[a] != b: # a is parent -> bの子孫以外にxを足す ans[ROOT] += x # 木全体 ans[b] -= x # bの子孫 else: # b is parent -> aの子孫にxを足す ans[a] += x # aの子孫 # imos Q = [ROOT] visited = [False]*N visited[ROOT] = True # imos on tree while Q: cur = Q.pop() for nex in adjes[cur]: if visited[nex]: continue ans[nex] += ans[cur] visited[nex] = True Q.append(nex) print("\n".join(map(str, ans)))
終わりに
- おわり
- 公式解説がわかりやすくて良い
AtCoder ARC103 E Tr/ee
内容
Atcoder ARC103 のE問題(700) Tr\eeをpythonで解いた。
問題
考えたこと
- S[i]=="1"の時に、N頂点は iとN-iに別れる-> S[i]==1ならS[N-i]==1
- 木だから葉が存在する。そこできると、1とN-1に別れるはず。-> S[1]==0
ポイント
- 頂点のidの大きい方から追加する。(Nをrootとして、N-1,N-2,..と追加していく)
- S[i]=="1"の時、j>iでS[j]=="1"である最小のjと辺をはる。
- すでにN-i個が追加されているから、iとN-iに分ける辺が張れる)
- S[i]=="0"の時、j>iでS[j]=="1"である最小のjと辺をはる。
- これを葉にすることで、1とN-1に別れる辺が張れる
- つまり、iとN-iには別れない。
- S[1]=S[N-1]=1は、チェック済みなので、1とN-1に別れるのは問題ない。
- S[i]=="1"の時、j>iでS[j]=="1"である最小のjと辺をはる。
実装
S=input() N=len(S) #1-originにする #S[0]があるとすると、0,Nに別れることはないので、0 S="0"+S #葉できった時に、1_(n-1)になるはず if S[1]!="1": print("-1") exit() # S[i]=1の時,i_(N-i)に別れる-> S[i]==S[N-i] for s,rev_s in zip(S,reversed(S)): if s!=rev_s: print("-1") exit() prev=N for i in reversed(range(1,N)): print(i,prev) #これまでに、N-i個がすでに気に追加されている。prevとcur(i)の間できると、(i_N-i)に別れる if S[i]=="1": prev=i else: #葉になる(1_N-1)に別れるため、i_(N-i)にはならない。S[1]=S[N-1]=1は決まっている。 pass
終わりに
- 解説AC
ABC013 D 阿弥陀
内容
Atcoder Beginner Contest 013 D問題 「阿弥陀」をpythonで解いた。
問題
阿弥陀くじが一つ与えられる。 そのあみだくじを、D個縦につなげる。 つなげたあと、各スタート地点からたどり着く場所を求めろ。 atcoder.jp
考えたこと
- あみだくじは、同じものをD個つなげる。
- あみだくじ一つ(D=1)の時は、O(M)くらいでシミュレーションできる。
- つなげる数は、D(10**9)なので1回のシミュレーションをD回繰り返すのは無理。
ポイント
効率的にシミュレーションしたい。
- ダブリングする!
2n回の移動で、各startからどこにたどり着くかを計算しておく。
log2(D)程度のシミュレーション回数でD回分の移動を計算できる。
- D=9なら、23+20なので、9回のシミュレーションを二回の計算で行える。
- ダブリングする!
これで、D回のシミュレーションをO(109)からO(log2(10**9))まで減らせるので間に合う。
- (log2(10**9)は30程度)
実装
N,M,D = map(int,input().split()) A = list(map(lambda x:int(x)-1,input().split())) #一回分シミュレーションをする。 dest=list(range(N)) for a in A: #横線があると、aとa+1が入れ替わる dest[a],dest[a+1] = dest[a+1],dest[a] #初回の行先(dest[key]=val, startがkeyの時に、valにたどり着く dest={v:i for i,v in enumerate(dest)} #ダブリングする DUB[i][j]= startがiで、2**i回移動する時に、たどり着く場所 DUB=[[-1]*N for _ in range(D.bit_length())] #初期化(一回分のシミュレーションの結果で、DB[0]を初期化する for key,val in dest.items(): DUB[0][key]=val #DUBを埋めていく。 D回の移動を求めるのには、2**(D.bitlen-1)まで必要。 #(考え方):2**(i-1)回の移動を、2回繰り返すと2**iの移動になる。 for i in range(1,D.bit_length()): for key in range(N): DUB[i][key] = DUB[i-1][DUB[i-1][key]] #求めたダブリングの結果を使って、答えを求める。 ans=list(range(N)) for i in range(D.bit_length()): if D>>i &1:#Dをsum(2**x)で表す時に2**iを使う for key in range(N): #2**i回の移動を適応する。 ans[key]=DUB[i][ans[key]] print("\n".join(map(lambda x:str(x+1),ans)))
終わりに
- 備忘録
ABC013 D 阿弥陀
内容
Atcoder Beginner Contest 013 D問題 「阿弥陀」をpythonで解いた。
問題
阿弥陀くじが一つ与えられる。 そのあみだくじを、D個縦につなげる。 つなげたあと、各スタート地点からたどり着く場所を求めろ。 atcoder.jp
考えたこと
- あみだくじは、同じものをD個つなげる。
- あみだくじ一つ(D=1)の時は、O(M)くらいでシミュレーションできる。
- つなげる数は、D(10**9)なので一回一回シミュレーションするのは無理。
ポイント
- 効率的にシミュレーションしたい。
実装
終わりに
ABC170 E問題 Smart Infants
内容
- ABC170のE問題(500) Smart Infantsを解いた。
- コンテスト中には解けなかったが、この類の問題を解けるようになりたいので、メモで残す。
問題
- 園児と幼稚園がある。
- 園児は、それぞれどこかの幼稚園に所属していて、atcoderのrateを持っている。 *園児は、転園をする。(query)
- 各queryの後に、各幼稚園の(所属園児のrateの最大値)を求め、それの最小値を求める。
ポイント
- 各幼稚園はheapqを持っておいて、最大のrateを求めれるようにする。
- Seg木を作って、各幼稚園の最大rateをノードとしてもち、最大rateの最小値を求めれるようにする。
- 高速化のために、各園児の現在の所属する幼稚園を記録しておくと良い。
難しかったとこ
- 転園によって、園児が出ていく幼稚園と、入ってくる幼稚園がある。
- 入ってくる幼稚園は、heappushするだけなので、簡単
- 出ていく方は、heapqから要素を取り除く必要がある。
- それが最大値ならheappopで良いが、そうでないとheapqの途中の値を取り除く必要が出てきて、それは辛い。
ポイント
- それが最大値ならheappopで良いが、そうでないとheapqの途中の値を取り除く必要が出てきて、それは辛い。
- 実際に取り除く処理を毎回するのではなく、サボって必要になった時にやる!!!
実装
import heapq from collections import defaultdict class SegmentTree(): ''' 非再帰 segment tree ''' def __init__(self, n, func, init=float('inf')): ''' n->配列の長さ func:func(a,b)->val, func=minだとRMQになる 木の高さhとすると, n:h-1までのノード数。h段目のノードにアクセスするために使う。 data:ノード。 parent:k->child k*2+1とk*2+2 ''' self.n = 2**(n-1).bit_length() self.init = init self.data = [init]*(2*self.n) self.func = func def set(self, k, v): ''' あたいの初期化 ''' self.data[k+self.n-1] = v def build(self): ''' setの後に一斉更新 ''' for k in reversed(range(self.n-1)): self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) def update(self, k, a): ''' list[k]=aに更新する。 rootまで更新 ''' k += self.n-1 self.data[k] = a while k > 0: k = (k-1)//2 self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2]) def query(self, l, r): ''' [l,r)のfuncを求める ''' L = l+self.n R = r+self.n ret = self.init while L < R: if R & 1: R -= 1 ret = self.func(ret, self.data[R-1]) if L & 1: ret = self.func(ret, self.data[L-1]) L += 1 L >>= 1 R >>= 1 return ret ############ #入力の処理 ############ N,Q = map(int,input().split()) infants=[] #各園児の初期状態 kinder:(kindergarden)幼稚園の意 for _ in range(N): rate,kinder_id = map(int,input().split()) infants.append((rate,kinder_id-1)) query = [] for _ in range(Q): child_id, rate = map(lambda x:int(x)-1,input().split()) query.append((child_id,rate)) ############## #初期状態を作る ############## MAXV=2*(10**5)+1 #幼稚園の最大数 belong = [-1]*N #各園児の所属 (kinder_id,rate) kinder = defaultdict(list) #各園についての、rateのheapq(-rate,child_id) maxs = [float("inf")]*MAXV #各園の最強園児のrate #初期値 for child_id,(rate,kinder_id) in enumerate(infants): belong[child_id]=(kinder_id,rate) heapq.heappush(kinder[kinder_id],(-rate,child_id)) #maxが欲しいからマイナスをつけてheapqに入れる #seg木を作る Seg = SegmentTree(MAXV,min,float("inf")) for kinder_id in kinder.keys(): (rate,child_id) = kinder[kinder_id][0] #kinder[kinder_id][0]は、幼稚園kinder_idの最強園児 Seg.set(kinder_id,-rate) Seg.build() ############## #queryの処理 ############# for child_id,to in query: #所属の更新 (from_,rate) = belong[child_id] belong[child_id] = (to,rate) #転園の処理 if kinder[from_][0][1]==child_id:#転園する奴が、その園の最強園児なら２番目に強い奴が新しく最強園児になる。 heapq.heappop(kinder[from_])#転園する人を消す #新しい最強を見つける while kinder[from_]: saikyo_child_id = kinder[from_][0][1] if belong[saikyo_child_id][0]==from_: #もしそいつが、from_に所属しているなら、そいつはfrom_で最強 break else:#他の園のやつ(転園処理をさぼったから残ってるやつ)ならremove heapq.heappop(kinder[from_]) if kinder[from_]: #kinder[frmo_]の先頭には、新しく最強園児になる奴がきてる。 Seg.update(from_, -kinder[from_][0][0]) else:#誰もいない場合 Seg.update(from_, float("inf")) else: pass#転園するのが最強園児でないなら、segを更新しなくていいから、何もしない。heapqからのremoveはサボる。(あとでやる) #入園の処理 heapq.heappush(kinder[to],(-rate,child_id)) Seg.update(to,-kinder[to][0][0]) #segに各園の最大値が入っているから、その最小値を求める print(Seg.query(0,MAXV+1))
終わりに
- heapqから、先頭以外の要素を取り除きたい気持ちになったときの解決法を学べた気がする。
- 普通に削除するのはpythonだとできない気がしてて、後から処理する方法があるとしれてよかった。
