目次

1. 関数など
   • 最小公倍数、最大公約数
   • 組み合わせ、階乗
   • mathモジュール
   • sort, max, min
   • スライス
   • 入力
   • 出力
2. 典型の実装
   • 二分探索
   • 累積和

最小公倍数、最大公約数

import fractions
# Python3.5以降はmathモジュールに統合された

# 最大公約数
def gcd(a, b):
    return fractions.gcd(a, b)

# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 何度も使う場合は自前で素因数分解した方が早い

組み合わせ、階乗

import itertools
import math
s = "ABCD"  # 配列、タプル、集合でもよい

# 重複なしのあらゆる並び（順列）
itertools.permutations(s, 2)
# =>  (AB AC AD BA BC BD CA CB CD DA DB DC) (タプル)

# 重複なしのソートされた並び（組み合わせ）
itertools.combinations(s, 2)
# =>  (AB AC AD BC BD CD)

# 階乗 O(N)であることに注意
math.factorial(3)
# =>  1 * 2 * 3 = 6

mathモジュール

import math

# 切り捨て、切り上げ、四捨五入
math.floor(1.9)  # 1
math.ceil(1.1)   # 2
round(1.5)       # 2

# 三角関数 入力がラジアン(弧度)であることに注意
# math.radiansで変換もできる  (逆はmath.degrees())
PI = math.pi
math.sin(PI/4)              # 1.4142.../2 
math.cos(PI/4)              # 1.4142.../2
math.tan(math.radians(45))  # 1

# 平方根 1/2乗でも可能
math.sqrt(2)  # 1.4142...
2**(1/2)      # 1.4142...

# 対数
math.log(9, 3)  # log3(9) = 2

sort, max, min

lst = [(1, 2), (2, 4), (3, 1)]

# lst.sort()は破壊的、sorted(lst)は非破壊的

# sortは通常は一つ目の要素を優先してソートする
sorted(lst)                     # (1 2) (2 4) (3 1)

# keyに無名関数を渡すと、その要素で評価してくれる
# この場合だとx[1]、つまり二つ目の要素でソートされる。
sorted(lst, key=lambda x:x[1])  # (3 1) (1 2) (2 4)

# max()、min()関数にも同じような使い方ができる
max(lst)                     # (3, 1)  一つ目の要素で評価される
max(lst, key=lambda x:x[1])  # (2, 4)  二つ目の要素で評価される

スライス

lst = [1, 2, 3, 4, 5, 6]
# lst[start:end:step]
lst[2:]  # [3, 4, 5, 6]
lst[:4]  # [1, 2, 3, 4]
lst[2:4] # [3, 4]
lst[::2] # [1, 3, 5]
lst[1::2] # [2, 4,]
lst[2:4:2] # [3]

入力

# N
N = int(input())

# A B
A, B = map(int, input().split())

# A_1 ... A_n
A = list(map(int, input().split()))

# A_1 B_1
# A_2 B_2
# ...
# A_n B_n
A = []
B = []
for i in range(n):
    Ai, Bi = map(int, input().split())
    A.append(Ai)
    B.append(Bi)

# N A_1 ... A_n
N, *A = map(int, input().split())

# a_11 a_12 ... a_1w
# a_21 a_22 ... a_2w
# ..................
# a_h1 a_h2 ... a_hw
a = [list(map(int, input().split())) for i in range(h)]
# a[y][x]となることに注意

出力

# 通常のものは省略
# /を使ったときにfloor型になる。整数出力でないとWAになる問題があるので注意。

# A_1 ... A_n
print(*A)  # アスタリスクをつけると空白区切りで出力される

二分探索

# めぐる式二分探索を採用
# lst[index] >= key という条件を満たす最小の index を返す

def lower_case(lst, key):
    ng = -1
    ok = len(lst)
    while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if lst[mid] >= key:
                    ok = mid
            else:
                    ng = mid
  　return ok

lst = [1, 2, 3, 5, 5, 9]
lower_case(lst, 3)  # 2  [1, 2, (2<n<=3), 3, 5] なので3を入れられる最小のindexは2
lower_case(lst, 4)  # 3
lower_case(lst, 5)  # 3
lower_case(lst, 10) # 6

def upper_case(lst, key):
    ng = -1
    ok = len(lst)
    while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if lst[mid] > key:
                    ok = mid
            else:
                    ng = mid
  　return ok

lower_case(lst, 5)  # 3
upper_case(lst, 5)  # 5
[1, 2, 3, (lower_case), 5, 5, (upper_case), 9] この違い

累積和

# 区間の総和を高速に求められる

# [1, 2, 3, 4, 5]っていう配列があるとする
# indexがlからrの区間の総和を求めるとき、配列を切り出してsum()する方法では大きい配列ではO(N(l-r))で遅い
# なので累積和を使ってO(2*N)で求める

# a = i番目までの配列の総和
lst = [1, 2, 3, 4, 5]
a = []
sumlst = 0
for i in range(len(lst)):
    sumlst += lst[i]
    a.append(sumlst)
# a => [1, 3, 6, 10, 15]
# こうした前処理をすることで、lからrまでの総和をa[r] - a[l]で求められる
# もちろん1から始まるindexなら-1をしておく