Library Checker [Library Checker] Polynomial Root Finding (Mod 998244353)
問題概要
問題文 → ■
多項式の相異なる $1$ 次の因数を列挙する問題だと見なすこともできます．特にこの問題は，多項式の因数分解の特殊ケースです．実際，以下で解説するアルゴリズムはほとんどそのまま多項式の因数分解アルゴリズ...
maspy
Library Checker 未分類 [Library Checker] Associative Array
問題概要
問題文 → ■
連想配列（Associative Array）の問題．
単純な処理なので使用頻度はかなり高いです．標準ライブラリを使う場合にパフォーマンスが良い実装方法を確認したり，適切なライブラリを整備する利点はかなり...
Library Checker [Library Checker] Many A + B
問題概要
問題文 → ■
$A, B$ が与えられるので $A+B$ を出力するというだけの問題です．
この問題はサイトの使い方を確認するための問題である一方で，入出力ライブラリの実行速度を比べるような目的でも利用されています．
...
未分類 [Library Checker] Predecessor Problem
概要
問題文 → ■
競技プログラミングでは，長さ $N$ の配列に対して何かをする場合に，適当な条件を満たすインデックス全体などを管理する目的で使うことが多いと思います．利用できる場面はかなり多く，想定解よりも少し悪い計算量...
問題解説 [yukicoder] No.2579 Dice Sum Infinity (制約変更版)
概要
問題文 → ■公式解説 → ■自分の提出 → ■
あまり見直していないので細かい数式の誤植が心配ですが方針は理解できると思います．
解法
方針
目的を達成したあとも永遠にサイコロを振り続けることを考えて，次のように...
問題解説 [yukicoder] No.1787 Do Use Dynamic Tree
概要
問題文 → ■公式解説 → ■自分の提出 → ■
動的木を使わなくて良かった．
解法
HL 分解して，heavy path, light edge などの言葉を使います．だいたい次のようにします．
パスの最後の ...
問題解説 [yukicoder] No.1762 🐙🐄🌲
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法
まずは $P$ のことを忘れて解きます．$N=4n+1$ とします．
次の指数型母関数を考えます：
$A(x) = \sum \dfrac{a_n}{...
アルゴリズム・数学 分割統治+FFT のよくある形のひとつ
概要
「分割統治FFT」というと特に みたいなタイプを指すような会話を少し見たことがあるのですが，どのくらい一般的な用語なのか分からず．
私は雑に，分割統治と FFT を組み合わせて答が求められる系のテクニックをすべて分割統...
問題解説 [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)$ となる...