アルゴリズム

1/4ページ
C#

[C#] セグメント木を実装してみる

セグメント木とは セグメント木は名前の通り区間を扱うのが得意なデータ構造です。中身は完全二分木であり、区間の持つデータを管理します。 要素8件からなる配列のデータについて、セグメント木は具体的には以下のような形になります。 各ノードの中の数字は配列の区間データを格納します。 上記のような二分木のデータ構造を使うと、区間に関するクエリ(データの更新、取得)を計算量 O(log N)行えます。 なにが […]

AtCoder Beginner Contest 152 に参加した記録

AtCoder Beginner Contest 152 に参加した記録 2日連続のコンテスト参加でした。結果は残念ながらABCの3問しかACできませんでした。 前回ABCが5問ACしたことを考えると大きな落ち込みです。D問題は解けなければいけなかったです。 とりあえず問題を振り返ります。 A – AC or WA A – AC or WA 高橋君は、プログラミングコンテス […]

C#

[C#] 10進数の桁数とx桁目の数を求める

10進数の桁数を求める C# で10進数の桁数を求める方法をまとめます。一番簡単なのは文字列に変換して Length を参照することですが、ここではそれ以外の方法をまとめます。 0になるまで10で割り続ける方法 0になるまで繰り返し10で割り続けることで求められます。余りは切り捨てます。 例えば12345の桁数を求めるときの計算例です。 12345 / 10 = 1234 1234 / 10 = […]

C#

[C#] ダイクストラ法で最短経路を見つけるための実装方法

ダイクストラ法とは ダイクストラ法 – Wikipedia ダイクストラ法とは、Wikipedia によると次のように説明されます。 ダイクストラ法(だいくすとらほう、英: Dijkstra’s algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。 ある点からの最短経路を求めるときに使用される […]

C#

[C#] ワーシャルフロイドのアルゴリズムに入門する。

ワーシャルフロイドのアルゴリズムについてまとめ、C#で実装してみる記事です。 ワーシャル–フロイド法 とは ワーシャル–フロイド法 – Wikipedia ワーシャル–フロイド法(英: Warshall–Floyd Algorithm)は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。 ワーシャルフロイドは最短経路問題を解くときに使われるアルゴリズムの1 […]

[C#] 最小公倍数(LCM)を求めるアルゴリズムと実装

最小公倍数 – Least Common Multiple 最小公倍数 – Wikipedia 最小公倍数とは、0ではない複数の整数の公倍数のうち最小の自然数をさします。 最小公倍数の求めかた 2つの正整数(a, b)の最小公倍数は、最大公約数が求めれば簡単に求まります。なぜなら最大公約数と最小公倍数には以下のような性質があるためです。 a * b = Gcd(a, b) […]

[C#] ユークリッドの互除法で最大公約数を求める方法

最大公約数を求めるプログラム 2つの自然数の最大公約数を求めるアルゴリズムの1つに、ユーグリッドの互除法 があります。これをプログラムで実装する方法をまとめます。 ユークリッドの互除法とは ユークリッドの互除法 – Wikipedia 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に […]

[C#] bit全探索の使い方と実装、例題を解く

bit全探索の使い方まとめ C# で bit全探索 を実装する方法をまとめます。ちょうど前回の ABC でこれを使う問題に出くわしたので復習もかねてまとめます。 bit全探索を使う場面 C – HonestOrUnkind2 C – Switches 上記のような問題がbit全探索を使える問題です。 ON/OFF, YES/NO, 1/0 のようにbool値で状態を表せるも […]

C#

[C#] ランレングス圧縮(連長圧縮)を実装する方法

C# でランレングス圧縮 連長圧縮 – Wikipedia C# で ランレングス圧縮 を実装してみます。ランレングス圧縮についてはWkipediaを引用すると以下のようなものです。 連長圧縮は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、RLE (Run Length Encoding) とも呼ばれる。 連長圧縮では、ある連続したデータを、そのデータ一つ分 […]

[C#] Union-Find木を実装する方法

Union-Find木 とは 素集合データ構造は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。 Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。 Union: 2つの集合を1つに統合する。 これら2つの操作をサポ […]

1 4