アルゴリズム・数学 slope trick (2) 問題編
以下の、解説編を読んでいることを仮定とします。使う記号などは共通で、改めて説明していません。
前 → (1) 解説編
ABC 127 Absolute minima
解説編で述べたものをそのまま実装すれば...
アルゴリズム・数学 アルゴリズム・数学 slope trick (1) 解説編
続き → (2) 問題編
ネタバレに配慮して、これが使える問題をまとめたものは、別記事 (2) 扱いとしています。
実装をしている具体的なコードについても、必要であれば (2) 問題編 における解答例を確認してください。
...
アルゴリズム・数学 [数学・numpy] 高速フーリエ変換(FFT)による畳み込み
概要
「Python で競技プログラミングをやる」の文脈で、高速フーリエ変換を使うための基礎知識を整理します。
高速フーリエ変換自体は競技プログラミング以外の文脈でも重要なアルゴリズムですが、そうした需要に応えることは、本記事...
アルゴリズム・数学 Segment Tree のお勉強(2)
遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。
概要
前回 → Segment Tree のお勉強 (1)
を前提としています。
1点更新...
アルゴリズム・数学 Segment Tree のお勉強(1)
遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。
遅延伝搬 Segment 木は後日、別記事で。 → Segment Tree のお勉強 (2)
概要
...
アルゴリズム・数学 Euler Tour のお勉強
個人的に勉強したことを整理します。
新規性とか強い主張とかは、特にありません。
Euler Tour
(1) DFS 順に探索して、通った頂点の列を記録する（$1,2,3,4,3,2,5,2,1,6,1$）。(2...
アルゴリズム・数学 Rolling Hashについて（survey + 研究）
新しい数値設定や実装方法を提案するものではありません。
衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。
前提知識
本記事では簡単のため、アルファベットの集合を $\Sigma = \{0...
アルゴリズム・数学 [数学] 畳み込み入門：Dirichlet積とゼータ変換・メビウス変換
色々な畳み込み
一般的な理解から始めるのではなく，まずは具体例をざっと確認します．
$A$ を数列とします．つまり，$A = $ のように数が非負整数で添字付けられていて並んでおり，その全体を $A$ と書きます．
※ ...
アルゴリズム・数学 マトロイドのお勉強（JSC2019予選 [E] Card Collector）
問題文 → ■自分の提出 → ■ （コンテスト外）公式解説pdf → ■
公式解説pdf 、特に「マトロイドを知っていれば一発」という部分について、マトロイドの基礎を学んだり、他の方の本問題を扱ったブログ等を見ても、なかなかスマートな理解...
アルゴリズム・数学 [数学] n乗の計算
$a^n$ の計算について整理します。この記事の大部分は、実数のべき乗に限らず、結合法則を満たす積が定義されているもの全てに適用できます。実数以外では、行列のべき乗や多項式のべき乗などが多いでしょうか。
なお、pythonでは組み込み関数...