約数・倍数に関する演算

gcd と lcm は最大公約数と最小公倍数を求める関数です。

from math import gcd, lcm
a = 10
b = 15
g = gcd(a, b)
l = lcm(a, b)
print(g, l) # 出力: 5 30

次のように任意の個数の数値を引数として与えることができます:

from math import gcd, lcm
g1 = gcd(2, 4, 6)
g2 = gcd()
print(g1, g2) # 2 0
l1 = lcm(2, 4, 6)
l2 = lcm()
print(l1, l2) # 12 1

a = [8,10,12]
print(gcd(*a), lcm(*a)) # 2 120

なお、gcd(0, v) == v となることが約束されています。

組み合わせの数え上げに関する関数

math モジュールには以下のような組み合わせを数える関数も提供されています:

• factorial(n) : n 個のものを一列に並べる並べ方の総数(n の階乗)を返します。
• comb(n, k) : n 個の中から k 個を重複無く順序をつけずに選ぶ方法の数を返します。
• perm(n, k) : n 個の中から k 個を重複無く順序をつけて選ぶ方法の数を返します。

しかし、これらの関数が競技プログラミングで使われることは後述の理由により多くありません。

数学関数・定数

以下の関数も利用可能です。いずれも from math import XX(関数名) のようにインポートして利用します。

利用できる関数の一覧は公式ドキュメントを参照ください。

• log(x, base = math.e) : base を底とする対数を返します。base を省略した場合、自然対数が底として使われます。
• log10(x) : 10 を底とする対数を返します。
• log2(x) : 2 を底とする対数を返します。
• exp(x) : 自然対数の x 乗を返します。
• sin(x), cos(x), tan(x) : サイン、コサイン、タンジェントの値を返します。
• atan2(y,x) : 点 (x,y) が座標平面上で x 軸となす角度をラジアンで返します。
• pi : 円周率 (3.1415...) です。
• e : 自然対数 (2.7182...) です。

大きな数に関する注意

一部の関数では簡単に大きい値が返ってきます。特に 64bit 整数に収まらないような大きさの整数は競技プログラミングでは一部の特別な問題を除いてあまり扱われず、「(求めるべき)大きな数を 998244353 で割った余りを求めよ」のような形で出題されることがほとんどです。
そのため、これらのライブラリは値が小さいときに限っては利用することが可能ですが、基本的には余りを求められるように特化した実装を別途準備することが必要になります。

from math import comb, factorial, lcm
print(comb(100, 20)) # 535983370403809682970
print(factorial(20)) # 2432902008176640000
print(lcm(*[v for v in range(1,50)])) # 3099044504245996706400

練習問題

ABC118C - Monsters Battle Royale (※考察が必要であり、難しいかもしれません)
ABC168C - : (Colon)

random モジュール : ランダムに数値を生成

他のライブラリよりは利用頻度は下がりますが、競技プログラミングではランダムな値を用いることがたびたびあります。確率的に動作するアルゴリズムを実装する場合や、テストケースをランダムに作成する場合などが該当します。

random モジュールはランダムな値を取得するための機能を提供します。
以下によく利用される関数を挙げます:

• random() : 0 以上 1 未満のランダムな浮動小数点数を返します。
• randrange(l, r) : range(l, r) の範囲の整数をランダムに選んで返します。
• choice(l) : 空でないリスト l の要素をランダムに選んで返します。l が空の場合エラーになります。
• choices(l, k=1, weights=None) : 空でないリスト l から k 個を重複あり(復元抽出)でランダムに選んで返します。l が空の場合エラーになります。weights として l と同じ長さの数値からなるリストを与えると、各要素の相対的な選択確率が weights に従うようになります。
• sample(l, k=1) : 長さ k 以上のリスト l から k 個を重複なし(非復元抽出)でランダムに選んで返します。l の長さが k 未満の場合エラーになります。
• seed(a=None) : a をシードとして乱数生成器を初期化します。同じシードで seed() を呼び出したあとはランダムな関数呼び出しの結果が同一になることが保証されます¹。
  • 以下の例では最初に seed(0) を呼び出しているため、どの環境で実行しても同じ結果が得られるはずです。
  • また、random() の呼び出しは1回目,3回目で同じ値になります。これはどちらも seed(0) を呼び出した直後に実行しているためです。

import random
random.seed(0)
print(random.random()) # 0.8444218515250481
print(random.random()) # 0.7579544029403025
random.seed(0)
print(random.random()) # 0.8444218515250481
print(random.random()) # 0.7579544029403025

print(random.randrange(5,10)) # 8
print(random.choice([1,2,3])) # 1
print(random.choices([1,2,3], k=3, weights=[1,1,100])) # [3, 3, 3]
print(random.sample([1,2,3], k=3)) # [2, 3, 1]

l = [1,2,3]
random.shuffle(l)
print(l) # [2, 1, 3]

その他にも、一様分布・指数分布といった分布からサンプリングするための関数も用意されています。
網羅的な機能については公式ドキュメントを参照ください。

また、より強力な乱数生成手法として後述するサードパーティライブラリの numpy における numpy.random モジュールを使う方法もあります。
乱数を大量に用いる場合はこちらの方法のほうが計算速度の面で有利なので覚えておくとよいでしょう。

time

time モジュールは時刻・時間に関する機能を提供します。
ここでは時間計測に使う time() 関数を紹介します。

import time
t0 = time.time() # 処理開始時刻を取得

# 時間のかかる処理を実行
s = 0
for i in range(100000000):
    s += i

t1 = time.time() # 処理終了時刻を取得
print(t1 - t0) # 計算時間が出力される

time() 関数は基準日(1970/1/1 00:00)からの経過時間を浮動小数点数(単位=秒)で返します。
この例では処理の開始・終了時にそれぞれ呼び出した結果の差を取ることで、処理にかかった時間を計算しています²。

発展的な使い方として、「同じ処理を1秒間繰り返す」プログラムは次のように記述することができます:

import time
t0 = time.time()
while True:
    pass # ここに任意の処理を記述する
    if time.time() - t0 > 1:
        break

問題

本節にはEX問題はありません。本文中の練習問題を解いてください。

前のページ | 次のページ