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) で行えて計算量の削減につながります。 ローリングハッシュは前 […]
AtCoder Beginner Contest 162 に参加した記録
AtCoder Beginner Contest 162 に C# で参加した記録 AtCoder Beginner Contest 162 – AtCoder ABC162 にC#で参加しました。結果はABCDの4問ACでした。今回から新ジャッジ環境でのコンテストになり、使用可能言語のバージョンアップが行われています。 コンテスト中にジャッジが詰まることもありましたが、無事レートが更 […]
AtCoder Beginner Contest 161 に C# で参加した記録
AtCoder Beginner Contest 161 に C# で参加した記録 AtCoder Beginner Contest 161 – AtCoder ABC161 にC#で参加しました。結果はABCDの滑り込みで4問ACでした。 パフォーマンスは残念な緑になって、レートは減少しました。次回も同じようなパフォーマンスだと水色から陥落します。敗因はC問題の数学アレルギーと、D問 […]
C# で Deque(両端キュー)を実装してみる
C# で Deque(両端キュー)を実装してみる 両端キュー – Wikipedia C# で Deque(両端キュー) を実装してみます。両端キューは以下の4つの操作が高速に行えるデータ構造のことです。 先頭に要素を挿入 先頭の要素を削除 末尾に要素を挿入 末尾の要素を削除 C# には標準ライブラリで LinkedList<T>(連結リスト) が用意されており、このデータ […]
AtCoder Beginner Contest 160 に参加した記録
AtCoder Beginner Contest 160 に C# で参加した記録 AtCoder Beginner Contest 160 – AtCoder ABC160 に参加しました。結果はABCDEの5問ACでした。 E問題が普段より易しく感じたのは数学チックな問題ではなかったからかもしれません。 E問題まで解けたのはよかったのですが、D問題で不用意なWAを重ねたことと、勘違 […]