競技プログラミングに関するメモ

計算量の目安

order	よくある制約	よくあるアルゴリズム
$O(N)$	$10^9$	全探索
$O(NlogN), O(N(logN)^2)$	$10^5$	二分探索、ソート
$O(N^2)$	$3000$	全探索
$O(N^2logN)$	$1000$	半分全列挙+二分探索
$O(N^4)$	$50$	全探索
$O(2^{N/2})$	$40$	半分全列挙
$O(2^N)$	$20$	bit全探索, bitDP
$O(N!)$	$8$	順列、組み合わせ

配列の大きさの限界量

だいたい $10^9$ が限界。 $9 \times 10^8$ はエラーにならない(Rust)。大きい場合は座標圧縮を考える。

Setの演算の計算量

演算	平均計算量
s \| l	$O(len(s) + len(l))$
s & l	$O(min(len(s), len(l))$
s - l	$O(len(s))$

調和級数の計算量

\sum_{k=1}^n 1/k = O(log(n))

倍数のところをインクリメントして素数判定するときとかに出てくる計算量

ABC170-D
ABC172-D
ABC177-E

$A \times B \le K$ の組み合わせを全列挙するときの計算量は $O(KlogK)$ になる。

for a in 1..=k {
    for b in 1..=k/a {
        println!("{} {}", a, b)
    }
}

floor mod

\lfloor\frac{10^N}{M}\rfloor \equiv \lfloor\frac{10^N}{M}\rfloor - kM \equiv \lfloor{\frac{10^N}{M}} - kM\rfloor \equiv \lfloor\frac{10^N - kM^2}{M}\rfloor (mod M)

なので、任意の整数kを使って $10^N$ から引くことができる。これは、 $10^N \% M^2$ に等しい。なので、

ans = pow(10, n, m ** 2) // m % m

のようなことをすれば $O(log(N))$ で求めることができる。

ARC111-A

木の条件

頂点数が $N$ のとき、辺の数が $N-1$

浮動小数点の誤差

>>> 0.07 * 100
7.000000000000001
>>> 0.29 * 100
28.999999999999996

みたいなことになりうるので、四捨五入するために0.5を足す。

bit演算について

bit演算 (&, |, !, ^) は桁ごとに考えると見通しが良くなることが多い。

x桁目が0か1かの判別

>>> a = 10
>>> print(bin(a))
0b1010
>>> x = 2 - 1 # 2桁目について確認
>>> right_shifted_a = a >> x # x+1桁目を1bit目に持ってくる
>>> print(bin(right_shifted_a))
0b101
>>> print(right_shifted_a & 1) # 1ならx桁目が1、そうじゃなければx桁目が0
1

期待値

確率 $p(p≠0)$ で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は $1/p$ である。

ガチャコンプ問題

コンプガチャに必要な回数の期待値の計算

正しいカッコの条件

()(())
(())()
()()()
((()))

みたいなやつ。これになる条件は、左から順に見ていって'('の数をleft、')'の数をrightとおくと、常に $left >= right$ かつ最終的に $left == right$

s = "()(())"

def is_correct_bracket(s: str) -> bool:
    left = 0
    right = 0
    for c in s:
        if c == '(':
            left += 1
        else:
            right += 1
        
        if not (left >= right):
            return False
    return left == right

なんか覚えておきたいこと

3点あるときは真ん中を固定
解答が小さいときは解答から考えればいい
x + y && x - yがあるときは45度回転すると良い。
|x| = max(x, -x)
数が大きいときはmodをとる。
gcd(m, 10)なら例えば"123"は1*10**2 % m + 2*10**1 % m + 3*10**0 % mのように表して良い
周期性があるならmodを考える。modがあれば周期性を考える。
一時不定方程式 $ax + by = c$ は拡張ユークリッドの互除法で解ける。
大きい数のmodを考えるときはn桁目を $10^n$ で表してみる( $gcd(10, mod) == 1$ のとき)
N以下のある条件を持つ数字の数を調べる場合桁DPが使えることが多い
辞書順最小は前から貪欲法！
数え上げは数え上げの順番を逆転させるとうまくいくことがある。

この記事に関するIssueをGithubで作成する