ダイクストラ法をPythonで
ダイクストラ法
最短経路問題に対する解法
辺の重みに負がないときに限る。
計算量は隣接行列を用いた場合O(|V2|) heap で処理するとO(|E|log|V|)
from heapq import * q = [] # heapq.heapify(q) inf = float("INF") def djk(start_node,num_node): dist = [inf]*num_node queqe = [(0,start_node)] dist[start_node] = 0 used = [False] * num_node while queqe: frm = heappop(queqe)[1] used[frm] = True for to, cost in adj[frm]: if used[to] == False and dist[frm] + cost < dist[to]: dist[to] = dist[frm] + cost heappush(queqe,(dist[to],to)) return dist # ノード数, エッジ数, 始点ノード v, e= map(int, input().split()) # adj[s]: ノード s に隣接する(ノード, 重み)をリストで持つ adj = [[] for _ in range(v)] for i in range(e): s, t, d = map(int, input().split()) s-=1 t-=1 adj[s].append((t, d)) adj[t].append((s, d)) m = inf for start in range(v): d = djk(start,v) m = min(m,max(d)) # print(d) print(m)
https://atcoder.jp/contests/abc012/tasks/abc012_4
両方向に辺をはる。 辺の数が少ないため始点を変えてすべて試す。 それぞれのリストの最大値をとり その中の最小値を出力
from heapq import * q = [] # heapq.heapify(q) inf = float("INF") def djk(s_node,num_node): d = [inf]*num_node q = [(0,s_node)] d[s_node] = 0 used = [False] * num_node while q: frm = heappop(q)[1] used[frm] = True for to, cost in adj[frm]: if used[to] == False and d[frm] + cost < d[to]: d[to] = d[frm] + cost heappush(q,(d[to],to)) return d # ノード数, エッジ数, 始点ノード v, e= map(int, input().split()) # adj[s]: ノード s に隣接する(ノード, 重み)をリストで持つ adj = [[] for _ in range(v)] for i in range(e): s, t, d = map(int, input().split()) s-=1 t-=1 adj[s].append((t, d)) adj[t].append((s, d)) m = inf for start in range(v): d = djk(start,v) m = min(m,max(d)) # print(d) print(m)
参考サイト
heapをPythonで
heapをPythonで
heapの実装を一からPythonでやってみたよ Classを使ったものと使ってないものの二つ。
Classなしのもの
# heap_last_index = 0 def insert(heap,obj): # heap_last_index += 1 heap.append(obj) # print(heap) i = len(heap)-1 while i > 0: if heap[(i-1)//2] > heap[i]: # chech the parents nodes heap[(i-1)//2] , heap[i] = heap[i] , heap[(i-1)//2] i = (i-1)//2 else: return def deletemin(heap): obj = heap[0] heap[0] = heap.pop() print(obj) # heap_last_index -= 1 i = 0 while i < (len(heap)-1)//2: if heap[i] > heap[i*2+1]: if heap[i*2+2] < heap[i*2+1]: heap[i],heap[i*2+2] = heap[i*2+2],heap[i] i = i*2+2 else: heap[i],heap[i*2+1] = heap[i*2+1],heap[i] i = i*2+1 elif heap[i] > heap[i*2+2]: heap[i],heap[i*2+2] = heap[i*2+2],heap[i] i = i*2+2 else: return heap = [] insert(heap,1) insert(heap,2) insert(heap,3) insert(heap,6) insert(heap,3) insert(heap,3) deletemin(heap) deletemin(heap) print(heap)
Classありのもの
class heap: def __init__(self, n): inf = float("INF") self.data = [inf for _ in range(n)] self.last = 0 def insert(self,obj): self.last += 1 self.data[self.last] = obj i = self.last while i>0: if self.data[(i-1)//2] > self.data[i]: self.data[(i-1)//2] , self.data[i] = self.data[i] , self.data[(i-1)//2] i = (i-1)//2 else: return def print_lis(self): print(self.data) def deletemin(self): obj = self.data[0] self.data[0] = self.data[self.last] # print(obj) self.last -= 1 i = 0 while i < (self.last-1)//2: if self.data[i] > self.data[i*2-1]: if self.data[i*2+2] < self.data[i*2+1]: self.data[i] , self.data[i*2+2] = self.data[i*2+2] , self.data[i] i = i*2+2 else: self.data[i] , self.data[i*2+1] = self.data[i*2+1] , self.data[i] i = i*2+1 elif self.data[i] > self.data[i*2+2]: self.data[i] , self.data[i*2+2] = self.data[i*2+2] , self.data[i] i = i*2+2 else: break return obj h = heap(10) h.insert(103) h.insert(110) h.insert(310) h.insert(120) print(h.deletemin()) h.print_lis()
ABC 183 さくさくまとめ
ABC 183 さくさくまとめ
しいしい
ABC183のまとめやってくよー E解けなかったから早ときに助けられた感じかな
A - ReLU
ReLU関数を作ろうって問題 タイトルだけで実装がわかって少しくすっと来たよね
x = int(input()) print(max(0,x))
B - Billiards
二点が与えられるのでX軸に当たってからもう片方の点に移動する場合にX軸上のどの点に当たるかという問題。 幾何がきてかなりびびったよね
考察ノートは2つ考えた。本番は<Ⅰ>の方を実装したが<Ⅱ>のほうが絶対かんたんっておもう
<Ⅰ>
a,b,c,d = map(int,input().split()) C = c-a D = d+b e = d - D/C*c A = D/C print(-e/A)
<Ⅱ>
a,b,c,d = map(int,input().split()) print(a+(c-a)*b/(b+d))
C - Travel
順列型全探査だね。itertoolsまとめないとなーってお気持ち。 どこからどこへ行くってのが必要なので一個前添字を保管するのを忘れない!
import itertools n,k = map(int,input().split()) Lis = [] for i in range(n): tmp_list = list(map(int,input().split())) Lis.append(tmp_list) patterns = list(itertools.permutations(range(1,n))) #順列生成 ans = 0 for pattern in patterns: before_index = 0 tmp_sum = 0 check_lis = [0] for index in pattern: tmp_sum += Lis[before_index][index] before_index = index check_lis.append(index) tmp_sum+=Lis[before_index][0] #back to start # print(tmp_sum,check_lis) if tmp_sum == k:ans+=1 print(ans)
D - Water Heater
問題分概要:区間[S,T)にPというがN個与えられます。区間の総和がWを超えることが存在するか否か判断しなさい。
最初セグ木かなおもったけどいもすで瞬殺だね。セグ木も練習足りてないからここらへんで悩むのは少しもったいないかな。
n,w = map(int,input().split()) dp = [0]*(2*10**5+10) l = [] for i in range(n): s,t,p = map(int,input().split()) l.append([s,t,p]) dp[s]+=p dp[t]-=p for i in range(len(dp)-1): dp[i+1] += dp[i] M = 0 for i in dp: M = max(M,i) if M <= w: print("Yes") else: print("No")
E - Queen on Grid (解説AC)
問題概要:チェスのクイーンが右、下、右下飲み進める場合に盤面の左上(1,1)から右下(H,W)まで行く方法は何通りあるか。”#”は進むことができないマスとする。
EDPCのGrid1を思い浮かべたけどうーんってかんじで結局止まってしまった。こういう問題見ると組み合わせとかするのかなって思うけどとても単純なDPで行けたりするから練習不足だね。またまとめる。
h,w=map(int,input().split()) mod=10**9+7 dp=[[0]*(w+1) for i in range(h+1)] X=[[0]*(w+1) for i in range(h+1)] Y=[[0]*(w+1) for i in range(h+1)] Z=[[0]*(w+1) for i in range(h+1)] dp[0][0]=1 l = [] MOD = 10**9+7 for i in range(h): t_l = input() l.append(t_l) for i in range(h): for j in range(w): if i + j == 0:continue if l[i][j]!='#': if j > 0: X[i][j] = X[i][j-1] + dp[i][j-1] if i > 0: Y[i][j] = Y[i-1][j] + dp[i-1][j] if i > 0 and j > 0: Z[i][j] = Z[i-1][j-1] + dp[i-1][j-1] dp[i][j] = X[i][j] + Y[i][j] + Z[i][j] dp[i][j]%=MOD print(dp[-2][-2]%mod)
感想
今のレートならNosub戦法とるより前からどんどん出したほうがレート上がるので出続けたいね。
めっちゃ久々にHighest更新できたのはすこしうれしかったな。。
ここまで読んでいただきありがとうございます
しい
ABC 181 ざくざくまとめ
しいだよー
久々にABCに参加したのでそのまとめ 結果はABCD(3)E5完で水色パフォの1338 レート上がると嬉しい
https://atcoder.jp/contests/abc181
A - Heavy Rotation
偶奇判別
n = int(input())
if (n%2==0):
print('White')
else:
print('Black')
B - Trapezoid Sum
等差数列の和の公式をループ回す 最初書いた数字の個数と読み間違えたけど。。
n = int(input()) ans = 0 for i in range(n): a,b= map(int,input().split()) ans += (b-a+1)*(a+b)//2 print(ans)
等差数列は最近やったから覚えてたけど数列の公式系をまとめて確認できるようにしといたほうがいいかも
C - Collinearity
3つの点が数直線状にある場合を判断する問題。 制約が N<=100で三重ループしても間に合うものだったので全探査。 差分をとって傾きが一致するかで判断した。
傾きでやったためゼロの場合を分ける必要があったが、外積だったらその必要がなかったなと今になって思うかも。慣れていきたいね
<変更前(傾きで確認)>
n = int(input()) l = [] for i in range(n): x,y = map(int,input().split()) l.append([x,y]) f = 0 for e,i in enumerate(l): for E,j in enumerate(l[e+1:]): e2 = E+e+1 # print(e,E,e2,i,j) for T in l[e+E+1+1:]: a = T[0] - i[0] b = T[0] - j[0] c = T[1] - i[1] d = T[1] - j[1] if a==0 and b==0: f=1 break elif a==0 or b==0: break if c/a == d/b: f = 1 if f: print('Yes') else: print('No')
<変更後(外積で確認)>
n = int(input()) l = [] for i in range(n): x,y = map(int,input().split()) l.append([x,y]) f = 0 for e,i in enumerate(l): for E,j in enumerate(l[e+1:]): e2 = E+e+1 # print(e,E,e2,i,j) for T in l[e+E+1+1:]: a = T[0] - i[0] b = T[0] - j[0] c = T[1] - i[1] d = T[1] - j[1] if c*b==a*d: f = 1 if f: print('Yes') else: print('No')
D - Hachi
https://atcoder.jp/contests/abc181/tasks/abc181_d
与えられた1−9で成り立つ文字列が並び替えて8の倍数になるかという問題。 8の倍数になるためには下三桁が8の倍数であればいいので三桁以下の8の倍数をすべて確かめてやればいい。とおもって愚直にすると一つのケースのみWA。コーナーかなと思いつつも0の場合はないため範囲を変えて提出し直すとどうやら桁数が2のときに挙動がおかしいことがわかる。82といった場合に反応していたため1桁、2桁、3桁以上の三通りで場合分けを行ってAC。
各8の倍数で文字数をカウントとして考えたがあんまりしっくりこないので改善の余地あり。解説見たらCounterから引いてて何これ!?!?
for i in range(112, 1000, 8): if not Counter(str(i)) - cnt: print("Yes") exit()
<十分後>
なるほど、辞書型が帰ってくるからその差分をとって何も残ってなかったら8の倍数が作れるってことか、かしこいな。。allで回答してる型もあったからそっちもまとめとこう。
<私の回答(変更前)> Counterを使わず配列で各文字数を確認し、実装した。8の倍数であるかの識別もrangeを8飛ばしで取るようにしたほうがきれいだね。調整しないと
ans = 0 S = input() dp = [0]*10 for i in S: dp[int(i)]+=1 if len(S)>=3: for i in range(100,1000): tdp = [0]*10 if i%8==0 : #ここが少し余分 s = str(i) for i in s: tdp[int(i)]+=1 f = 1 for i in s: if dp[int(i)] < tdp[int(i)]:f=0 if f: ans = 1 else: if int(S)%8==0: ans = 1 for i in range(10,100): tdp = [0]*10 if i%8==0 : s = str(i) for i in s: tdp[int(i)]+=1 f = 1 for i in s: if dp[int(i)] < tdp[int(i)]:f=0 if f: ans = 1 if S == '8': ans =1 if ans: print('Yes') else: print('No')
<変更後(辞書型)>
from collections import Counter ans = 0 S = input() cnt = Counter(S) if len(S)>=3: for i in range(112,1000,8): c = Counter(str(i)) if not c - cnt:ans = 1 else: if int(S)%8==0: ans = 1 for i in range(16,100,8): c = Counter(str(i)) if not c - cnt:ans = 1 if S == '8': ans =1 if ans: print('Yes') else: print('No')
E - Transformable Teacher
https://atcoder.jp/contests/abc181/tasks/abc181_e
問題文概要:N人の児童がおり、それぞれにHiの身長が割り当てられる。あなたは先生で体の大きさをWiのどれかにすることができます。二人一組のペアを作ったときの距離の差の総和を最小化したときの値。
身長順にソートしたら番号順にペアを作るのが最適であることも未証明で実装したがあっていたみたい。 絶対値を分解したらわかったことだが、足す側と引く側に分けて先生の挿入位置で場合分けした。 添字バグが怖すぎてめっちゃ時間かかったけど最終的に一発ACできたのでヨシ!
from bisect import bisect_left n,m = map(int,input().split()) h = list(map(int,input().split())) w = list(map(int,input().split())) h.sort() ho = [0] he = [0] w.sort() for e,i in enumerate(h): if e%2==0:ho.append(ho[-1]+i) else:he.append(he[-1]+i) inf = float('INF') ans = inf for i in w: t = bisect_left(h,i) # print(t,i) EO = (t%2==0) if not EO: tho = (t+1)//2 the = tho-1 tmp1 = abs(he[the]-ho[tho-1]) tmp2 = abs(i-h[t-1]) tmp3 = abs(he[-1]-he[the]) tmp4 = abs(ho[-1]- ho[tho]) tmp5 = abs(tmp3 - tmp4) # print(tmp1,tmp2,tmp3,tmp4,tmp5) tmp= tmp1+tmp2+tmp5 elif EO: tho = (t)//2 the = tho tmp1 = abs(he[the]-ho[tho]) tmp2 = abs(i-h[t]) tmp3 = abs(he[-1]-he[the]) tmp4 = abs(ho[-1]- ho[tho+1]) tmp5 = abs(tmp3 - tmp4) # print(tmp1,tmp2,tmp3,tmp4,tmp5) tmp= tmp1+tmp2+tmp5 ans = min(tmp,ans) print(ans)
感想
久々にしては頭回ってたし、累積和、二分探索の問題に慣れてきてるんだと思う。今回は問題のあたりが大きかった気もするけど、もう少しコードを最適化できるところあると思うからまたまとめたい。
ここまで読んでいただきありがとうございます
しい
AGC 036 A - Triangle 緑コーダーですが何か?その6
Python にも公式からマスコットでたらもっと楽しいな。
緑のしいだよ、緑コーダーですが何か?第6回目だよ
今日の一問はこれ!
A. Triangle
https://atcoder.jp/contests/agc036/tasks/agc036_a
AGCじゃん。。めっちゃ苦手意識あるけどがんばる。。まあ緑コーダーの私にかかれば瞬殺なんですけどね(笑)
問題の概要は
面積Sが与えられるのでその面積となる三角形の座標を表示してください。
解法
座標は三つあるのでとりあえず一つを原点(0、0)に固定する。
そうしたとき三角形の面積を求める方法は二つある
- 底辺 x 高さ / 2
- 外積(| x2 * y3 - x3 * y2| / 2)
1の方法は簡単だが求めるがむずかしいので却下 残りの二つの座標をX軸、Y軸に固定するとすぐに求めることができるが 任意の値に対応することができない。 値が大きすぎるためである。
2の方法でいくのだがここで大事なのが
二つ目の座標を(1, 109)**で固定することである。
続きは考察ノート載せとくね📔
(汚くてごめんなさい🙏)
実装
s = int(input()) m = 10**9 x = (m-s%m)%m y = (s+x)//m print(0,0,m,1,x,y)
あとがき
計数ソート,基数ソートってなんや(Python)
おはようございます。しいです
バケット法に調べてたら知らない単語”計数ソート”ってのが出てきたので調べたメモをまとめていきます。
上のけんちょんさんの第8章にのってるやつね
計数ソート(Counting sort)
これは大学の授業で書いてたやつだった別の名をCounting sortともいうらしい。
最初に最大値Nの非負の配列をソートする場合を考える。そのときに書く数値の数を数えて並べなおしソートするというものである。
N = int(input())#配列の大きさを取得 A = list(map(int,input().split())) dp = [0]*(N+1)#辞書の用意 ans = []#答えの配列 for i in A:#出現した要素をカウント dp[i]+=1 for e,i in enumerate(dp):#並び替え実行部分 for j in range(i):#出現回数分追加してあげる ans.append(e) print(ans)
- コメントのとおりだが最初に辞書を用意
- Aの出現回数をカウント
- 出現回数分追加する
実質高速なのだが扱う整数の最大値に速度が依存するため注意
基数ソート
基数を決めて各桁ごとに比較していくと最終的にソートされるというもの
https://ko-gaku-jiji.hatenablog.jp/entry/2019/11/10/033214
詳しくはここ見たらイメージしやすいと思うよ
https://algoful.com/Archive/Algorithm/RadixSort
実装はここのCのやつを参考にします
from collections import defaultdict from copy import copy D1 = defaultdict(list) N = int(input()) A = list(map(int,input().split())) M = len(str(max(A))) #最大桁数の取得 ans = [] print(M) for i in range(M+1): if i == 0: for j in A: D1[j%10].append(j) else: for I in range(10): for j in tmpD[I]: D1[(j%10**(i+1))//(10**(i))].append(j) if i == M-1:ans.append(j) print(i,D1) tmpD = copy(D1) D1 = defaultdict(list) ans = D1[0] print(ans)
defaultdict つかって作成
一番の肝は最初は1のけた使ってやるためうまいことソートされることじゃないかな
任意の桁取り出すのが少し物騒な実装になってるのが反省
from collections import defaultdict from copy import copy D1 = defaultdict(list) N = int(input()) A = list(map(int,input().split())) M = len(str(max(A))) #最大桁数の取得 ans = [] print(M) for i in range(M+1): if i == 0: for j in A: D1[j%10].append(j) else: for I in range(10): for j in tmpD[I]: D1[(j//10**(i+1))%10].append(j) if i == M-1:ans.append(j) print(i,D1) tmpD = copy(D1) D1 = defaultdict(list) ans = D1[0] print(ans)
こっちのほうがわかりやすいね。
10**(取り出したい桁数−1)でわって10で割ったあまりをもとめる。
それじゃお昼ご飯食べてきます。
D. String Equivalence 緑コーダーですが何か?その5
緑のしいだよ。今年のトレンドは明るめのグリーンだから流行の最先端だよ。 緑コーダーですが何か?第5回目!
深夜で眠いけど一問はとくよ 今宵の一問はこれ D. String Equivalence
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d
問題文の意味が難しくてずっと先延ばしてた問題なんだけど、頑張って理解していきましょう。
解法
パッとみたところ制約のNが最大でも10なのでやりたいことし放題だね。 DFSをつかって文字列を生成していったらできそうだね。
ところで、今回大事なのが任意の同じ形に対して最小のものを集めた辞書を作るということ。 つまり
‘ab’ ‘ac’
は同じものだから’ac’の方を出力したらまちがいになる。
ということで
a = int(input()) S = 'abcdefghij' def dfs(s,c): if c == a: ans.append(s) return for i in S[:c+1]:dfs(s+i,c+1)
こういうループは書いてはいけないのだ。
注意すべきなのは追加する文字が元の文字列に入っているものなのかどうかを判断して追加してあげないといけないね。
以下がACコード
実装
a = int(input()) S = 'abcdefghij' def dfs(s,c): if c == a: ans.append(s) return for i in S[:c+1]: if i in s:dfs(s+i,c+1) else: dfs(s+i,c+1) return ans = [] dfs("",0) for i in ans: print(i)
あとがき
結構スッキリ実装できて満足 DFSを使うのも慣れてきてうれしい😆