atcoder ABC 320 D - Relative Positionの説明
・説明
DFSで解ける。Aiから行けるBiをDFSしていき、原点からの距離を(distx, disty)で管理する。
注意点として、入力で
g[b].append((a,-1*c,-1*d))
bから見たaの座標もappendしないといけないことに注意。
import sys sys.setrecursionlimit(10**6) n,m=map(int,input().split()) g=[[] for _ in range(n)] for _ in range(m): a,b,c,d=map(int,input().split()) a-=1 b-=1 g[a].append((b,c,d)) g[b].append((a,-1*c,-1*d)) #bから見たaの位置 #print(g) #原点からの距離. distx=[0 for _ in range(n)] disty=[0 for _ in range(n)] seen=[0 for _ in range(n)] def dfs(v): seen[v]=1 for nv,x,y in g[v]: if seen[nv]: continue #vから行ける点nvの距離を更新. distx[nv]=distx[v]+x disty[nv]=disty[v]+y dfs(nv) dfs(0) #探索済みでないなら"undecidable"を出力。 for i in range(n): if seen[i]==0: print("undecidable") else: print(distx[i],disty[i])
atcoder ABC177 D - Friendsの説明
・説明
答えは連結成分の中で、最大の人数になる。なぜなら最大人数を全部の別々のグループに別けなければいけないからだ。
from atcoder import dsu n,m=map(int,input().split()) uf=dsu.DSU(n) for i in range(m): a,b=map(int,input().split()) a-=1 b-=1 uf.merge(a,b) l=[0 for _ in range(n)] #連結成分毎の合計人数を求める. for i in range(n): l[uf.leader(i)]+=1 print(max(l))
atcoder ARC 106 B - Valuesの勉強
・参考
AtCoder Regular Contest 106 B – Values を解いた記録 – Manuel1024の引きこもルーム
・説明
Union-Findを使って実装した。操作によって連結成分毎の合計は変わらないことので、もし変わっていればNoになる。
atcoderで新しく使えるようになったac-library-python/atcoder at master · not522/ac-library-python · GitHubを使って実装した。
from atcoder import dsu n,m=map(int,input().split()) a=list(map(int,input().split())) b=list(map(int,input().split())) uf=dsu.DSU(n) for i in range(m): c,d=map(int,input().split()) c-=1 d-=1 uf.merge(c,d) a_sum=[0 for _ in range(n)] #操作前の連結成分毎の合計. b_sum=[0 for _ in range(n)] #操作後の連結成分毎の合計. #連結成分毎の合計を求める. for i in range(n): a_sum[uf.leader(i)]+=a[i] b_sum[uf.leader(i)]+=b[i] for i in range(n): if a_sum[i]!=b_sum[i]: print("No") exit() print("Yes")
atcoder ABC 319 E - Bus Stopsの勉強
・参考
ABC319をPythonで解いてみたよ。(A～E問題) - Qiita
・説明
TLEだったので、参考記事を参考にした。プログラムの説明は下のプログラムでコメントアウトしている。
import math n,x,y=map(int,input().split()) p=[] t=[] for i in range(n-1): pi,ti=map(int,input().split()) p.append(pi) t.append(ti) LCM=math.lcm(*[i for i in range(1,9)]) #1-8までの最大公倍数.840. ans=[0 for _ in range(LCM)] #前もって、840までの問題文の答えを用意してansに代入する. for i in range(LCM): ni=i+x #バス停1につくまで. #バスの乗り継ぎ時間. for j in range(n-1): if ni%p[j]==0: ni+=t[j] else: quo=ni//p[j] #商. ni=p[j]*(quo+1)+t[j] #バス停から青木君の家につくまでの時間. ni+=y ans[i]=ni q=int(input()) for _ in range(q): qi=int(input()) quo, MOD=divmod(qi, LCM) print(ans[MOD]+LCM*quo) #例えば、qi=847だとquo=1, MOD=7より、qiが7の答えにLCM*1(LCMで区切られるので)を足す.
atcoder ABC319 C - False Hopeの勉強
・参考
ABC319をPythonで解いてみたよ。(A～E問題) - Qiita
・説明
基本的には参考記事を参考にして、問題文の通りに実装した。
工夫としては
f=[] for _ in range(3): a,b,c=map(int,input().split()) f.append(a) f.append(b) f.append(c)
と入力を受け取ることで、そのまま見ていく順列の位置posに対して、f[pos]で値を取ってこれるようにした。
from itertools import permutations import math f=[] for _ in range(3): a,b,c=map(int,input().split()) f.append(a) f.append(b) f.append(c) tmp=[[0,1,2],[0,3,6],[3,4,5],[6,7,8],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] #当てはまる縦横斜め.8こある. P=permutations([i for i in range(9)]) cnt=0 #for perm in permutations(range(9)): #for perm in P:と同じ。 for perm in P: flag=1 for t in tmp: T=[] for pos in t: #tは[0,1,2]とかでposは0,1,2とか. T.append((perm[pos], f[pos])) #perm[pos]が何番目にpos地点を見たか表す T.sort() #見た順にする. if T[0][1]==T[1][1] and T[1][1]!=T[2][1]: #がっかりするとき. flag=0 break if flag: #がっかりしなかったときをカウントする. cnt+=1 print(cnt/math.factorial(9))
atcoder ABC176 D - Wizard in Mazeの勉強
・やったこと
atcoder ABC 213 E - Stronger Takahashiの勉強 - stosasa’s blogでやった問題と同じようにすれば解けるのでやってみた。0-1BFSで解ける。説明は下でコメントアウトしている。
from collections import deque H,W=map(int,input().split()) sx,sy=map(int,input().split()) sx-=1 sy-=1 gx,gy=map(int,input().split()) gx-=1 gy-=1 field=[input() for _ in range(H)] dx=[1,0,-1,0] dy=[0,1,0,-1] #魔法の回数がdist。大きい値で初期化 dist=[[10**18 for _ in range(W)] for _ in range(H)] #スタートはdist=0、queにスタートを追加 dist[sx][sy]=0 que=deque() que.append((sx,sy)) #0-1BFS #queがからになるまで幅優先探索をやる while len(que)!=0: x,y=que.popleft() #queの先頭のペアを取り出す #普通の移動 for i in range(4): next_x=x+dx[i] next_y=y+dy[i] #場外はスルー if next_x<0 or next_x>=H or next_y<0 or next_y>=W: continue #壁もスルー if field[next_x][next_y]=='#': continue #壁がないとき、queの前から。 if dist[next_x][next_y]>dist[x][y]: dist[next_x][next_y]=dist[x][y] que.appendleft((next_x,next_y)) #魔法の移動 for next_x in range(x-2,x+3): #next_xはx-2からx+2まで動く. for next_y in range(y-2,y+3): if next_x<0 or next_x>=H or next_y<0 or next_y>=W: #場外のとき continue if field[next_x][next_y]=='#': #壁もスルー continue #前の座標のdist[x][y]+1(魔法のぶん+1する)のほうが次のよりも小さいとqueの後ろからいれる if dist[next_x][next_y]>dist[x][y]+1: dist[next_x][next_y]=dist[x][y]+1 que.append((next_x,next_y)) print(dist[gx][gy] if dist[gx][gy]!=10**18 else -1)
atcoder ABC 213 E - Stronger Takahashiの勉強
・参考
AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点) - けんちょんの競プロ精進記録
・やったこと
参考記事をpythonで書いて実装した。パンチすることによって2*2のマスに移動できるのでそれをコスト1、通常の移動をコスト0として0-1BFSをして、実装する。注意点として、パンチしての移動は四隅に行くことができないことに注意。
・備考
提出の際はPyPyで提出してください。pythonだとTLEします。
from collections import deque H,W=map(int,input().split()) field=[input() for _ in range(H)] dx=[1,0,-1,0] dy=[0,1,0,-1] #パンチを繰り出した回数がdist。大きい値で初期化 dist=[[10**18 for _ in range(W)] for _ in range(H)] #スタートはdist=0、queにスタートを追加 dist[0][0]=0 que=deque() que.append((0,0)) #0-1BFS #queがからになるまで幅優先探索をやる while len(que)!=0: x,y=que.popleft() #queの先頭のペアを取り出す #普通の移動 for i in range(4): next_x=x+dx[i] next_y=y+dy[i] #場外はスルー if next_x<0 or next_x>=H or next_y<0 or next_y>=W: continue #壁もスルー if field[next_x][next_y]=='#': continue #壁がないとき、queの前から。 if dist[next_x][next_y]>dist[x][y]: dist[next_x][next_y]=dist[x][y] que.appendleft((next_x,next_y)) #パンチしての移動 for next_x in range(x-2,x+3): #next_xはx-2からx+2まで動く. for next_y in range(y-2,y+3): if next_x<0 or next_x>=H or next_y<0 or next_y>=W: #場外のとき continue if abs(next_x-x)+abs(next_y-y)==4: #四隅はいけない continue #前の座標のdist[x][y]+1(パンチしたぶん+1する)のほうが次のよりも小さいとqueの後ろからいれる if dist[next_x][next_y]>dist[x][y]+1: dist[next_x][next_y]=dist[x][y]+1 que.append((next_x,next_y)) #print(dist) print(dist[H-1][W-1])
・類題
atcoder.jp
