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

published: 2021/1/13 update: 2021/1/13

Table of Contents
  - 計算量の目安
  - 配列の大きさの限界量
  - 調和級数の計算量
  - floor mod
  - 木の条件
  - 浮動小数点の誤差
  - なんか覚えておきたいこと

計算量の目安

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

配列の大きさの限界量

だいたいが限界。はエラーにならない(rust)。

調和級数の計算量

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

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

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を足す。

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

  • 3点あるときは真ん中を固定
  • 解答が小さいときは解答から考えればいい
  • x + y && x - yがあるときは45度回転すると良い。
  • |x| = max(x, -x)
  • 数が大きいときはmodをとる。
  • 周期性があるならmodを考える。
  • 一時不定方程式は拡張ユークリッドの互除法で解ける。
  • 大きい数のmodを考えるときはn桁目をで表してみる(のとき)

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

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

Twitter: @illuminationK

Privacy Policy

Copyright © illumination-k 2021.