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

published: 2021/1/13 update: 2021/6/20

Table of Contents

計算量の目安

orderよくある制約よくあるアルゴリズム
全探索
二分探索、ソート
全探索
半分全列挙+二分探索
全探索
半分全列挙
bit全探索, bitDP
順列、組み合わせ

配列の大きさの限界量

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

Setの演算の計算量

演算平均計算量
s \| l
s & l
s - l

調和級数の計算量

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

  • ABC170-D
  • ABC172-D
  • ABC177-E

の組み合わせを全列挙するときの計算量はになる。

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

floor mod

なので、任意の整数kを使ってから引くことができる。これは、に等しい。 なので、

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

のようなことをすればで求めることができる。

  • ARC111-A

木の条件

頂点数がのとき、辺の数が

浮動小数点の誤差

>>> 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

期待値

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

ガチャコンプ問題

正しいカッコの条件

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

みたいなやつ。これになる条件は、左から順に見ていって'('の数を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があれば周期性を考える。
  • 一時不定方程式は拡張ユークリッドの互除法で解ける。
  • 大きい数のmodを考えるときはn桁目をで表してみる(のとき)
  • N以下のある条件を持つ数字の数を調べる場合桁DPが使えることが多い
  • 辞書順最小は前から貪欲法!
  • 数え上げは数え上げの順番を逆転させるとうまくいくことがある。

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

ofuse
Privacy Policy

Copyright © illumination-k 2021.