[C#] エラトステネスの篩で素数列挙と素因数分解を実装する
エラトステネスの篩とは エラトステネスの篩 – Wikipedia エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。 指定された整数N以下の素数を列挙できるアルゴリズム、エラトステネスの篩 […]
C#
[C#] 繰り返し二乗法で n^p % mod を拘束に求める
繰り返し二乗法とは Np を高速に計算する方法です。NもPも109くらいあるときに、NをP回かけ合わせると計算量 O(N) かかりますが、繰り返し二乗法を使えば O(logN) で実現できます。 Pが偶数のとき 例えばPが偶数(P=2k)の時、 N2k = Nk * Nk となるので、Nkが計算できればそれを2乗するだけでよくなります。 具体的な例で、P=8の時には N8 = N4 * N4 N4 […]
- 2020.04.13
- C#, RollingHash, アルゴリズム,
[C#] ローリングハッシュを実装する
ローリングハッシュとは ローリングハッシュは文字列検索等に使われるアルゴリズムです。 ローリングハッシュを使うとある文字列Sのすべての部分文字列のハッシュ値を O(1) で返すことができるようになります。ローリングハッシュで得られるハッシュ値を使って文字列の比較を行うことで、通常比較する文字列の長さ分の計算量がかかる比較処理が O(1) で行えて計算量の削減につながります。 ローリングハッシュは前 […]
C# で Deque(両端キュー)を実装してみる
C# で Deque(両端キュー)を実装してみる 両端キュー – Wikipedia C# で Deque(両端キュー) を実装してみます。両端キューは以下の4つの操作が高速に行えるデータ構造のことです。 先頭に要素を挿入 先頭の要素を削除 末尾に要素を挿入 末尾の要素を削除 C# には標準ライブラリで LinkedList<T>(連結リスト) が用意されており、このデータ […]
[C#] セグメント木を実装してみる
セグメント木とは セグメント木は名前の通り区間を扱うのが得意なデータ構造です。中身は完全二分木であり、区間の持つデータを管理します。 要素8件からなる配列のデータについて、セグメント木は具体的には以下のような形になります。 各ノードの中の数字は配列の区間データを格納します。 上記のような二分木のデータ構造を使うと、区間に関するクエリ(データの更新、取得)を計算量 O(log N)行えます。 なにが […]
[C#] 10進数の桁数とx桁目の数を求める
10進数の桁数を求める C# で10進数の桁数を求める方法をまとめます。一番簡単なのは文字列に変換して Length を参照することですが、ここではそれ以外の方法をまとめます。 0になるまで10で割り続ける方法 0になるまで繰り返し10で割り続けることで求められます。余りは切り捨てます。 例えば12345の桁数を求めるときの計算例です。 12345 / 10 = 1234 1234 / 10 = […]
[C#] ダイクストラ法で最短経路を見つけるための実装方法
ダイクストラ法とは ダイクストラ法 – Wikipedia ダイクストラ法とは、Wikipedia によると次のように説明されます。 ダイクストラ法（だいくすとらほう、英: Dijkstra’s algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 ある点からの最短経路を求めるときに使用される […]
[C#] ワーシャルフロイドのアルゴリズムに入門する。
ワーシャルフロイドのアルゴリズムについてまとめ、C#で実装してみる記事です。 ワーシャル–フロイド法 とは ワーシャル–フロイド法 – Wikipedia ワーシャル–フロイド法（英: Warshall–Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。 ワーシャルフロイドは最短経路問題を解くときに使われるアルゴリズムの1 […]
[C#] 三井住友信託銀行プログラミングコンテスト2019 の記録
[C#] 三井住友信託銀行プログラミングコンテスト2019 の記録 三井住友信託銀行プログラミングコンテスト2019 – AtCoder 三井住友信託銀行プログラミングコンテスト2019 に参加したのでその記録です。 AtCoder Beginner Contest (ABC) 相当の難易度のコンテストです。 結果は ABCD の4問解けて、Eは解けそうで解けませんでした。以下コンテス […]
[C#] 順列を求める next_permutation() 代わりを実装する方法
C# で順列を求めたい next_permutation – cpprefjp C++日本語リファレンス C++ には next_permutation という順列を生成する関数が用意されています。これに似た関数を C# でもほしいので実装してみます。 next_permutation() まずは next_permutation() がどんな関数か見てみます。 例えば [1, 2, […]