LibraryChecker

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

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

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

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

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

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

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

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

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

問題概要 問題文 → ■ 多項式の相異なる $1$ 次の因数を列挙する問題だと見なすこともできます．特にこの問題は，多項式の因数分解の特殊ケースです．実際，以下で解説するアルゴリズムはほとんどそのまま多項式の因数分解アルゴリズ...