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

計算量の目安

配列の大きさの限界量

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

Setの演算の計算量

調和級数の計算量

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

• 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

なので、任意の整数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が使えることが多い
• 辞書順最小は前から貪欲法！
• 数え上げは数え上げの順番を逆転させるとうまくいくことがある。