2020-01-01から1年間の記事一覧
概要 逆元が必ずしもない状況で行列式を計算する方法を紹介します 一般の可換環上の行列式 n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub 除算を使わない のシンプルなアルゴリズムが知られています。 除算無しでも にな…
Poyashi で参加して 6 完 4 位でした 開始前 リハーサル参加のためかなり早めに来たが、模擬に参加してるのでほとんど練習の必要がないことに気付く。 ライブラリを書きながら開始を待つ。 コンテスト開始後 記憶がかなり曖昧なので間違ってるかも。 A moyas…
長さ 同士の列を畳み込むのが でできるやつ 時間計算量 備考 , 高速フーリエ変換 環, Schönhage–Strassen 環, 高速ゼータ変換, メビウス変換 環, 高速ゼータ変換, メビウス変換 環, 2 で割れる, 高速アダマール変換 環, subset convolution 環, 高速ゼータ変…
概要 Range Mode Query - data-structures これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。 アルゴリズム まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも…
概要 部分永続 Union Find のアルゴリズムの変種を考えました 注意: 実測では使い物にならない気がします 空間計算量 - 単一の要素からなる集合 個で初期化する 時間計算量 - と が属する集合を併合する 時間計算量 - 回目に が呼ばれた直後に が属していた…
概要 SegmentTree などのように、代数的構造 (特にモノイド) を乗せるデータ構造は多い。 この部分の設計は様々だが、「静的メンバを実装した型を受け取る」設計を他の設計と比較する。 設計のバリエーション A: std::function で関数オブジェクトを持つ tem…
注意: この記事は非公式です。また、情報の正確性や取捨選択について著者は一切の保証をしません。 概要 コンテスト関係で重要と思われる情報を抜粋、要約しました。 雑談などの情報は省略、あるいは大筋のみになっています。 まとめ AtCoderの公式生放送「…
注意: この記事は非公式です。また、情報の正確性や取捨選択について著者は一切の保証をしません。 概要 コンテスト関係で重要と思われる情報を抜粋、要約しました。 雑談などの情報は省略、あるいは大筋のみになっています。 まとめ AtCoderの公式生放送「…
概要 オムライスを作り、食べた オムライス 作り方 みじん切りにした玉ねぎを炒める 鶏もも肉を加えて炒める ケチャップを加えて炒める 炊いた白米を加えて炒める チキンライス完成 卵を焼く チキンライスの上に乗せる オムライス完成 食べる 結果 おいしい …
概要 到達当時の記録 AtCoder AtCoder Performances AtCoder Problems AtCoder Scores ライブラリ Library | This documentation is automatically generated by online-judge-verify-helper
概要 競プロ用の C++ ライブラリを作るための struct の使い方を説明する メンバ変数 struct を使うと、std::pair<int, int> と似たようなものを作ることが出来ます。 #include <iostream> struct t { int a; int b; }; int main() { t x; x.a = 1; x.b = 2; std::cout << x.a <<</iostream></int,>…
随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Tr…
A - Uncommon これを として時間計算量 で解きます。 畳み込み ゼータ変換・メビウス変換を理解する - Qiita 添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ 添え字の での畳み込みをおおまかに理解しているとします。 は行列 を用いて と表現…