2/38ページ

2/38ページ

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をパ […]

SparseTable の実装と解説 [C#]

Sparse Table とは Sparse Table とは、静的なデータに対して、範囲最小クエリ(RMQ)に答えることができるデータ構造です。 RMQ に答えることができるデータ構造に Segment Tree がありますが、データの変更に対応できるかどうかという点で異なります。Sparse Table はデータの変更はできない代わりに、前計算を行った上でRMQに O(1) で答えることが可能 […]

Suffix Array の解説と実装方法[C#][C++]

Suffix Array(接尾辞配列) とは 接尾辞配列 – Wikipedia 接尾辞配列(せつびじはいれつ)やサフィックス・アレイ(英: suffix array)とは、文字列の接尾辞(開始位置を異にし終端位置を元の文字列と同じくする部分文字列)の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。 Suffix Array を構築することで文 […]

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 […]

C#

[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でした。今回から新ジャッジ環境でのコンテストになり、使用可能言語のバージョンアップが行われています。 コンテスト中にジャッジが詰まることもありましたが、無事レートが更 […]

[C#] 第一回 アルゴリズム実技検定 K – 巨大企業

[C#] 第一回 アルゴリズム実技検定 K – 巨大企業 を解きたい C# で参加した第一回 アルゴリズム実技検定(PAST)は、AからI問題まで解けました。第二回も参加するので予習がてら解いてない過去問を解いてみます。今回は第一回のK問題を解きます。 [C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録 [C#] J – 地ならし [第一回 アルゴリズ […]

Judge System Update Test Contest 202004 に C# で参加した記録

Judge System Update Test Contest 202004 Judge System Update Test Contest 202004 – AtCoder AtCoderのジャッジ環境更新負荷テストのコンテストに参加したので記録しておきます。 今回のコンテストはジャッジ環境更新に伴う負荷テストが目的のため Unrated です。成功しても失敗してもレートは変動し […]

AtCoder Beginner Contest 161 に C# で参加した記録

AtCoder Beginner Contest 161 に C# で参加した記録 AtCoder Beginner Contest 161 – AtCoder ABC161 にC#で参加しました。結果はABCDの滑り込みで4問ACでした。 パフォーマンスは残念な緑になって、レートは減少しました。次回も同じようなパフォーマンスだと水色から陥落します。敗因はC問題の数学アレルギーと、D問 […]

1 2 38