個人用アルゴリズムのメモ
AtCoderに最近参加しているのですがつい先日に適用ルールが改訂され、生成AIを使ったコードについて事前に公開する必要が出てきたので、このページに載せることにします。(AtCoder Libraryというのがあるらしいのですが、私のそれはライブラリとは呼べないのでこちらに不法投棄することにします。)
競プロ知識まとめ(python3)
[多重リストの作り方]
a = [ [] * n ] * n # これだと一つのリストに対する変更が全てのリストに適用されてしまう
a = [[] for _ in range(n)] # これで解決
[文字列処理]
スライス
s = "1234567"
s_1 = s[:2] # "12"
s_2 = s[3:] # "4567"
s_3 = s[:-2] # "12345"
s_4 = s[-2:] # "67"
s_5 = s[0:3:2] # "13"
反転(回文にしたいときとか)
s = "1 2 3 4 5 6 7"
s = s[::-1]
print(s) # "7 6 5 4 3 2 1"
[配列操作]
ある要素の位置出力
li = [a, b, c, d, e, f, g]
dのインデックスを出力する方法x3
method.1
for i in range(len(li)):
if li[i] == "d":
print(i) # 3
method.2
for index, element in enumerate(li):
if element == "d":
print(index) # 3
method.3
print(li.index("d")) # 3
Counterメソッドで数え上げ
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = Counter(a)
print(cnt[n])
順番を逆にする
N = int(input())
A = [int(x) for x in input().split()]
for a in reversed(A):
print(a)
ある位置の要素の削除
n, m = map(int, input().split())
a = [int(x) for x in input().split()]
del a[m - 1]
for i in range(n-1):
print(a[i])
ある位置への要素の挿入
n, m, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.insert(m-1, k)
for e in a:
print(e)
[bit演算]
bit単位における論理積AND(&)、論理和OR(|)、排他的論理和XOR(^)
x = 12 # 0b1100
y = 10 # 0b1010
print(x & y) # 8
print(bin(x & y)) # 0b1000 各桁が共に1のときに1を返す
print(x | y) # 14
print(bin(x | y)) # 0b1110 各桁の少なくとも一方が1のときに1を返す
print(x ^ y) # 6
print(bin(x ^ y)) # 0b0110 各桁が同じときに1を返す。同じ数同士のxorは0。任意の数xと0のxorはx。
活用次第では奇数判定に使えたり、
n = int(input())
if n & 1:
print("Odd")
else:
print("Even")
数列の中に奇数回出現する整数(1種類のみとする)を判別したりも。(x ^ y ^ y == x)
N = int(input())
A = list(map(int, input().split())) # 1, 3, 3, 5, 1
ans = 0
for i in range(N):
ans ^= A[i]
print(ans) # 5
2回xorすると元に戻る。
x = 3
y = 7
print(x, y) # 3 7
x = x ^ y
y = x ^ y
x = x ^ y
print(x, y) # 7 3
ビット列の1の数のカウント・ビット列の長さのカウント
i = 100
print(bin(i)) # 0b1100100
print(i.bit_count()) # 3
===
i = -3
bin(i) # -0b11
i.bit_length() # 2 (符号と先頭の0以外の長さ)
bit反転 (xorを使うと便利)
b = list(input())
for i in range(len(b)):
b[i] = str(int(b[i]) ^ 1)
print("".join(b))
k桁目のみのbit反転
N = int(input())
k = int(input())
ans = N ^ (1 << k) # 1を左にkだけビットシフトしてxorをとる
print(ans)
[探索系 ( 全探索, 二分探索 )]
二分探索 ( ライブラリを使わない場合 )
def binary_search(A, n, k):
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if A[mid] == k:
return True
if A[mid] < k:
left = mid + 1
else:
right = mid - 1
return Falsen = int(input())
A = [int(x) for x in input().split()]
q = int(input())
for _ in range(q):
k = int(input())
if binary_search(A, n, k):
print("Yes")
else:
print("No")
二分探索 ( ライブラリ'bisect'を使う場合 )
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
k = int(input())
for _ in range(k):
q = int(input())
i = bisect_left(a, q)
if i < n and a[i] == q:
print("Yes")
else:
print("No")二分探索 (答えを二分探索して求める場合の一例)
L, n, k = map(int, input().split())
A = [0]
A += list(map(int, input().split()))
A += [L]
lo = 0
hi = L
for i in range(1, k + 2):
lo = max(lo, A[i] - A[i-1])
lo -= 1
for _ in range(30):
while hi - lo > 1:
mid = (lo + hi) // 2
cnt = 0
last = 0
i = 0
while True:
while i + 1 < k + 2 and A[i+1] - A[last] <= mid:
i += 1
cnt += 1
if i == k + 1:
break
last = i
if cnt <= n:
hi = mid
else:
lo = midprint(hi)
三分探索(問題:https://paiza.jp/works/mondai/binary_search_related/binary_search_related__related_algorithms_2)
def f(x, n, a, b):
res = -1e18
for i in range(n):
res = max(res, a[i] * x + b[i])
return resn = int(input())
a_list = []
b_list = []
for i in range(n):
a, b = map(int, input().split())
a_list.append(a)
b_list.append(b)
lo = -1e9
hi = 1e9
while True:
m1 = lo + (hi - lo) / 3 #ここが重要。1/3の点。
m2 = hi - (hi - lo) / 3 #2/3の点。
f1 = f(m1, n, a_list, b_list)
f2 = f(m2, n, a_list, b_list)
if f1 > f2:
lo = m1
else:
hi = m2
if hi - lo < 1e-6 and abs(f2 - f1) < 1e-6:
breakprint(hi, f2)
bit全探索
n = int(input())
s = list(map(int, input().split()))
for i in range(pow(2, n)):
b = []
sub_set = []
for j in range(n):
if (i >> j) & 1:
sub_set.append(s[j])
b.append((i>>j)&1)
b = "".join(map(str, b))
b = b[::-1]
print(b, "{"+ " ".join(map(str, sub_set)) +"}")[ソート]
挿入ソート O(N^2) # 「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す
n = int(input())
a = list(map(int, input().split()))
for i in range(1, n):
x = a[i]
j = i - 1
while j >= 0 and a[j] > x:
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
print(*a)シェルソート O(N^1.25) # 挿入ソートの前処理として間隔hだけ空いた数列について挿入ソートを実施
def insertion_sort(A, n, h): # A:配列, n:Aの要素数, h:間隔
for i in range(h, n):
# A[i] を、整列済みの A[i-ah], ..., A[i-2h], A[i-h] の適切な位置に挿入する
# 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく
x = A[i]
# A[i] の適切な挿入位置を表す変数 j を用意
j = i-h
# A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を後ろにずらしていく
while j >= 0 and A[j] > x:
A[j+h] = A[j]
j -= h
# A[i] を挿入
A[j+h] = x
print(A)def shell_sort(A, n, H): # H:間隔列
for h in H:
insertion_sort(A, n, h)
n = int(input())
A = [int(x) for x in input().split()]
k = int(input())
H = [int(x) for x in input().split()]
shell_sort(A, n, H)
選択ソート O(N^2)
n = int(input())
a = [int(x) for x in input().split()]
for i in range(0, n-1):
min_index = i
for j in range(i+1, n):
if a[j] < a[min_index]:
min_index = j
a[i], a[min_index] = a[i], a[min_index]
print(*a)バブルソート O(N^2)
n = int(input())
a = [int(x) for x in input().split()]
for i in range(0, n-1):
for j in range(n-1, i, -1):
if a[j-1] > a[j]:
a[j-1], a[j] = a[j], a[j-1]
print(*a)マージソート 平均O(NlogN) # 列を繰り返し二分割し、最終的にバラバラになった列を部分ごとにソートしてくっつけてを繰り返す
def merge(l_array, r_array):
merged = []
l_i = 0
r_i = 0
while l_i < len(l_array) and r_i < len(r_array):
if l_array[l_i] <= r_array[r_i]:
merged.append(l_array[l_i])
l_i += 1
# count += 1
else:
merged.append(r_array[r_i])
r_i += 1
# count += 1
if l_i < len(l_array):
merged.extend(l_array[l_i:])
if r_i < len(r_array):
merged.extend(r_array[r_i:])
return mergeddef merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
l_array = array[:mid]
r_array = array[mid:]
l_array = merge_sort(l_array)
r_array = merge_sort(r_array)
return merge(l_array, r_array)a = [int(_) for _ in input().split()]
print(merge_sort(a))
クイックソート 平均O(NlogN) #"基準値"を選び、それ以上か未満かに分けて整列させることを繰り返す
def quick_sort(lst):
if len(lst) <= 1:
return lst
last_index = len(lst) - 1
pivot = lst[last_index]
left = []
center = []
right = []
for val in lst:
if val < pivot:
left.append(val)
elif val > pivot:
right.append(val)
else:
center.append(val)
left = quick_sort(left)
right = quick_sort(right)
return left + center + rightn = int(input())
a = [int(x) for x in input().split()]
print(*quick_sort(a))
[素数やmod関連]
素因数分解
def factorize(n):
prime = {}
for i in range(2, int(pow(n, 0.5))+1 ):
exp = 0
while n % i == 0:
exp += 1
n //= i
prime[i] = exp
if n != 1:
prime[n] = 1
return primen = int(input())
prime = factorize(n)
for factor, exp in prime.items():
for _ in range(exp):
print(factor)
最大公約数(gcm) # mathライブラリに既に搭載済み
import math
N = int(input())
ans = 0
for _ in range(N):
A = int(input())
ans = math.gcd(ans, A)
print(ans)
最小公倍数(lcm) # mathライブラリに既に搭載済み(3.9以降)
from math import lcm
N = int(input())
ans = int(input())
for _ in range(1, N):
A = int(input())
ans = math.lcm(ans, A)
print(ans)
ユークリッドの互除法
def euclid(a, b):
if b == 0:
return a
return euclid(b, a%b)
ax + by = gcd(a, b) を満たすx, y, gcd(a, b)を返すプログラム
途中の"y -= (a // b) * x"という部分では 'q*y1' を計算している。(xに代入されるのはy1)
つまり、'y = x1 - q*y1' となる。(yに代入されるのはx1)
これを再帰的に行うことでax + by = gcd(a, b)のx, yが求まる。
ちなみに、右辺がgcd(a, b)ならば(x, y)の組は一意に定まることが知られている(拡張ユークリッドの互除法で検索)。
def extgcd(a, b):
if b != 0:
y, x, c = extgcd(b, a%b)
y -= (a // b) * x
return x, y, c # 最終的に返される c が gcd(a,b) となる
return 1, 0, a
x, y, c = extgcd(e, s)
d = (x+s) % s # xのままだと負の値になることがあるので、割る数(mod s)の値を足しておくと安心
print(d)
繰り返し2乗法
def modpow(a, b, m): # 'a^b (mod m)'を求める関数, bit演算を行っている。
ans = 1
while 0 < b:
if b & 1 == 1: # '&'は論理積。両端が1であれば1を、そうでなければ0を返す。
ans = (ans * a) % m
a = (a * a) % m
b >>= 1 # bを1ビット右シフトする。左シフトの場合は b << 1。
return ans
繰り返し2乗法 # pow()関数を使う場合
ans = pow(a, b, MOD) # a^b (mod MOD) を計算
[累積和]
1次元累積和
n, k = map(int, input().split())
sum = [0]
for i in range(n):
sum.append(sum[i] + int(input()))
for _ in range(k):
print(sum[int(input())])
2次元累積和(問題:https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__2dsection_sum_boss2)
与えられた配列の累積和を取って直接上書きする場合
n, m, q =map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(n)]
for i in range(n):
for j in range(m):
if i > 0:
A[i][j] += A[i - 1][j]
if j > 0:
A[i][j] += A[i][j - 1]
if i > 0 and j > 0:
A[i][j] -= A[i - 1][j - 1]for _ in range(q):
a, b, c, d = map(int, input().split())
ans = A[c][d]
if a > 0:
ans -= A[a - 1][d]
if b > 0:
ans -= A[c][b - 1]
if a > 0 and b > 0:
ans += A[a - 1][b - 1]
print(ans)
新規に2次元配列を用意してそっちに累積和を書き込む場合
N, M, Q = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(N)]
s = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
for j in range(M):
s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + A[i][j]
for i in range(Q):
a, b, c, d = map(int, input().split())
print(s[c + 1][d + 1] - s[a][d + 1] - s[c + 1][b] + s[a][b])
n, q = map(int, input().split())
a = [0 for _ in range(n + 1)]
for _ in range(q):
l, r = map(int, input().split())
a[l - 1] += 1
a[r] -= 1
for i in range(n):
a[i + 1] += a[i]
print(max(a))
n, m, k = map(int, input().split())
D = [[0 for j in range(m + 1)] for i in range(n + 1)]
for _ in range(k):
b, a, d, c = map(int, input().split())
a -= 1
b -= 1
D[a][b] += 1
D[a][d] -= 1
D[c][b] -= 1
D[c][d] += 1
for i in range(n + 1):
for j in range(m + 1):
if i > 0:
D[i][j] += D[i - 1][j]
if j > 0:
D[i][j] += D[i][j - 1]
if i > 0 and j > 0:
D[i][j] -= D[i - 1][j - 1]
ans = 0
for row in D:
ans = max(ans, max(row))
print(ans)
-尺取り法(問題:https://paiza.jp/works/mondai/prefix_sum_problems/prefix_sum_problems__syakutori_count_boss)
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
right = 0
cnt = 0
s = 0
for left in range(n):
while right < n:
if s + a[right] <= k:
s += a[right]
right += 1
else:
break
cnt += right - left
if right == left:
right += 1
else:
s -= a[left]print(cnt)
[平方分割]
N, K = 10000, int(input())
A = [int(input()) for _ in range(N)]
sqrt = int(pow(N, 0.5))
if sqrt ** 2 < N:
sqrt += 1
range_max = [-1] * sqrt
for i in range(sqrt):
start, end = sqrt * i, sqrt * (i + 1)
range_max[i] = max(A[start:end])
for _ in range(K):
left, right = map(lambda x: int(x) - 1, input().split())
ans = A[left]
now = left
while now <= right:
if now % sqrt == 0 and now + sqrt - 1 <= right:
ans = max(ans, range_max[now // sqrt])
now += sqrt
else:
ans = max(ans, A[now])
now += 1
print(ans)[DP(動的計画法)]
最長部分増加列(LIS)、二分探索を使った解法 O(NlogN)
from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]
dp = []
for tree in a:
idx = bisect_left(dp, tree)
if idx == len(dp):
dp.append(tree)
else:
dp[idx] = treeprint(len(dp))
最長減少部分列(LDS) O(NlogN)
from bisect import bisect_left
n = int(input())
a = [int(input()) * -1 for _ in range(n)] # 要素にマイナスを書けてLISの問題にする
tails = []
for tree in a:
idx = bisect_left(tails, tree)
if idx == len(tails):
tails.append(tree)
else:
tails[idx] = tree
print(len(tails))
アイテムを高々一回しか使えないとき(問題:https://paiza.jp/works/mondai/dp_primer/dp_primer_partial_sums_step0)
n, target = map(int, input().split())
a = [int(input()) for _ in range(n)]
dp = [False] * (target + 1)
dp[0] = True
for omori in a:
for i in range(target, omori - 1, -1): # アイテムを一回しか使えないため降順。
if dp[i - omori]:
dp[i] = True
if dp[target]:
print("yes")
else:
print("no")