C#

3/9ページ
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問 […]

C#

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を重ねたことと、勘違 […]

[C#] J – 地ならし [第一回 アルゴリズム実技検定]

第一回 アルゴリズム実技検定 J – 地ならし を解きたい C# で参加した第一回 アルゴリズム実技検定(PAST)は、AからI問題まで解けました。J問題は検定中に解けそうで解けなかった問題なので改めて解いてみました。 [C#] AtCoder 第一回 アルゴリズム実技検定 の振り返り │ Web備忘録 AからIまで上の記事で解いてみたコードがあります。 ではJ問題を解いてみます。コー […]

AtCoder Beginner Contest 159 に参加した記録

AtCoder Beginner Contest 159 に参加した記録 AtCoder Beginner Contest 159 – AtCoder ABC159 に参加しました。結果はABCDの4問ACでした。 今回はD問題が20分しないで解けたので簡単な部類でした。E問題は時間をかけましたが実装しきれませんでした。 前回のAGCに続き、一応レート微増でした。とりあえずWA0でしっ […]

1 3 9