アルゴリズム・数学 Segment Tree のお勉強(2) 遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 概要 前回 → Segment Tree のお勉強 (1) を前提としています。 1点更新... 2020.04.25 アルゴリズム・数学
アルゴリズム・数学 Segment Tree のお勉強(1) 遅延伝搬 Segment 木まで一通り、 $0$ から実装できるようことを目指して、丁寧に自習しました。折角なので記事化。 遅延伝搬 Segment 木は後日、別記事で。 → Segment Tree のお勉強 (2) 概要 ... 2020.04.25 アルゴリズム・数学
アルゴリズム・数学 Euler Tour のお勉強 個人的に勉強したことを整理します。 新規性とか強い主張とかは、特にありません。 Euler Tour (1) DFS 順に探索して、通った頂点の列を記録する($1,2,3,4,3,2,5,2,1,6,1$)。(2... 2020.04.20 アルゴリズム・数学
アルゴリズム・数学 Rolling Hashについて(survey + 研究) 新しい数値設定や実装方法を提案するものではありません。 衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。 前提知識 本記事では簡単のため、アルファベットの集合を $\Sigma = \{0... 2020.04.05 アルゴリズム・数学
アルゴリズム・数学 [数学] 畳み込み入門:Dirichlet積とゼータ変換・メビウス変換 色々な畳み込み 一般的な理解から始めるのではなく,まずは具体例をざっと確認します. $A$ を数列とします.つまり,$A = $ のように数が非負整数で添字付けられていて並んでおり,その全体を $A$ と書きます. ※ ... 2019.11.02 アルゴリズム・数学
アルゴリズム・数学 マトロイドのお勉強(JSC2019予選 [E] Card Collector) 問題文 → ■自分の提出 → ■ (コンテスト外)公式解説pdf → ■ 公式解説pdf 、特に「マトロイドを知っていれば一発」という部分について、マトロイドの基礎を学んだり、他の方の本問題を扱ったブログ等を見ても、なかなかスマートな理解... 2019.10.04 アルゴリズム・数学問題解説
アルゴリズム・数学 [数学] n乗の計算 $a^n$ の計算について整理します。この記事の大部分は、実数のべき乗に限らず、結合法則を満たす積が定義されているもの全てに適用できます。実数以外では、行列のべき乗や多項式のべき乗などが多いでしょうか。 なお、pythonでは組み込み関数... 2019.06.30 アルゴリズム・数学
アルゴリズム・数学 [数学] Euclid の互除法 $x,y$ の最大公約数 $\mathrm{gcd}(x,y)$ を計算します(最大公約数は英語でgreatest common divisorですので、gcdと略されます)。 なお、$x=y=0$ の場合には、任意の整数が $x,y$ ... 2019.06.16 アルゴリズム・数学