アルゴリズム・数学 Euler Tour のお勉強
個人的に勉強したことを整理します。
新規性とか強い主張とかは、特にありません。
Euler Tour
(1) DFS 順に探索して、通った頂点の列を記録する（$1,2,3,4,3,2,5,2,1,6,1$）。(2...
maspy
アルゴリズム・数学 問題解説 [yukicoder] No.803 Very Limited Xor Subset
概要
問題文 → ■公式解説 → ■自分の提出 → ■
うっかり、$M \leq 300$ という制約がない状態で考えてしまったので、記しておきます。$N, M$ について線形です。
解法
$\xor$ ですので、$A_i$ を列ベ...
AtCoder [AtCoder 参加感想] 2020/04/12:ABC 162
A
B
C
D
E
F
問題文
■
■
■
■
■
■
自分の提出
■
■
■
■
■
■
結果
AC
AC
AC
AC
AC
AC
全体感想
26分全完で、20位でした。
言語アプデと関係...
問題解説 [yukicoder] No.42 貯金箱の溜息
概要
問題文 → ■公式解説 → ■自分の提出 → ■
最終的な結論は同じです。
解法
硬貨の価値の集合を $A = \{1,5,10,50,100,500\}$ と書きます。
多項式・形式的べき級数による解法に慣れていれば、直ちに...
問題解説 [yukicoder] No.886 Direct
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説の、$\Theta(H\log H)$ よりも計算量がよいので、書きます。Project Euler でよく見る手法のひとつですね。正方形では何度も経験があるけれど、長方形で...
問題解説 [yukicoder] No.262 面白くないビットすごろく
概要
問題文 → ■公式解説 → ■自分の提出 → ■
埋め込みとか、$\sqrt{N}$ 単位の計算量を仮定した解説しかなかったので、一応書きます。たとえば制約が、$N\leqq 10^{18}$ でもすぐに答が出ます。
解法
次...
問題解説 [yukicoder] No.161 制限ジャンケン
概要
問題文 → ■公式解説 → ■
問題に対して大げさな手法を持ち出しすぎなのはそれはそうなのですが、これが見えるようになったことに成長を感じます。
解法
最小費用流問題に帰着できます。
・source S から貼る...
アルゴリズム・数学 Rolling Hashについて（survey + 研究）
新しい数値設定や実装方法を提案するものではありません。
衝突確率の下からの評価に対して、見たことがない考察を行ったので、記しておきます。
前提知識
本記事では簡単のため、アルファベットの集合を $\Sigma = \{0...
AtCoder [AtCoder 参加感想] 2020/04/04:ABC 161
A
B
C
D
E
F
問題文
■
■
■
■
■
■
自分の提出
■
■
■
■
■
■
結果
AC
AC
AC
AC
AC
AC
全体感想
26分全完で、2位でした。
...
自作問題 [yukicoder]初めての作問（yukicoder contest 242）
コンテストページ：■ 参加してくださった方、ありがとうございました！そうでない方も、お時間のございますときに、是非考えてみてください。面白いと思った問題には、yukicoder の問題ページから Fav★ をしていってくれると嬉...