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)\) の計算量になりますが、後述する通り実は \( ...

2020年2月28日グラフグラフ, 有向グラフ, DAG, トポロジカルソート, BFS, DFS

トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。

左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。

閉路のないDAG ...

2020年2月27日データ構造二分探索, セグメント木, 二分木, 完全二分木, 区間, モノイド, 更新, RMQ, RUQ, データ構造, RAQ, RSQ

セグメント木とは

セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...

2020年2月24日AtCoder剰余, 二項係数, 操作, 数え上げ, 500点, 重複組合せ

問題概要

n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。

ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...

2020年2月24日数学bit演算, 剰余, 競プロ, べき乗, ダブリング, 繰り返し二乗法, 2進数

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。

Input : pow(2,4) (x=2, n=4)
Output : 16

べき乗は非常に大きな数値に ...

2020年2月22日動的計画法bit演算, 動的計画法, bitDP, DP, テーマ記事, 競プロ

競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。

ビットDPとは

ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...

2020年2月20日AtCoder最大値, 二分探索, 最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のとこ ...

2020年2月20日競技プログラミングテーマ記事, 競プロ

競技プログラミングの問題を解くためには2つのステップがあります。

問題で要求されていることを言い換える
知っているアルゴリズムやデータ構造を組み合わせて解く

必要な(知っておくべき)アルゴリズムやデータ構造は色 ...