AtCoder Beginner Contest 219 G - Propagation
問題 https://atcoder.jp/contests/abc219/tasks/abc219_g
解説 https://atcoder.jp/contests/abc219/editorial/2670
コメント (折り畳み)
クエリ平方分割による解法の説明です。
AtCoder Beginner Contest 238 F - Two Exams
問題 https://atcoder.jp/contests/abc238/tasks/abc238_f
解説 https://atcoder.jp/contests/abc238/editorial/3387
コメント (折り畳み)
平衡二分木を用いることで計算量を $O(N ^ 2 \log N)$ 時間に改善する方法について書いています。
AtCoder Beginner Contest 162 E - Sum of gcd of Tuples (Hard)
問題 https://atcoder.jp/contests/abc162/tasks/abc162_e
解説 https://atcoder.jp/contests/abc162/editorial/3469
コメント (折り畳み)
$O(K ^ {\frac{2}{3}} (\log \log K) ^ {\frac{1}{3}} + K ^ {\frac{1}{2}} \log N)$ 時間解法の解説です。
- $N$ を固定したとき、$\lfloor N/x \rfloor$ の値で整数 $x$ を分類すると、高々 $2\lfloor\sqrt{N}\rfloor$ 個の区間に分けられること
- トーシェント関数 $\varphi$ の prefix sum の高速計算 (https://yukcoder.me/wiki/sum_totient)
を用いて高速化します。
AtCoder Beginner Contest 246 F - typewriter
問題 https://atcoder.jp/contests/abc246/tasks/abc246_f
解説 https://atcoder.jp/contests/abc246/editorial/3727
コメント (折り畳み)
非想定解法です。
AtCoder Beginner Contest 256 F - Cumulative Cumulative Cumulative Sum
問題 https://atcoder.jp/contests/abc256/tasks/abc256_f
解説 https://atcoder.jp/contests/abc256/editorial/4152
コメント (折り畳み)
数列 $A$ に対して累積和を 3 回取ってできる数列 $D$ の $k$ 項目を表す式を母関数を用いて機械的に導出する方法を説明しています。
dwangoプログラミングコンテスト D - タクシー
問題 https://atcoder.jp/contests/dwango2015-prelims/tasks/dwango2015_prelims_4
解説 https://atcoder.jp/contests/dwango2015-prelims/editorial/4570
コメント (折り畳み)
公式解説で説明が省略されている部分の補足と $\displaystyle \min _ x \sum _ {i = 1} ^ N w _ i \lvert x - t _ i \rvert$ の計算に関する別解について説明しています。
AtCoder Beginner Contest 278 G - Generalized Subtraction Game
問題 https://atcoder.jp/contests/abc278/tasks/abc278_g
解説 https://atcoder.jp/contests/abc278/editorial/5253
コメント (折り畳み)
$O(N ^ 2)$ 時間で Grundy 数を全て計算する解法です。
AtCoder Beginner Contest 213 H - Stroll
問題 https://atcoder.jp/contests/abc213/tasks/abc213_h
解説 https://atcoder.jp/contests/abc213/editorial/5488
コメント (折り畳み)
形式的冪級数を要素とする行列を考えることで導出される $O(N ^ 3 T \log T)$ 時間解法です。
AtCoder Beginner Contest 289 F - Teleporter Takahashi
問題 https://atcoder.jp/contests/abc289/tasks/abc289_f
解説 https://atcoder.jp/contests/abc289/editorial/5739
コメント (折り畳み)
$i$ step 後に存在しうる点の集合はおおよそ矩形領域として記述できることを用いて implicit に BFS を行う解法です。BFS の性質から最短遷移を計算できます。
AtCoder Beginner Contest 289 Ex - Trio
問題 https://atcoder.jp/contests/abc289/tasks/abc289_h
解説 https://atcoder.jp/contests/abc289/editorial/5749
コメント (折り畳み)
公式解説で Bonus として言及されている人が $n\leq 10 ^ 5$ 人いる場合の問題を $O(n (\log n) ^ 2 + T (\log T) ^ 2)$ 時間で解く解法です。
人 $1$ から人 $i$ への相対座標 $n-1$ 個を不定元として持つ多次元の形式的冪級数を考えると連続する $j$ に対する $\prod _ {i = 1} ^ n (j + a _ i)!$ や $\prod _ {i = 1} ^ n (j - a _ i)!$ の形の計算へと落ちます。差分更新を考えると、差分の計算は $\prod _ {i = 1} ^ n (x + a _ i)$ や $\prod _ {i = 1} ^ n (x - a _ i)$ の多点評価へと帰着されます。
