※この記事は随時更新していきます。
何の記事？
この記事は、螺旋本の問題を解いたものである。
言語は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")
幅優先探索
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
'''
最短経路問題（ダイクストラ）
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)