アルゴリズム・数学

概要 この記事 の手法の一部を掘り下げたものです．少し適用例が集まったので記事化． 残念ながら，計算量オーダーの証明はしていないです，HELP． → 解決しました． 簡単な例 手法の説明のため，次の自明な問...

概要 本記事では、次の離散対数問題の変種を扱います。 $X$ をモノイド、$S$ を集合とし、$X$ が $S$ に左作用しているとする。$x\in X$ および $s, t \in S$ および、正整数 $N$ が与えられる...

概要 本記事では、次の形の問題を扱います。 $X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ：区間 $[a,b)$ が与えられるので、...

slope trick (1) 解説編 slope trick (2) 問題編 概要 凸関数の凸共役（Legendre-Fenchel 変換）とその性質について、軽くまとめます。さらに、slope trick による...

概要 下降冪 $(x)_n$、符号つき第 1 種 Stirling 数 $s(n,k)$、第 2 種 Stirling 数 $S(n,k)$ を次で定義します： $(x)_n = \prod_{0\leq i < n} ...

概要 この記事では常に $p$ は素数を表すこととし、$i, k, n$ は整数、$x$ は実数を表すものとします。特に単に $\sum_{p\leq x}$ や $\prod_{p\leq x}$ などと書いて、素数にわたる和や積...

以下の、解説編を読んでいることを仮定とします。使う記号などは共通で、改めて説明していません。 前 → (1) 解説編 ABC 127 Absolute minima 解説編で述べたものをそのまま実装すれば...

続き → (2) 問題編 ネタバレに配慮して、これが使える問題をまとめたものは、別記事 (2) 扱いとしています。 実装をしている具体的なコードについても、必要であれば (2) 問題編 における解答例を確認してください。 ...

概要 「Python で競技プログラミングをやる」の文脈で、高速フーリエ変換を使うための基礎知識を整理します。 高速フーリエ変換自体は競技プログラミング以外の文脈でも重要なアルゴリズムですが、そうした需要に応えることは、本記事...