アルゴリズム・数学 重心分解・1/3重心分解のお絵描き
お絵描きをしました。
重心分解
木の重心の定義や計算方法については省略します．
重心分解の図示
木の重心のひとつを求め，重心を取り除き連結成分に分けることを繰り返します．
各ステップにおいて，重心のひとつを根...
maspy
アルゴリズム・数学 問題解説 [yukicoder] No.2507 Yet Another Subgraph Counting
概要
問題文 → ■自分の提出 → ■
計算量 $O(N^42^N)$ なので、指数は公式解説よりもよいです（本問の制約下で fastest がとれるかは分かりません）。
必要に応じて、集合べき級数解説 を参照してください。
...
問題解説 [yukicoder] No.2504 NOT Path Painting
概要
問題文 → ■自分の提出 → ■
解説と同じ式が出てきます。もう少し簡単に導出しているつもりです。
解法
求める期待値は、次のように書けます：
$k$ 回操作しても白点が存在するような確率を $p_k$ とす...
未分類 AtCoder WTF 2022 (お手伝いとして参加）
問題の解法については何も書きません．
tester
8 月後半の競プロ活動の多くの部分をこの 10 問にあてた．たのしー．
人材的に片方くらいは手伝った方がいいだろうなとは思っていたんですが，検討の結果 2 セットまとめ...
アルゴリズム・数学 $K$ 個を選ぶ最適化における乱択アルゴリズム
概要
この記事 の手法の一部を掘り下げたものです．少し適用例が集まったので記事化．
残念ながら，計算量オーダーの証明はしていないです，HELP． → 解決しました．
簡単な例
手法の説明のため，次の自明な問...
集合べき級数解説 集合べき級数関連 (4) 問題例
Distinct Multiples (ABC 236 Ex)
ユーザー解説に書いた通り．集合べき級数の $\exp$ で $O(N^22^N)$ 時間で解ける．
Connectivity 2 (ABC 2...
集合べき級数解説 集合べき級数関連 (3) 集合べき級数の Power Projection
参考文献
Elegia さん：
転置原理により本記事で扱う問題の解法が導出できることについて述べている．
ryuhe1 さん：
転置原理について詳細な記述がある．
noshi91 さん：
...
集合べき級数解説 集合べき級数 (2) 多項式との合成
参考文献
Elegia さん：
本記事で扱っているアルゴリズムはここで紹介されているものとほぼ同一です．ただし以下の点について，定式化や議論を変更・追加しています．
分母 $\frac{1}{k!}$ について説明し，...
集合べき級数解説 集合べき級数 (1) subset convolution
参考文献
(arXiv) Fourier meets Mobius : Fast subset convolutionFourier Meets Mobius: Fast Subset Convolution
Elegi...
アルゴリズム・数学 モノイド作用に関する離散対数問題
概要
本記事では、次の離散対数問題の変種を扱います。
$X$ をモノイド、$S$ を集合とし、$X$ が $S$ に左作用しているとする。$x\in X$ および $s, t \in S$ および、正整数 $N$ が与えられる...