アルゴリズム・数学 分割統治+FFT のよくある形のひとつ
概要
「分割統治FFT」というと特に みたいなタイプを指すような会話を少し見たことがあるのですが，どのくらい一般的な用語なのか分からず．
私は雑に，分割統治と FFT を組み合わせて答が求められる系のテクニックをすべて分割統...
maspy
アルゴリズム・数学 問題解説 [yukicoder] No.1574 Swap and Repaint
概要
問題文 → ■公式解説 → ■自分の提出 → ■
大体公式解説と同じですが， $O(N\log^2N)$ ということで一応書きます．
いろんなところで多項式だけではなく Laurent 多項式が現れることに注意してください．
...
問題解説 [yukicoder] No.1888 Odd Insertion
概要
問題文 → ■自分の提出 → ■
解説の貪欲法とは違ったので一応．考察はこちらの方が簡単だという気がする．
解法
$S = (A_1, A_2, \ldots, A_N)$, $P=(1,2,\ldots,N)$ となる...
問題解説 [yukicoder] No.1840 Random Painting
概要
問題文 → ■自分の提出 → ■
設定されている難易度（★の数）に比べてかなり簡単に感じた．
解法
今まで訪問したことがあるタイルの集合を単に状態と呼ぶことにします．答は次のように書けます．
白マスが存在するよう...
問題解説 [yukicoder] No.596 郵便配達
概要
問題文 → ■自分の提出 → ■
AC 人数も少なく難易度評価も高い問題ですが，解法はかなりシンプルに感じました．
考察も実装も他の方の解説より簡単にできたと感じたので，自身のロジックの確認も兼ねて解説執筆しておきます．
解法...
アルゴリズム・数学 重心分解・1/3重心分解のお絵描き
お絵描きをしました。
重心分解
木の重心の定義や計算方法については省略します．
重心分解の図示
木の重心のひとつを求め，重心を取り除き連結成分に分けることを繰り返します．
各ステップにおいて，重心のひとつを根...
問題解説 [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． → 解決しました．
簡単な例
手法の説明のため，次の自明な問...