Library Checker

Library Checker について

想定解の解説・いろいろな解法の解説・最速提出に関する調査・関連事項の解説などをやっていきます.問題は問題名の辞書順に並べています.

公開日 問題
2024/01/28 Associative Array
2024/04/22 Compositional Inverse of Power Series (Large)
2024/04/24 Composition of Formal Power Series (Large)
2024/01/22 Count Points in Triangles
2024/01/24 Enumerate Quotients
2024/01/21 Gcd of Gaussian Integers
2024/01/18 Many A + B
2024/09/09 Matrix Product (Mod 2)
2023/01/02 Min of Mod of Linear
2024/09/28 Nim Product
2024/09/04 Point Set Tree Path Composite Sum
2024/09/04 Point Set Tree Path Composite Sum (Fixed Root)
2024/01/18 Polynomial Root Finding (Mod 998244353)
2023/05/05 Power Projection of Set Power Series
2024/05/04 Predecessor Problem
2024/01/23 Range Set Range Composite
2024/02/06 Static RMQ

 

スポンサーリンク
Library Checker

[Library Checker] Nim Product

問題概要 問題文 → ■ 自分の提出 → ■(89ms) (非想定解などで)定数倍バトルになることを複数回経験したので,Library Checker 最速周辺の実装を勉強しました.過去に取り組んだときには最速実装が理解できな...
Library Checker

[Library Checker] Matrix Prooduct (Mod 2)

問題概要 問題文 → ■ 自分の提出 → ■ (212ms) この問題は,実行時間に占める入出力の割合が比較的大きいです. 本記事内での私の提出では,入出力に 180 ms 程度を要しているようです.実行時間を比...
Library Checker

[Library Checker] Point Set Tree Path Composite Sum

問題概要 問題文 → ■, ■自分の提出 → ■(根付き木, 169 ms),■ (全方位,332 ms) Static Top Tree (以下 STT)と呼ばれるデータ構造を用いた解法の実装例について解説します. S...
Library Checker

[Library Checker] Rational Approximation

問題概要 問題文 → ■自分の提出 → ■ (35 ms) 一発書きで fastest (2024/08/27)になったのは意外でした. 解法 以下,有理数と言えば非負であることを仮定し,有理数 $a/b$ のよう...
Library Checker

[Library Checker] Static RMQ

問題概要 問題文 → ■ 列が静的(Static)というのは,変更されないということです.静的な列に対する区間 $\min$ クエリに答える問題です. この記事の読者であればこの問題を簡単に解ける人がほとんどだと思います...
Library Checker

[Library Checker] Enumerate Quotients

問題概要 問題文 → ■ $N$ を正の整数とし,$S = \bigl\lbrace\lfloor N/x\rfloor\mid x\in\lbrace 1,2,\ldots,N\rbrace\bigr\rbrace$ としま...
Library Checker

[Library Checker] Range Set Range Composite

問題概要 問題文 → ■ 代入操作に特化した場合の区間作用・区間積クエリという問題です. 解法1:遅延セグメント木 ある区間をすべて $a$ で置き換えたときの区間積 $a^n$ は繰り返し二乗法で $O(\log...
Library Checker

[Library Checker] Count Points in Triangles

問題概要 問題文 → ■ 三角形内部の点の個数を数える問題です. 解法1:愚直解 $4$ 点 $A,B,C,p$ に対して $p$ が $\triangle ABC$ の内部にあるか否かを $\Theta(1)$ ...
Library Checker

[Library Checker] Gcd of Gaussian integers

問題概要 問題文 → ■ Gauss 整数環における gcd の計算です.基本的な定義は問題文を見てください.本解説は,高校数学レベルの前提知識で十分読めるように書いていると思います. Gauss 整数環の性質 【...
Library Checker

[Library Checker] Polynomial Root Finding (Mod 998244353)

問題概要 問題文 → ■ 多項式の相異なる $1$ 次の因数を列挙する問題だと見なすこともできます.特にこの問題は,多項式の因数分解の特殊ケースです.実際,以下で解説するアルゴリズムはほとんどそのまま多項式の因数分解アルゴリズ...
スポンサーリンク
タイトルとURLをコピーしました