## Python チートシート
入力
```jsx
3
1 2 3
4 5 6
7 8 9
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
1 2 3
data = [int(x) for x in stdin.readline().rstrip().split()]
```
配列
```python
l = [1, 2, 3, 4, 5]
print(l[0])
//1
print(l[-1])
//5
print(l[:3])
[1, 2, 3]
print(l[-3:])
[3, 4, 5]
print(l[1:4])
[2,3,4]
リストの要素の追加(最後に追加)
l.append(600)
リストの要素の追加(先頭に追加：0番目のインデックスに「0」を追加)
l.insert(0, 0)
リストの要素の取得(最後の要素の取得、リストからは消える)
l.pop()
リストの要素の取得（０番目の要素の削除、リストからは消える）
l.pop(0)
リストの指定した値に合致した要素を削除
l.remove(3)
リストの要素数の取得
print(len(l))
指定した値に合致するインデックスの取得
l.index(3)
//2
```
dict
```python
d = {'x': 10, 'y': 20, 'z': 30}
辞書型（ディクショナリ型）にキーと値の追加
d['a'] = 40
辞書型（ディクショナリ型）の特定のキーの削除
del d['a']
辞書型（ディクショナリ型）のキーリストの取得
list(d.keys())
特定のキーの値を取得
d['x']
```
deque
```python
S = deque()
一番上(最後尾)に要素追加
S.append(x)
一番上の要素取得
a = S[-1]
一番上の要素を削除
a = S.pop()
先頭要素を取得
a = S[0]
先頭要素を削除
a= S.popleft()
```
heapq(優先度つきqueue)
```python
T = []
追加
heapq.heappush(T,x)
最小値を取得し、削除
a = heapq.heappop(T)
```
set
```python
S = set()
set.add(x)
set.remove(x)
```
制御
```python
if 条件式1:
条件式1が真の場合に実行される処理
elif 条件式2:
条件式1が偽かつ条件式2が真の場合に実行される処理
else:
全ての条件式が偽の場合に実行される処理
1 != 1
1 >= 0
1 <= 0
and
or
items = ['pen', 'note', 'book']
'book' in items
'note' not in items
```
ループ
```python
for i in list:
for i in range(int):
chars = 'word'
for count, char in enumerate(chars):
print(f'{count}番目の文字は{char}')
sports = {'baseball': 9, 'soccer': 11, 'tennis': 2}
for k, v in sports.items():
```
関数
```python
def increment(num1, num2):
return a, b //配列で返す
```
class
```python
class Person:
def __init__(self):
print('Init completed!')
def say_something(self):
print('Hello!!!')
person = Person()
```
## 二分探索priter
```python
# 答えが x 以下かを判定し、Yes であれば true、No であれば false を返す関数
def check(x, N, K, A):
sum = 0
for i in range(N):
sum += x // A[i] # 「x÷A[i]」の小数点以下切り捨て
if sum >= K:
return True
return False
# 二分探索
# Left は探索範囲の左端を、Right は探索範囲の右端を表す
Left = 1
Right = 10 ** 9
while Left < Right:
Mid = (Left + Right) // 2
Answer = check(Mid, N, K, A)
if Answer == False:
Left = Mid + 1 # 答えが Mid+1 以上であることが分かる
if Answer == True:
Right = Mid # 答えが Mid 以下であることが分かる
# 出力（このとき Left=Right になっている）
print(Left)
```
## 二分探索木
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self, arr):
self.root = None
for val in arr:
self.insert(val)
def insert(self, val):
if self.root is None:
self.root = Node(val)
else:
node = self.root
flag = True
while flag:
if node.data > val:
if node.left is None:
node.left = Node(val)
flag = False
# whileを終了させるためにFalseをセットする
else:
node = node.left
else:
if node.right is None:
node.right = Node(val)
flag = False
else:
node = node.right
def find(self, node, val):
if node is not None:
if node.data == val:
return True
else:
flag_left = self.find(node.left, val)
flag_right = self.find(node.right, val)
if flag_left or flag_right:
return True
return False
def bst_min(self, node):
if node.left is None:
return node.data
else:
return self.bst_min(node.left)
#再帰で行きついた先の値を返したいときはreturn のあとに再帰関数を書く。traversalのときと用法が異なるので注意。
def bst_max(self, node):
if node.right is None:
return node.data
else:
return self.bst_max(node.right)
def inoder_traverse(self, node):
if node is not None:
self.inoder_traverse(node.left)
print(node.data)
self.inoder_traverse(node.right)
```
## dungeon
```python
# 動的計画法
dp = [ None ] * (N+1)
dp[1] = 0
dp[2] = A[0]
for i in range(3, N+1):
dp[i] = min(dp[i-1]+A[i-2], dp[i-2]+B[i-3])
# 答えの復元
# 変数 Place は現在位置（ゴールから進んでいく）
# たとえば入力例の場合、Place は 5 → 4 → 2 → 1 と変化していく
Answer = []
Place = N
while True:
Answer.append(Place)
if Place == 1:
break
# どこから部屋 Place に向かうのが最適かを求める
if dp[Place-1] + A[Place-2] == dp[Place]:
Place = Place - 1
else:
Place = Place - 2
Answer.reverse()
```
## subset sum
```python
0 1 2 3 4 5 6 7
0 T F F F F F F F
1 T F T F F F F F
2 T F T F T F F F
3 T F T T T T F T
dp = [ [ None ] * (S + 1) for i in range(N + 1) ]
dp[0][0] = True
for i in range(1, S+1):
dp[0][i] = False
# 動的計画法（i=1）
for i in range(1, N+1):
for j in range(0,S+1):
if j < A[i-1]:
if dp[i-1][j] == True:
dp[i][j] = True
else:
dp[i][j] = False
if j >= A[i-1]:
if dp[i-1][j] == True or dp[i-1][j-A[i-1]] == True:
dp[i][j] = True
else:
dp[i][j] = False
```
## knapsack
```
w = [ None ] * (N + 1)
v = [ None ] * (N + 1)
for i in range(1, N+1):
w[i], v[i] = map(int, input().split())
# 動的計画法
dp = [ [ -10 ** 15 ] * (W + 1) for i in range(N + 1) ]
dp[0][0] = 0
for i in range(1, N+1):
for j in range(0,W+1):
if j < w[i]:
dp[i][j] = dp[i-1][j]
if j >= w[i]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
```
## Longest Common Subsequence
```python
dp = [ [ None ] * (M + 1) for i in range(N + 1) ]
dp[0][0] = 0
for i in range(0, N+1):
for j in range(0,M+1):
if i>=1 and j>=1 and S[i-1]==T[j-1]:
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)
elif i>=1 and j>=1:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
elif i>=1:
dp[i][j] = dp[i-1][j]
elif j>=1:
dp[i][j] = dp[i][j-1]
```
## 配る遷移方式
```
dp = [ -(10 ** 9) ] * (N + 1)
dp[1] = 0
# 動的計画法
for i in range(1, N):
dp[A[i-1]] = max(dp[A[i-1]], dp[i] + 100)
dp[B[i-1]] = max(dp[B[i-1]], dp[i] + 150)
```
## bit DP
```python
# 配列の初期化
dp = [ [ 10 ** 9 ] * (2 ** N) for i in range(M + 1) ]
# 動的計画法
dp[0][0] = 0
for i in range(1, M+1):
for j in range(0, 2 ** N):
# already[k] = 1 のとき、品物 k は既に無料になっている
already = [ None ] * N
for k in range(0, N):
if (j // (2 ** k)) % 2 == 0:
already[k] = 0
else:
already[k] = 1
# クーポン券 i を選んだ場合の整数表現 v を計算する
v = 0
for k in range(0, N):
if already[k] == 1 or A[i-1][k] == 1:
v += (2 ** k)
# 遷移を行う
dp[i][j] = min(dp[i][j], dp[i-1][j])
dp[i][v] = min(dp[i][v], dp[i-1][j] + 1)
```
## deep first search
```python
def dfs(pos, G, searched_flag_list):
searched_flag_list[pos] = True
for nex in G[pos]:
if nex == True:
pass
else:
dfs(nex, G, searched_flag_list)
def solve(n, m, connected_list):
G = [list() for i in range(N)]
for a,b in connected_list:
G[a].append(b)
G[b].append(a)
searched_flag_list = [False] * (N + 1)
dfs(1,G,searched_flag_list)
answer = True
for i in range(1, N+1):
if searched_flag_list[i] == False:
answer = False
```
## breadth first search
```
G = [ list() for i in range(N + 1) ]
for a, b in edges:
G[a].append(b)
G[b].append(a)
# 幅優先探索の初期化（dist[i] = ? ではなく dist[i] = -1 で初期化していることに注意）
dist = [ -1 ] * (N + 1)
dist[1] = 0
Q = deque()
Q.append(1)
# 幅優先探索
while len(Q) >= 1:
pos = Q.popleft() # キュー Q の先頭要素を取り除き、その値を pos に代入する
for nex in G[pos]:
if dist[nex] == -1:
dist[nex] = dist[pos] + 1
Q.append(nex)
```
## ダイクストラ法
```python
# 隣接リストの作成（重み付きグラフなので、各辺について (隣接頂点, 重み) のタプルを記録する）
G = [ list() for i in range(N + 1) ]
for a, b, c in edges:
G[a].append((b, c))
G[b].append((a, c))
# 配列・キューの初期化（キューには (距離, 頂点番号) のタプルを記録する）
INF = 10 ** 10
kakutei = [ False ] * (N + 1)
cur = [ INF ] * (N + 1)
cur[1] = 0
Q = []
heapq.heappush(Q, (cur[1], 1))
# ダイクストラ法
while len(Q) >= 1:
# 次に確定させるべき頂点を求める
# （ここでは、優先度付きキュー Q の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を pos に代入する）
pos = heapq.heappop(Q)[1]
# Q の最小要素が「既に確定した頂点」の場合
if kakutei[pos] == True:
continue
# cur[x] の値を更新する
kakutei[pos] = True
for e in G[pos]:
# 書籍内のコードとは pos = e[0], cost = e[1] で対応している
if cur[e[0]] > cur[pos] + e[1]:
cur[e[0]] = cur[pos] + e[1]
heapq.heappush(Q, (cur[e[0]], e[0]))
```
## DP tree
```python
A = [ 0 ] * 2 + list(map(int, input().split()))
# 隣接リストの作成
G = [ list() for i in range(N + 1) ]
for i in range(2, N + 1):
G[A[i]].append(i) # 上司 → 部下の方向に方向に辺を追加
# 動的計画法（dp[x] は社員 x の部下の数）
dp = [ 0 ] * (N + 1)
for i in range(N, 0, -1):
for j in G[i]:
dp[i] += (dp[j] + 1)
```
## union-find
```python
class unionfind:
def __init__(self, n):
self.n = n
self.par = [ -1 ] * (n+1)
self.size = [1] * (n+1)
def root(self, x):
while self.par[x] != 1:
x = self.par[x]
return x
def unite(self, u, v):
rootu = self.root(u)
rootv = self.root(v)
if rootu != rootv:
if self.size[rootu] < self.size[rootv]:
self.par[rootu] = rootv
self.size[rootv] += self.size[rootu]
else:
self.par[rootv] = rootu
self.size[rooty] += self.size[rootv]
def same(self, u, v):
return self.root(u) == self.root(v)
```
Sign in with Wallet
Connect another wallet