[C#] 第二回アルゴリズム実技検定PAST A-F(初級)問題振り返り
第二回アルゴリズム実技検定の振り返り記事です。 [C#] 第二回アルゴリズム実技検定PAST A-F(初級)問題振り返り │ Web備忘録 <-このページ [C#] 第二回アルゴリズム実技検定PAST GHI(中級)問題振り返り │ Web備忘録 [C#] 第二回アルゴリズム実技検定PAST JKL(上級)問題振り返り │ Web備忘録 第一回の振り返りは以下の記事にあります。 [C#] A […]
9/46ページ
AtCoder Beginner Contest 166 に C# で参加した記録
AtCoder Beginner Contest 166 に C# で参加した記録 AtCoder Beginner Contest 166 – AtCoder ABC166 にC#で参加しました。結果はABCDEの5問ACでした。 とはいえコンテスト終了間近の滑り込みACだったので、パフォーマンスは1100くらいでレートは微減でした。昨日のコンテストのレートと合わせてちょうど±0でし […]
AtCoder Beginner Contest 165 に C# で参加した記録
AtCoder Beginner Contest 165 に C# で参加した記録 AtCoder Beginner Contest 165 – AtCoder ABC165 にC#で参加しました。結果はABCDの4問ACでした。 開始が10分遅れるという問題がありましたが、レートがつくコンテストになりました。 パフォーマンスは1300くらいでレートは10くらい上がりました。 C問題が […]
[C#] ABC035 D トレジャーハントを解く
ABC035 D – トレジャーハント を解く D: トレジャーハント – AtCoder Beginner Contest 035 | AtCoder ABC035 D – トレジャーハント を C# を使って解いてみます。 この問題は AtCoder Beginner Contest 035 の D問題で、最短経路を求める問題です。問題は以下のようになってい […]
AtCoder Beginner Contest 164 に C# で参加した記録
AtCoder Beginner Contest 164 に C# で参加した記録 AtCoder Beginner Contest 164 – AtCoder ABC164 にC#で参加しました。結果はABCDの4問ACでした。 D問題は過去問で類題というか完全上位互換の問題があったのでそのコードを改変して提出してACしました。 パフォーマンスは1500くらいでレートは30くらい上が […]
AtCoder Beginner Contest 163 に参加した記録
AtCoder Beginner Contest 163 に C# で参加した記録 AtCoder Beginner Contest 163 – AtCoder ABC163 にC#で参加しました。結果はABCEの4問ACでした。 コンテスト自体は Unrated でレート変動はありませんでした。D問題は30分くらい考えても解けなくて、Unratedが確定してたので諦めました。 Dをパ […]
- 2020.04.18
- C#, SparseTable, アルゴリズム, データ構造,
SparseTable の実装と解説 [C#]
Sparse Table とは Sparse Table とは、静的なデータに対して、範囲最小クエリ(RMQ)に答えることができるデータ構造です。 RMQ に答えることができるデータ構造に Segment Tree がありますが、データの変更に対応できるかどうかという点で異なります。Sparse Table はデータの変更はできない代わりに、前計算を行った上でRMQに O(1) で答えることが可能 […]
- 2020.04.16
- C#, SuffixArray, アルゴリズム,
Suffix Array の解説と実装方法[C#][C++]
Suffix Array(接尾辞配列) とは 接尾辞配列 – Wikipedia 接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。 Suffix Array を構築することで文 […]
[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) で行えて計算量の削減につながります。 ローリングハッシュは前 […]