---
# System prepended metadata

title: Untitled

---

## 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)
```