集合べき級数解説 集合べき級数 (1) subset convolution 参考文献 (arXiv) Fourier meets Mobius : Fast subset convolutionFourier Meets Mobius: Fast Subset Convolution Elegi... 2023.05.05 集合べき級数解説
アルゴリズム・数学 モノイド作用に関する離散対数問題 概要 本記事では、次の離散対数問題の変種を扱います。 $X$ をモノイド、$S$ を集合とし、$X$ が $S$ に左作用しているとする。$x\in X$ および $s, t \in S$ および、正整数 $N$ が与えられる... 2023.03.28 アルゴリズム・数学
アルゴリズム・数学 分割統治による静的列の区間積クエリ 概要 本記事では、次の形の問題を扱います。 $X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ:区間 $[a,b)$ が与えられるので、... 2023.02.11 アルゴリズム・数学
Library Checker [Library Checker] Min of Mod of Linear 概要 問題文 → ■自分の提出 → ■ $O(\log M)$ 時間で解く方法を解説します。 準備:最良近似分数と Farey 数列 この記事において、「有理数 $\frac{p}{q}$」などと書けば、$p,q$ は互... 2023.01.02 Library Checker
問題解説 [yukicoder] No.2166 Paint and Fill 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 制約 1 の取り扱いが、少し別解っぽかったので書いておきます。 公式解説補足 $f=1$ となる(疎な)多項式と定数 $N$ に対して、$F_k = f(x)^N$ で定... 2022.12.19 問題解説
問題解説 [yukicoder] No.2114 01 Matching 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 $K=1$ に帰着します。次のような問題が解ければよいです。 点 $X_0, \ldots, X_N$ ($X_i \leq X_{i+1}$)がある。各点は... 2022.10.29 問題解説
アルゴリズム・数学 slope trick (3) slope trick の凸共役 slope trick (1) 解説編 slope trick (2) 問題編 概要 凸関数の凸共役(Legendre-Fenchel 変換)とその性質について、軽くまとめます。さらに、slope trick による... 2022.10.29 アルゴリズム・数学
問題解説 [yukicoder] No.1216 灯籠流し/Lanterns 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説よりも計算量が良いので、書いておきます。 解法 消灯への対応 $v$ を出発した灯籠が、$w$ から先では消灯しているとします。このとき、 $v$ か... 2022.10.15 問題解説
問題解説 [yukicoder] No.1763 Many Balls 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 割と素直な解法だと思いますが、少し公式解説と違うのかな?大差での Fastest AC にもなったので、書いておきます。 解法 $p = 90001$ とします。$K = 60... 2022.10.15 問題解説
問題解説 [yukicoder] No.1379 Postponed 概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説では、最小値の挙動に注目しています。私は最大値の挙動に注目して解いたので、解説しておきます。 私の解説では、$A_i+1$ のことを改めて $A_i$ と呼ぶこと... 2022.10.10 問題解説