ダイクストラ法を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)

参考サイト

https://mirucacule.hatenablog.com/entry/2020/05/21/124026

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解けなかったから早ときに助けられた感じかな

f:id:whitesiro1107:20201121121018p:plain

A - ReLU

ReLU関数を作ろうって問題 タイトルだけで実装がわかって少しくすっと来たよね

x = int(input())
print(max(0,x))

B - Billiards

二点が与えられるのでX軸に当たってからもう片方の点に移動する場合にX軸上のどの点に当たるかという問題。 幾何がきてかなりびびったよね

考察ノートは２つ考えた。本番は＜Ⅰ＞の方を実装したが＜Ⅱ＞のほうが絶対かんたんっておもう

＜Ⅰ＞

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）

問題概要：チェスのクイーンが右、下、右下飲み進める場合に盤面の左上（１，１）から右下（H,W）まで行く方法は何通りあるか。”＃”は進むことができないマスとする。

EDPCのGrid１を思い浮かべたけどうーんってかんじで結局止まってしまった。こういう問題見ると組み合わせとかするのかなって思うけどとても単純な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

３つの点が数直線状にある場合を判断する問題。 制約が N<＝１００で三重ループしても間に合うものだったので全探査。 差分をとって傾きが一致するかで判断した。

傾きでやったためゼロの場合を分ける必要があったが、外積だったらその必要がなかったなと今になって思うかも。慣れていきたいね

＜変更前（傾きで確認）＞

    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

与えられた１−９で成り立つ文字列が並び替えて８の倍数になるかという問題。 ８の倍数になるためには下三桁が８の倍数であればいいので三桁以下の８の倍数をすべて確かめてやればいい。とおもって愚直にすると一つのケースのみWA。コーナーかなと思いつつも０の場合はないため範囲を変えて提出し直すとどうやら桁数が２のときに挙動がおかしいことがわかる。82といった場合に反応していたため1桁、２桁、３桁以上の三通りで場合分けを行ってAC。

各８の倍数で文字数をカウントとして考えたがあんまりしっくりこないので改善の余地あり。解説見たらCounterから引いてて何これ！？！？

    for i in range(112, 1000, 8):
      if not Counter(str(i)) - cnt:
        print("Yes")
        exit()

<十分後>

なるほど、辞書型が帰ってくるからその差分をとって何も残ってなかったら８の倍数が作れるってことか、かしこいな。。allで回答してる型もあったからそっちもまとめとこう。

<私の回答（変更前）> Counterを使わず配列で各文字数を確認し、実装した。８の倍数であるかの識別もrangeを８飛ばしで取るようにしたほうがきれいだね。調整しないと

    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 　緑コーダーですが何か？その６

Python にも公式からマスコットでたらもっと楽しいな。

緑のしいだよ、緑コーダーですが何か？第6回目だよ

今日の一問はこれ！

A. Triangle

https://atcoder.jp/contests/agc036/tasks/agc036_a

AGCじゃん。。めっちゃ苦手意識あるけどがんばる。。まあ緑コーダーの私にかかれば瞬殺なんですけどね（笑）

問題の概要は

面積Sが与えられるのでその面積となる三角形の座標を表示してください。

解法

座標は三つあるのでとりあえず一つを原点（0、0）に固定する。

そうしたとき三角形の面積を求める方法は二つある

  1. 底辺 x 高さ / 2
  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ぬいぐるみほしいからPython認定うけよっかな。

計数ソート,基数ソートってなんや（Python）

おはようございます。しいです

バケット法に調べてたら知らない単語”計数ソート”ってのが出てきたので調べたメモをまとめていきます。

https://qiita.com/drken/items/44c60118ab3703f7727f#8-%E8%A8%88%E6%95%B0%E3%82%BD%E3%83%BC%E3%83%88-%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%81%AF%E9%87%8D%E8%A6%81%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0

上のけんちょんさんの第８章にのってるやつね

計数ソート(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)
  1. コメントのとおりだが最初に辞書を用意
  2. Aの出現回数をカウント
  3. 出現回数分追加する

実質高速なのだが扱う整数の最大値に速度が依存するため注意

基数ソート

基数を決めて各桁ごとに比較していくと最終的にソートされるというもの

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 つかって作成

一番の肝は最初は１のけた使ってやるためうまいことソートされることじゃないかな

任意の桁取り出すのが少し物騒な実装になってるのが反省

    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**（取り出したい桁数−１）でわって10で割ったあまりをもとめる。

それじゃお昼ご飯食べてきます。

D. String Equivalence　緑コーダーですが何か？その５

緑のしいだよ。今年のトレンドは明るめのグリーンだから流行の最先端だよ。 緑コーダーですが何か？第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を使うのも慣れてきてうれしい😆