- 切り上げ
math.ceil- 自分で書く
(b + a - 1) // a
b/aの切り上げ
- 切り捨て
math.floorb//a- 自分で書く
(b - b % a) // a
b/aの切り捨て
- 四捨五入
def round(x, d=0): x *= 10**d x = (x * 2 + 1) // 2 x /= 10**d return x
- プログラム上では実数は近似的に扱われているので、なるべく整数で扱っちゃうのが良い
- 許容される誤差の範囲内で正しく動くプログラムを作る方法について
- 幾何の方も要参照
- Under construction
問題
- Panasonic2020 C - Sqrt Inequality (300点)
- なるべく整数でいけるときはそうするのが楽と言うのがよくわかるいい問題
- 幾何の問題も要参照
問題
正整数
def get_divisor(n: int) -> list:
divisor = []
for i in range(1, n + 1):
if i * i > n:
break
if n % i == 0:
divisor.append(i)
if n // i != i:
divisor.append(n // i)
# divisor.sort() # if you want sorted divisors
return divisorキーワード : GCD(最大公約数 - Greatest Common Divisor), LCM(最小公倍数 - Least Common Multiple), ユークリッドの互除法
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b) }def GCD(a:int , b: int) -> int:
return a if b == 0 else GCD(b, a % b)
def LCM(a: int, b: int) -> int:
return a * b // GCD(a, b) - Python3.5以降には
mathにgcdは実装してある。https://docs.python.org/ja/3/library/math.html#math.gcd- ただし、Python3.4.3では最大公約数を求めるgcdは”math"ではなくて、"fractions"の中にある:
from fractions import gcd
- ただし、Python3.4.3では最大公約数を求めるgcdは”math"ではなくて、"fractions"の中にある:
問題
- ABC131 C - Anti-Divisor (300点)
- ABC125 C - GCD on Blackboard (300点)
- 複数の数に対するGCD
- ABC150 D - Semi Common Multiple (400点)
- JSUTC202004 D - Calculating GCD (400点)
競プロではしばしば「〜〜の値をmod
Fermatの小定理
$p$ を素数、$a$ を$p$ の倍数でない整数とする時、$$a^{p-1} \equiv 1 ~ (\text{mod} ~p)$$
Fermatの小定理より、
なので、
def modinv(x: int, mod: int) -> int:
return pow(x, mod - 2, mod)時間計算量は繰返し二乗法で冪乗を計算すれば、
問題
正整数
from collections import defaultdict
def factorize(n: int) -> dict:
f = defaultdict(int)
while n % 2 == 0:
f[2] += 1
n //= 2
p = 3
while p * p <= n:
while n % p == 0:
f[p] += 1
n //= p
p += 2
if n != 1:
f[n] += 1
return f問題
ある正整数
def is_prime(n: int) -> bool:
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
for i in range(3, n, 2):
if i * i > n:
break
if n % i == 0:
return False
return True問題
- ABC149 C - Next Prime (300点)
-
ARC044 A - 素数判定
$\mathbb{N} = \{1\} ~\cup~ \{\text{Prime number}\} ~\cup~ \{\text{Composite number}\}$
- 2から
$n$ までの整数の配列を用意し全てTrueにする。 - 小さい方から順に数字を見て
Trueである数字は素数とみなす。その数字の倍数に対応する要素はFalseにする。 - 2.を繰り返して行く。
オーダーは、
def eratosthenes(n: int) -> list:
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n // 2 + 1):
if is_prime[i]:
for j in range(2, n // i + 1):
is_prime[i * j] = False
return is_prime問題
def perm(n: int, k: int) -> int:
if n < k or n < 0 or k < 0:
return 0
ans = 1
for i in range(n - k + 1, n + 1):
ans *= i
return ans自分で再帰とかで書いても良いけど、permutationとかの生成にはitertoolsが便利。
- https://docs.python.org/ja/3/library/itertools.html
- ToDo 早いのかどうか確認
from itertools import permutations
for p in permutations(range(3)):
print(p)
# (0, 1, 2)
# (0, 2, 1)
# (1, 0, 2)
# (1, 2, 0)
# (2, 0, 1)
# (2, 1, 0)いわゆる重複組み合わせ
- itertools.combinations_with_replacement
- 具体例
from itertools import combinations_with_replacement n = 3 r = 2 for l in combinations_with_replacement(range(1, n + 1), r): print(l) # (1, 1) # (1, 2) # (1, 3) # (2, 2) # (2, 3) # (3, 3)
- 具体例
- 自分でdfsして構成する
問題
def comb(n: int, k: int) -> int:
if n < k or n < 0 or k < 0:
return 0
k = min(k, n - k)
ans = 1
for i in range(1, k + 1):
ans *= n - i + 1
ans //= i
return ans複数回のcombinationの計算やそのmodを取る処理を効率よく行うには工夫が必要。
という関係式を利用して、combinationのテーブルを作る方法。
パスカルの三角形的な表を上の漸化式で作るという話。
上記の式より、階乗とその逆元の事前計算をしておくことで高速にcombinationができるようになる。
以下のFermatの小定理を使うことで、「素数
Fermatの小定理
$p$ を素数、$a$ を$p$ の倍数でない整数とする時、$$a^{p-1} \equiv 1 ~ (\text{mod} ~p)$$ [
$\Rightarrow$ $p$ を素数、$a$ を任意の整数とする時、$a^p \equiv a ~ (\text{mod} ~p) $ ]
MOD = 10**9 + 7
MAX = 2000 + 5
fact = [1] * MAX
finv = [1] * MAX
for i in range(2, MAX):
fact[i] = fact[i - 1] * i % MOD
finv[i] = pow(fact[i], MOD-2, MOD)
def comb(n: int, k: int) -> int:
if n < k or n < 0 or k < 0:
return 0
return (fact[n] * finv[k] % MOD) * finv[n-k] % MODこの方法だと
このままだとpowが遅い。
-
$\text{MOD}=10^9+7$ に対して、$(a!)^{\text{MOD}-2}$ を計算しないといけない。 - ダブリング使った実装だとしても
$O(\log \text{MOD})$ かかる（多分）。
実はこの
（最初の式は
const int MAX = 510000;
const int MOD = 1000000007;
long long int fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long int COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}MOD = 10**9 + 7
MAX = 7 * 10**5
fact = [1] * (MAX + 1) # i!
finv = [1] * (MAX + 1) # (i!)^{-1}
iinv = [1] * (MAX + 1) # i^{-1}
for i in range(2, MAX + 1):
fact[i] = fact[i - 1] * i % MOD
iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
finv[i] = finv[i - 1] * iinv[i] % MOD
def comb(n: int, k: int) -> int:
if n < k or n < 0 or k < 0:
return 0
return (fact[n] * finv[k] % MOD) * finv[n - k] % MODこの方法だと
combinationを1回求めるだけなら以下でもOK。
上記のcombinationの表式を前から愚直に計算していくと同時に、
def comb(n: int, k: int, MOD: int) -> int:
if n < k or n < 0 or k < 0:
return 0
k = min(k, n - k)
if k == 0:
return 1
iinv = [1] * (k + 1)
ans = n
for i in range(2, k + 1):
iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
ans *= (n + 1 - i) * iinv[i] % MOD
ans %= MOD
return ans問題
-
ABC011 D - 大ジャンプ
- 立式自体は正統だが、確率を計算できるように
$\frac{_n C_k}{2^n}$ を計算する
- 立式自体は正統だが、確率を計算できるように
- ABC034 C - 経路
- ABC042 D - いろはちゃんとマス目 / Iroha and a Grid (400点)
- ABC110 D - Factorization (400点)
- ABC132 D - Blue and Red Balls (400点)
- ABC145 D - Knight (400点)
- ABC151 E - Max-Min Sums (500点)
- ABC154 F - Many Many Paths (600点)
- ABC156 D - Bouquet (400点)
- ABC156 E - Roaming (500点)
- ABC167 E - Colorful Blocks (500点)
- ABC171 F - Strivore (600点)
- ARC039 B - 高橋幼稚園
問題
撹乱順列とも。 数字の並びを完全にかくらんする（もとと同じ場所になる要素がない）順列のこと。
1から
- 要は
$[1,2,3,\cdots, n]$ を並び替え方は$n!$ 通りあるが、そのうち場所が変わっていない要素がないようなものは何通りあるかという話。 -
$a_n$ はモンモール数と呼ばれている。
問題
「1がどこに移るか」という観点で考えると漸化式を立てやすい。
1の移動先を
-
$x$ の移動先が1であるようなパターン- 以下のような表のイメージ
$i$ $1$ $\cdots$ $x$ $\cdots$ $n$ $p$ $x$ ? $1$ ? ? - ?は
$n-2$ 個あり、$1$ と$x$ 以外の$n-2$ 個の数が配置される - この
$n-2$ 個が撹乱順列となっていれば良い-
$a_{n-2}$ 通り
-
- 以下のような表のイメージ
-
$x$ の移動先が 1 以外 であるようなパターン-
以下のような表のイメージ
$i$ $1$ $2$ $\cdots$ $y$ $\cdots$ * $x$ $\cdots$ $n-1$ $n$ $p$ $z$ ? ? $x$ ? * $1$ ? ? ? $y \neq 1, x$ $z \neq 1, x$
-
ポイント
- アスタリスクのついている部分は今の仮定なので無視
- 下段の
$p$ において、-
$x$ は$i=1$ の位置(左端)にいってはいけない - その他の数
$a (\neq 1, x)$ はそのままで、$i=a$ の場所にはいけない
-
-
以上を踏まえると、上段について
$1$ を$x$ と置き換えると分かりやすく、実質$1$ 以外の$n-1$ 個の数について撹乱順列を作ればよいことがわかる$i$ $x$ 1$2$ $\cdots$ $y$ $\cdots$ ( * $x$ )$\cdots$ $n-1$ $n$ $p$ $z$ ? ? $x$ ? ( * $1$ )? ? ? - 丸カッコ()以外の部分で撹乱順列を作れば良いと言うこと
-
$a_{n-1}$ 通り
-
以上より、
まず補集合を考えることで、
完全順列でない順列について考える。
$|B_i| = (n-1)!$ -
$|B_i \cap B_j| = (n-2)! ~~~(i \neq j)$ -
$i$ と$j$ は動いていないような順列の総数
-
である。
一方「完全順列でない順列の総数」は
以上より、
問題
references
三分探索は、ただ一つ極値を持つ関数の極値を探索するアルゴリズム。
def func(x):
pass
left = 0.0
right = 10**8
while right - left > 1e-8:
c1 = (2 * left + right) / 3
c2 = (left + 2 * right) / 3
if func(c1) < func(c2):
right = c2
else:
left = c1問題
組み込み関数のbinを使うと、簡単に整数を先頭に "0b" が付いた 2 進文字列に変換できる。
bin(3)
# '0b11'
bin(-10)
# '-0b1010'- 整数
xの2進数表示した時の1の数はbin(x).count('1')
整数xの最下位の1bit分だけ取り出す
(x & (-x))- 負の数は「全てのbitを反転して1を足す」という補数で表現されていることを利用した技
- BITの実装などに使える
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 00001 | 00010 | 00011 | 00100 | 00101 | 00110 | 00111 | 01000 | |
| 11111 | 11110 | 11101 | 11100 | 11011 | 11010 | 11001 | 11000 | |
| 00001 | 00010 | 00001 | 00100 | 00001 | 00010 | 00001 | 01000 |
def msb(x):
cnt = 0
while x:
x >>= 1
cnt += 1
return cntx|y = x + y - (x & y)x^y = x + y - 2*(x & y)
https://qiita.com/kuuso1/items/778acaa7011d98a3ff3a
XOR関連の問題はDPなどと合わせて出たり、数学の問題として出ることが多々ある。
XORの性質について知っていると便利なことも多い。
以下
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- 基本的な性質
- 2進数として表した時にbit毎に独立な演算
- 可換 :
$a \land b = b \land a$ - 結合律 :
$a \land (b \land c) = (a \land b) \land c$ - 単位元 : 0
- 逆元 :
$a$ の逆元は$a$ 自身。つまり$a \land a = 0$ $a \land x \land x = a$ - つまりある
$a,b$ に対して$a \land x = b$ なる$x$ は、$x = a \land b$
$a \land b \leq a + b$ - 任意の
$n$ について$2n \land (2n+1) = 1$ -
$2n$ と$2n+1$ は最下位bit以外は全て一致している -> 最下位bit以外についてはXor取ると0 - 最下位のbitは0と1なので、1
-
- 任意の
$n$ について$4n \land (4n+1) \land (4n+2) \land (4n+3) = 0$ -
$4n$ と$4n+1$ と$4n+2$ と$4n+3$ は2進数で考えたとき、下2桁以外は全て$4n$ で一致している -> Xor取ると、下２桁以外は全て0 - 下２桁、つまり
$0 \land 1 \land 2 \land 3$ はよく考えると0
-
-
$x' = x \land a$ 、$y' = y \land a$ の時、x' \land y' = (x \land a) ~ \land ~ (y \land a) = (x \land y) ~ \land ~ (a \land a) = x \land y - 2つの数列
$\{a_i \}$ と$\{b_i \}$ が一致するということは以下のようにいくつかの言い方ができる$\forall i ~, ~ a_i = b_i$ - 初項が一致し、階差数列(
$a_i^\prime = a_{i+1} - a_i ~,~~b_i^\prime = b_{i+1} - b_i$ )が一致する。$a_0 = b_0$ -
$\forall i ~, ~ a_i^\prime = b_i^\prime$ $a_i = (a_{i} - a_{i-1} ) + (a_{i-1} - a_{i-2} ) + \cdots + (a_{1} - a_{0} ) + a_0$
- 初項が一致し、Xor階差数列(
$a_i^{\prime\prime} = a_{i+1} \land a_i ~,~~ b_i^{\prime\prime} = b_{i+1} \land b_i$ )$a_0 = b_0$ -
$\forall i ~, ~ a_i^{\prime\prime} = b_i^{\prime\prime}$ $a_i = (a_{i} \land a_{i-1} ) ~\land~ (a_{i-1} \land a_{i-2} ) ~\land \cdots \land~ (a_{1} \land a_{0} ) ~\land~ a_0$
問題
- ABC117 D - XXOR (400点)
- ABC121 D - XOR World (400点)
- ABC129 E - Sum Equals Xor (500点)
- ABC150 F - Xor Shift (600点)
- ABC171 E - Red Scarf (500点)
2を法とした余りに注目した集合
+(XOR), 0, 1
0, 0, 1
1, 1, 0
x(AND), 0, 1
0, 0, 0
1, 0, 1
例えば32bit整数の空間は、線形空間としては
と一意に表せる。
ある基底
問題
標準ライブラリのcmathで複素数を扱える。
- 極座標形式で複素数を作る
import cmath z = cmath.rect(r, th) # z = r * (math.cos(phi) + math.sin(phi)*1j)