maspy

スポンサーリンク
Library Checker

[Library Checker] Static RMQ

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

グラフ数え上げ

概要 「$N$ 頂点のグラフであって xx を満たすものはいくつありますか?」という種類の問題を扱います. いわゆる入力定数個の数え上げ問題です.「グラフが与えられるので条件を満たす部分グラフを数えよ」というタイプの問題は扱い...
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$ 次の因数を列挙する問題だと見なすこともできます.特にこの問題は,多項式の因数分解の特殊ケースです.実際,以下で解説するアルゴリズムはほとんどそのまま多項式の因数分解アルゴリズ...
未分類

[Library Checker] Associative Array

問題概要 問題文 → ■ 連想配列(Associative Array)の問題. 単純な処理なので使用頻度はかなり高いです.標準ライブラリを使う場合にパフォーマンスが良い実装方法を確認したり,適切なライブラリを整備する利点はかなり...
Library Checker

[Library Checker] Many A + B

問題概要 問題文 → ■ $A, B$ が与えられるので $A+B$ を出力するというだけの問題です. この問題はサイトの使い方を確認するための問題である一方で,入出力ライブラリの実行速度を比べるような目的でも利用されています. ...
問題解説

[yukicoder] No.2579 Dice Sum Infinity (制約変更版)

概要 問題文 → ■公式解説 → ■自分の提出 → ■ あまり見直していないので細かい数式の誤植が心配ですが方針は理解できると思います. 解法 方針 目的を達成したあとも永遠にサイコロを振り続けることを考えて,次のように...
スポンサーリンク
タイトルとURLをコピーしました