Open7
競技プログラミングメモ
ウチコ
-
(a + b) mod dは(a mod b) + (b mod d)できる。 - 各要素を mod でグルーピングして、グループ数に絞り、全探索する。
ウチコ
01-BFS
ウチコ
9の倍数: 各桁の数字の和が 9 の倍数
- 3の倍数: 各桁の数字の和が 3 の倍数
- 4の倍数: 下2桁が 4 の倍数
ウチコ★4までの問題 44問
ウチコ
最小公倍数は
a x b / gcd(a,b)
オーバーフローに注意。
10^18 なら long long で収まるので、計算結果がオーバーフローにならないように注意。
計算結果が 10^18 より大きい数値になるかならないかの判定は以下の手順。
- b / gcd(a, b) を求める。
- 1.の値が 10^18 / a よりも大きい場合は、10^9以上の数値のなるので Large。
ウチコセグメント木
セグメント木でできること
- 区間上の値を更新する
- 任意の区間上の最小値や合計値を取得する
セグメント木のクエリ
- 区間変更クエリ：加算、更新
- 区間取得クエリ：最小値、最大値、和
モノイドとAtCoderのlazy_segtree
セグメント木に載せられるのは モノイド。
結合則：X の任意の元 𝑎,𝑏,𝑐 について、𝑎•(𝑏•𝑐)=(𝑎•𝑏)•𝑐
単位元 e の存在：Mの任意の元 a について、𝑒•𝑎=𝑎•𝑒=𝑎 を満たす X の元 e が存在する
AtCoder LibraryのLazy Segtree。
以下は、区間変更クエリ：更新、区間取得クエリ：最大値の場合の設定。
- モノイドの型 S
int
- S×S→S を計算する関数 S op(S a, S b)
S op(S a, S b) { return max(a, b); }
- e を返す関数 S e()
S e() { return -INF; }
- 写像の型 F
int
- f(x) を返す関数 S mapping(F f, S x)
S mapping(F f, S x) { return max(f, x); }
- f∘g を返す関数 F composition(F f, F g)
F composition(F f, F g) { return max(f, g); }
- id を返す関数 F id()
F id() { return 0; }
参考