2020年3月7日グラフヒープ,優先度付きキュー,貪欲法,グラフ,競プロ,重み付きグラフ,単一始点最短経路,最短経路,ダイクストラ法

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては

計算量が \(O(|E| \l ...

2020年3月7日グラフ単一始点最短経路,最短経路,負の閉路,負の辺,グラフ,競プロ,重み付きグラフ,ベルマンフォード法

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、

負の辺が含まれているような場合でも適用 ...

2020年3月6日その他区間,累積和,imos法,二次元区間和,区間和,テーマ記事,競プロ

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理：\(O(N)\)
クエリ：\(O(1)\)

で処理がで ...

2020年3月5日データ構造二分探索,セグメント木,区間,データ構造,RAQ,RSQ,転倒数,二次元BIT,BIT,区間和

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...

2020年3月4日数学約数,競プロ,全列挙

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。

単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活かすと \(O(\sqrt{N})\) で全列 ...

2020年3月3日AtCoder競プロ,連結成分,Union-Find,グラフ

問題概要

N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。

まだ友達関係ではない
ブロック関係ではない
友達関係を辿ってたどり着ける
制約\ ...

2020年3月2日AtCoder500点,セグメント木,区間,set,クエリ

問題概要

長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。

S の \(i_q\) 番目を \(c_q\) に変更する
S の \(i_q\) 番目から \(r_q\) 番目ま ...

2020年3月1日数学エラトステネスの篩,素因数分解

素因数分解とは「ある自然数を素数の積の形に分解すること」です。

\(12 = 2^2 × 3\)
\(1024 = 2^{10}\)

1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と ...

2020年3月1日数学最大公約数,競プロ,ユークリッドの互除法,最小公倍数

最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。

最小公倍数は、最大公約数を利用することで簡単に求めることができます。

2 ...

2020年2月29日数学素数,エラトステネスの篩,素数判定

素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。

ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) の計算量になりますが、後述する通り実は \( ...