競プロ

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まか ...

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用い ...

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られ ...

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7\) の素数を使用することなどが多いです。

...