競プロチートシート(python3)

atcorderとかpaizaとか就活のコーディングテストとか。
おいおい追加していく予定。

入力

• 単数入力

#入力が文字列の時
n = input()
#入力が数値の時
n = int(input())

• 複数入力(文字列の時はintをstrにしてね)

#それぞれの変数に入力
n , m , l = map(int , input().split())
#listにしたい時
list_n = list(map(int , inpuut().split()))

• 複数行入力

今まで

#N回入力
N = int(input())
#リストをあらかじめ作成
list = []
for _ in rnage(N):
    list.append(input())

どうやらこれで良いらしい。コンパクトにかけて便利

N = int(input())
list = [input() for _ in range(N)]

配列

python使ってるから基本はリスト使う。リスト便利

• 一次元リスト

list = [i for i in range(N)]

• 二次元リスト

list = [[i for i in range(N)] for _ in range(M)]

# list = [[0] * N] * M　みたいな書き方は参照先が重複しバグの原因になるからだめ。
# 三次元以上を扱うときはfor文を使って書いた方がどう考えてもわかりやすい

組み合わせ（combination）

組み合わせの計算をしながらmodを考慮したい時

def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a = cmb(n,r,mod)

引用：【Python】組み合わせ(nCr) 計算の高速化

約数のリスト

$O({\sqrt{n}})$で求められる。
C問、D問あたりで多いイメージ。
約数関係はこれかユークリッドの互除法使うイメージ

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

引用：約数を高速で列挙するコード(Python)

累乗

組み込み関数を用いる。10**9+7のあまりも第三引数に指定することで高速に処理ができる。

print(pow(10 ** 9, 10 ** 5, 10 ** 9 + 7))
# 出力：183133701