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