Pythonで螺旋本！螺旋本でPython！（〜１３章）

#※この記事は随時更新していきます。
#何の記事？
この記事は、螺旋本の問題を解いたものである。
言語はpythonを使用している。また一口メモも書いているので参考にして欲しい。

#chapter2

###Maximum Profit

最小値を保存することで、for文を回す手間を省けるよねという話。

n = int(input())
price = []
for k in range(n):
    price.append(int(input()))

min_price = 1000000001
max_pro = -200000

for i in range(n):
    max_pro = max(max_pro, price[i]-min_price)
    min_price = min(price[i], min_price)

print(max_pro)

Chapter3

###insertion sort
jをwhileで回していく！

arr = list(map(int, input().split()))

def insertion_sort(arr):
    for i in range(1,len(arr)):
        j = i-1
        v = arr[i]
        while j >= 0 and v < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = v
    print(arr)

insertion_sort(arr)

bubble sort

changeでループ終了を判定する。

arr = list(map(int, input().split()))

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(1, len(arr))[::-1]:
            if arr[i] < arr[i-1]:
                arr[i], arr[i-1] = arr[i-1], arr[i]
                change = True
    return arr

print(bubble_sort(arr))

###selective sort
min()関数使ったらもっと楽です。

arr = list(map(int, input().split()))

def selective_sort(arr):
    for i in range(len(arr)-1):
        min = arr[i]
        min_index = i
        for index in range(i+1,len(arr)):
            if arr[index] < min:
                min = arr[index]
                min_index = index
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

print(selective_sort(arr))

#Chapter4(データ構造）
###4.2 stack

from collections import deque

Input = list(input().split())
stack = deque([])

for k in Input:
    if k not in ("+", "-", "*"):
        stack.append(int(k))
    elif k == "+":
        stack.append(stack.pop()+ stack.pop())
    elif k == "-":
        stack.append(-(stack.pop()- stack.pop()))
    elif k == "*":
        stack.append(stack.pop()*stack.pop())

print(stack.pop())

###4.3 Queue

from collections import deque

n, q = map(int, input().split())
Queue = deque([])
for i in range(n):
    name, time = input().split()
    Queue.append([name, int(time)])

t = 0
while len(Queue) != 0:
    process = Queue.popleft()
    process[1] = process[1] - q
    if process[1] <= 0:
        t += q + process[1]
        print(process[0]+" "+str(t))
    else:
        t += q
        Queue.append(process)

'''
#入力
5 100
p1 150
p2 80
p3 200
p4 350
p5 20

＃出力
p2 180
p5 400
p1 450
p3 550
p4 800

'''

###4.6 Areas on the Cross-Section Diagram

ground = input()
idx_stack = []

total_area = 0
for i, s in enumerate(ground):
    if s == "\\":
        idx_stack.append(i)
    elif s == "/" and idx_stack:
        j = idx_stack.pop()
        total_area += i-j

print(total_area)

'''
入力
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\

出力
35
'''

#Chapter5
###5.2 二分探索
二部探索はライブラリがあるのでそれ使うともっと楽チンです。
https://qiita.com/ta7uw/items/d6d8f0ddb215c3677cd3

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def binary_search(array, target):
    head = 0
    tail = len(array) -1
    while head <= tail:
        mid = (head+tail) // 2
        comp = array[mid]
        if comp > target:
            tail = mid - 1
        elif comp < target:
            head = mid + 1
        else:
            return True
    return False

ans = 0
for a in t:
    if binary_search(s,a):
        ans += 1
    else:
        continue

print(ans)

#Chapter6 (再帰・分割統治法）
###全探索

n = int(input())
num = list(map(int, input().split()))
q = int(input())
q_num = list(map(int, input().split()))

'''
solve(i,j)はj番目までの数値でiを構成できるかどうかをTrueかFalseで返す関数
'''
'''
i, jの値を用いて再帰関数のループ終了条件を考える。
'''
def solve(i, j):
    if i == 0:
        return True
    if j < -1:
        return False
    return solve(i-num[j], j-1) or solve(i, j-1)


for k in q_num:
    if solve(k, n-1):
        print("Yes")
    else:
        print("No")

#Chapter7

###マージソート
indexが0の要素を引っ張ってくる必要があるから、listじゃなくてdequeを使って実装しました。
そしたら、dequeのスライスのスマートな実装が分からず、長くなってしまいました。
itertoolsのisliceを使いました。

この方の記事がスマート

from collections import deque
from itertools import islice

array = list(map(int,input().split()))
Q = deque(array)

def merge_sort(a):

    if len(a) == 1:
        return a
    else:
        mid = len(a) // 2
        return merge(merge_sort(deque(islice(a, 0, mid))), merge_sort(deque(islice(a, mid, len(a)))))

def merge(x, y):
    z = deque([])
    while len(x) > 0 and len(y) > 0:
        X = x[0]
        Y = y[0]
        if X < Y:
            z.append(x.popleft())
        elif Y < X:
            z.append(y.popleft())
        elif X == Y:
            z.append(x.popleft())
            z.append(y.popleft())

        if len(x) == 0 or len(y) == 0:
            z = z + x + y
    return z

print(list(merge_sort(Q)))

###クイックソート

L = list(map(int, input().split()))

def quick_sort(arr):

    if len(arr) <= 1:
        return arr

    #critの決め方はそれぞれ（今回は左端の数値を無条件でcritとしたがrandを使う場合もある）
    crit = arr[0]
    #critと同じ数値があった場合は、leftにもrightにも入れずに、カウントしてあとで付け加える・
    same_crit = 0

    left = []
    right = []
    for num in arr:
        if num < crit:
            left.append(num)
        elif num > crit:
            right.append(num)
        else:
            same_crit += 1
            
    left = quick_sort(left)
    right = quick_sort(right)

    return left + [crit] * same_crit + right

print(quick_sort(L))

###計数ソート

array = list(map(int, input().split()))

def counting_sort(arr):

    max_num = max(arr)
    count = [0] * (max_num+1)
    sorted_arr = [0] * len(arr)

    for i in arr:
        count[i] += 1
    #累積和計算
    for k in range(max_num):
        count[k+1] = count[k+1] + count[k]

    for t in reversed(arr):
        i = count[t]
        #i-1にすることを忘れない
        sorted_arr[i-1] = t
        count[t] -= 1

    return sorted_arr

if __name__ == "__main__":
    print(counting_sort(array))

#chapter8
実装する機会がないと思うので省略します。
テキストを読み込んで二分木がどのような構造をしているのかを頭に入れていれば大丈夫だと思います。
必要性が出てきたらコード書きます。
#chapter9
同様の理由で省略。
二分木のノード削除の操作だけ少しめんどくさいので注意！
https://qiita.com/maebaru/items/a47c2ef675a76e8816ab
#Chapter10

###max-heap
heapqライブラリを使いましょう。
こちらの記事がわかりやすかったです。

from heapq import heapify, heappop, heappush

arr = list(map(int, input().split()))
#MAXheapの時は、-1をかける
arr = list(map(lambda x : x * (-1), arr))
heapify(arr)
heap_arr = [ s * (-1) for s in arr]
print(heap_arr)

###Priority_Queue

数列を入力して、max_heap表現をし、最大値を取り出す。

from heapq import heapify, heappop, heappush

print("heapしたい数列を入力してください")
arr = list(map(int, input().split()))
arr = list(map(lambda x : x * (-1), arr))
heapify(arr)
heap_arr = [ s * (-1) for s in arr]
print("max_heap表現")
print(heap_arr)

print("挿入したい数を入力してください")
num = int(input())
arr = [ s * (-1) for s in heap_arr]
num = num * (-1)
heappush(arr, num)
heap_arr = [ s * (-1) for s in arr]
print("挿入後のmax_heap")
print(heap_arr)

print("最大値を取り出したい場合はYESを入力してください")
valid = input()
if valid == "YES":
    print((-1)* heappop(arr))
    heap_arr = [s * (-1) for s in arr]
    print("最大値を取り出された後の数列")
    print(heap_arr)

#Chapter11（動的計画法）

###11.4連鎖行列積

そもそも、実装するべき漸化式立てるのがむずい。
さらに、計算していく順番を考えるのもむずい。
計算していく順番はこちらを参考。
このfor文を回す順番を間違えるとうまくいかない！（考えれば当たり前だけど）

n = int(input())
p = []
for t in range(n):
    a, b = map(int, input().split())
    if t == 0:
        p.append(a)
    p.append(b)

'''
dp[i][j]は、Mi~Mjを計算するための最小の掛け算の回数
'''
dp = [[float('inf')] * (n+1) for j in range(n+1)]
for k in range(n+1):
    dp[k][k] = 0
    dp[0][k] = 0
    dp[k][0] = 0

#lは対角成分からの距離
for l in range(1,n+1):
    for i in range(0,n-l+1):
        j = i + l
        for k in range(0,j-i):
            dp[i][j] = min(dp[i][j], dp[i][i+k] + dp[i+k+1][j] + p[i-1] * p[j] * p[i+k])
print(dp[1][n])


'''
入力
6
30 35
35 15
15 5
5 10
10 20
20 25

出力
15125
'''

#Chapter12

###深さ優先探索
螺旋本の問題より、Atcoderの問題が面白そうだったのでこちらをときました。（もはや記事の趣旨に反していますが...)
https://atcoder.jp/contests/atc001/tasks/dfs_a

'''
https://atcoder.jp/contests/atc001/tasks/dfs_a
'''
import sys

h, w = map(int, input().split())
maze = [list(input()) for k in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j] == "s":
            sx, sy = i, j
        elif maze[i][j] == "g":
            gx, gy = i,j

stack = [[sx, sy]]
visited = [[0] * w for i in range(h)]
visited[sx][sy] = 1

while stack:
    x, y = stack.pop()
    for s in [[1,0],[-1,0],[0,1],[0,-1]]:
        nx, ny = x+s[0], y+s[1]
        if 0 <= nx < h and 0 <= ny < w and visited[nx][ny] == 0 and maze[nx][ny] != "#":
            visited[nx][ny] = 1
            stack.append([nx, ny])
        if visited[gx][gy] == 1:
            print("Yes")
            sys.exit()
print("No")

###幅優先探索
https://atcoder.jp/contests/abc151/tasks/abc151_d

from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for k in range(h)]

def bfs(start, goal):
    queue = deque([start])
    visited = [[0] * w for u in range(h)]

    while  len(queue) > 0:
        now_loc = queue.popleft()
        cx = now_loc[0]
        cy = now_loc[1]
        for d in [[1,0],[-1,0],[0,1],[0,-1]]:
            #nx, nyは次の位置
            #cx, cyは現在の位置
            nx = cx + d[0]
            ny = cy + d[1]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and visited[nx][ny] == 0:
                visited[nx][ny] = visited[cx][cy] + 1
                queue.append([nx, ny])

        if visited[goal[0]][goal[1]] != 0:
            return visited[goal[0]][goal[1]]

    return 0

step = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            continue
        start = [i, j]
        for s in range(h):
            for t in range(w):
                if maze[s][t] == "#":
                    continue
                goal = [s,t]

                step.append(bfs(start, goal))

ans = max(step)
print(ans)

###連結成分

こちらの記事を参考にさせていただきました。
dfsの実装に、stackではなく再帰関数を用いています。

from collections import defaultdict
import sys
sys.setrecursionlimit(25)

n, m = map(int, input().split())

#コネクションをdefaultdictを使って保存
connect = defaultdict(lambda: [])
for _ in range(m):
    s, t = map(int, input().split())
    connect[s].append(t)
    connect[t].append(s)

#各ノードの属するグループを辞書型で記録
group = {x:None for x in range(n)}

def dfs(node:int, gro:int):
    if group[node] is not None:
        return
    group[node] = gro

    for n in connect[node]:
        dfs(n, gro)

gro = 1
for node in connect.keys():
    dfs(node, gro)
    gro += 1

q = int(input())
ans = []
for _ in range(q):
    x, y = map(int, input().split())
    if group[x] == group[y]:
        ans.append("yes")
    else:
        ans.append("no")

for a in ans:
    print(a)

#Chapter13 重み付きグラフ

###最小全域木（プリム法）
こちらの方のコードを参考にさせていただきました。

また下のコードの入力は、螺旋本のように隣接行列を想定していません。
（入力の例は下のコードの最後をご覧ください）

[入力の形]
nodeの数 辺の数
node1 node2 cost
node3 node4 cost
.
.
.
の形です。

from heapq import heappush, heappop


def prim_heap(connection):
    used = [False] * len(connection) #i番目のノードがすでに使われたかどうか
    node_heap = []
    for x in connection[0]:
        heappush(node_heap, x)
    used[0] = True
    ans = 0

    while len(node_heap) != 0:
        min_node = heappop(node_heap)
        if used[min_node[1]]:
            continue
        min_node_num = min_node[1]
        used[min_node_num] = True
        for y in connection[min_node_num]:
            if not used[y[1]]:
                heappush(node_heap, y)
        ans += min_node[0]

    return ans

n, v = map(int, input().split())
#[[[cost,node],[]...],[[],[].....],[]
s_connection = [[] for i in range(n)]
for i in range(v):
    s, t, u = map(int, input().split())
    s_connection[s].append([u, t])
    s_connection[t].append([u, s])


if __name__ == "__main__":
    print(prim_heap(s_connection))


'''

#入力
7 9
0 1 1
1 2 2
1 3 3
2 5 10
1 4 7
3 4 1
3 6 5
4 6 8
5 4 5

'''

###最短経路問題（ダイクストラ）
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=jp

from heapq import heappush, heappop, heappushpop, heapreplace, heapify

#隣接リスト作成
v = int(input())
edge_list = [[] for _ in range(v)]
for i in range(v):
    l = list(map(int, input().split()))
    for j in range(1,l[1]+1):
        edge_list[l[0]].append([l[2*j+1],l[2*j]])

def dijkstra(v, edges, start):
    d = [float("inf")] * v
    visited = [False] * v
    d[start] = 0
    visited[start] = 0
    hq = []
    for i in edges[start]:
        d[i[1]] = i[0]
        heappush(hq, i)

    while hq:
        x, y = heappop(hq)
        #もし更新する必要がないならこれ以降の処理を行わない
        if d[y] < x:
            continue
        d[y] = x
        visited[y] = True
        for n in edges[y]:
            if not visited[n[1]]:
                hq.append([x + n[0], n[1]])
        heapify(hq)
    return d

for index, d in enumerate(dijkstra(v, edge_list,0)):
    print(index,d)