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

published: 2021/1/13 update: 2021/4/11

Table of Contents
  - 計算量の目安
  - 配列の大きさの限界量
  - Setの演算の計算量
  - 調和級数の計算量
  - floor mod
  - 木の条件
  - 浮動小数点の誤差
  - bit演算について
    - x桁目が0か1かの判別
  - 期待値
    - ガチャコンプ問題
  - なんか覚えておきたいこと

計算量の目安

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

配列の大きさの限界量

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

Setの演算の計算量

演算平均計算量
`sl`
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

期待値

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

ガチャコンプ問題

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

  • 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桁目をで表してみる(のとき)

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

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

Twitter: @illuminationK

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

ofuse
Privacy Policy

Copyright © illumination-k 2021.