アルゴリズム・数学 分割統治による静的列の区間積クエリ
概要
本記事では、次の形の問題を扱います。
$X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ：区間 $[a,b)$ が与えられるので、...
maspy
アルゴリズム・数学 問題解説 [Library Checker] Min of Mod of Linear
概要
問題文 → ■自分の提出 → ■
$O(\log M)$ 時間で解く方法を解説します。
準備：最良近似分数と Farey 数列
この記事において、「有理数 $\frac{p}{q}$」などと書けば、$p,q$ は互...
問題解説 [yukicoder] No.2166 Paint and Fill
概要
問題文 → ■公式解説 → ■自分の提出 → ■
制約 1 の取り扱いが、少し別解っぽかったので書いておきます。
公式解説補足
$f=1$ となる（疎な）多項式と定数 $N$ に対して、$F_k = f(x)^N$ で定...
問題解説 [yukicoder] No.2114 01 Matching
概要
問題文 → ■公式解説 → ■自分の提出 → ■
解法
$K=1$ に帰着します。次のような問題が解ければよいです。
点 $X_0, \ldots, X_N$ （$X_i \leq X_{i+1}$）がある。各点は...
アルゴリズム・数学 slope trick (3) slope trick の凸共役
slope trick (1) 解説編
slope trick (2) 問題編
概要
凸関数の凸共役（Legendre-Fenchel 変換）とその性質について、軽くまとめます。さらに、slope trick による...
問題解説 [yukicoder] No.1216 灯籠流し/Lanterns
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説よりも計算量が良いので、書いておきます。
解法
消灯への対応
$v$ を出発した灯籠が、$w$ から先では消灯しているとします。このとき、
$v$ か...
問題解説 [yukicoder] No.1763 Many Balls
概要
問題文 → ■公式解説 → ■自分の提出 → ■
割と素直な解法だと思いますが、少し公式解説と違うのかな？大差での Fastest AC にもなったので、書いておきます。
解法 $p = 90001$ とします。$K = 60...
問題解説 [yukicoder] No.1379 Postponed
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説では、最小値の挙動に注目しています。私は最大値の挙動に注目して解いたので、解説しておきます。
私の解説では、$A_i+1$ のことを改めて $A_i$ と呼ぶこと...
AtCoder [AtCoder] ジャッジが壊れている問題
ジャッジがこわれていて AC 不可能
（特殊ジャッジ） （特殊ジャッジ） （誤差ジャッジ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （特殊...
問題解説 [yukicoder] No.1353 Limited Sequence
概要
問題文 → ■公式解説 → ■自分の提出 → ■
想定解法よりも計算量が落ちたようなので、一応書いておきます。$O(R\log R)$ 時間で解けます。
解法
$a$ を $1$ 個以上 $k=A_a$ 個以下並べ...