自分用のメモ。気づきがあればその度に追記していく予定なので完成ということはない。使用言語はpythonなので、python固有なことも多くなります。
ref
[1] https://algo-logic.info/how-to-think-cp/#toc_id_12
入力
標準のinput()よりもsys.stdin.readlineのほうがはやいです。
import sys
input = sys.stdin.readlineこうするとinputがsys.stdin.readlineになるので、いつもどおり書けます。特に複数行の入力がある場合はこう書いたほうがよいです。
問題:https://atcoder.jp/contests/tricky/tasks/tricky_1
基本的なこと
math.ceil(x/y)を使ってはいけない
切り上げたいときは多くあると思いますが、このときmath.ceil(x/y)は絶対に使ってはいけません。x/yの時点で浮動小数点演算になり誤差がでるときがあるからです。正しくは浮動小数点演算を経由しないように以下のように書きます。
z=-(-x//y)メモ化再帰
from functools import lru_cache
@lru_cache(maxsize=None)
def rec(x):
pass このように書く。maxsize=Noneで無制限にキャッシュするようになる。ちなみにfunctools.cacheというのが同じ機能だが、python3.9からなのでatcoderだとREになる。
また、キャッシュをそこまで必要としていないときに使うと逆に遅くなる。使い所はシビアなので普通にメモ化したほうがいい気もする。
高速化するために
copy.deepcopy()は遅い
配列をdeepcopyしたいときcopy.deepcopy()が使えますが、これは遅いです。なので以下のように書きます
B=A[:]ただしリストの中身がリストなどの参照型のときはこれだと内側のリストが浅いので
B=[a[:] for a in A]のようにコピーします。これでもcopy.deepcopy()よりはかなりはやいです。
A[::-1]よりreversed(A)のほうがちょっとはやい
リストを反転したいときはA[::-1]よりもreversed(A)のほうがちょっとはやいです。まあちょっとだけなので気になることは少ないと思います。
このときただしA[::-1]は新たなリストになりますがreversed(A)はlist_reverseiteratorオブジェクトとなるので、新たにリストがほしい時はA[::-1]かlist(reversed(A))と書く必要があります。
整数とかbit演算
ある整数が2で割れる回数
def f(n):
k=n&-n
return k.bit_length()-1一番右が1になるまで何回右bitシフトできるか、と思うことができる。
xor
xorは繰り上がりのない足し算というやつ。
\(\ a+b=a\:\mathrm{xor}\: b+2(a\: \mathrm{and}\: b)\)
典型的計算量
\(\ i\in[1,N]\)の倍数を全部見たいとき
つまり以下のようなループ
for i in range(1,N+1):
for j in range(i, N+1, i):
passこれの計算量は\(\ O(N\log(N))\)になります。覚えておきましょう。計算してもでてきますが、感覚的にはある\(\ i\)に対して\(\ j\)が\(\ j=i\)のみなのが\(\ [1,N] \)の約半分、\(\ j\)が2通りあるのが残りの半分のうちのまた半分、とどんどん半分になっていくので\(\ \log_2(N)\)がでてくるイメージですね。
よく使うライブラリ
の重要度。