7K12B blog

猫でも分かる何か

2021-07-01から1ヶ月間の記事一覧

LIB::AhriSet

欲張りマルチセット multiset に標準コンテナの頻出関数を全部実装した欲張りデータ構造 色々なコンテナを使い分けて処理する操作毎に関数名を使い分けるのが面倒な人にオススメ(適当) 内部に unordered_map を持つことで count(x) を定数時間に高速化する…

AGC016 B - Colorful Hats

の種類数が2個以下でないとNoというのは自明なので の種類数を基準に場合分け 条件が多く大変だがサンプルが豊富なので、ある程度サンプルから条件を整理できる https://atcoder.jp/contests/agc016/submissions/24577904自分と同じ色が存在しない猫を「uniq…

NyaaLIB::DS_LazySegmentTree

遅延評価セグメント木 (Lazy Segment Tree) 任意区間のクエリを計算量 で処理するhttps://betrue12.hateblo.jp/entry/2020/09/22/194541 https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html https://betrue12.hateblo.jp/entry/…

ARC017 C - 無駄なものが嫌いな人

N=32 は半分全列挙 https://atcoder.jp/contests/arc017/submissions/24169529ナップサック問題っぽい文章なのでナップサックDPではないと予想する(ぇ そもそも X が なので DP で処理するのは無理と分かる。 ここで N が 32 しかないことから半分全列挙し…

NyaaLIB::DS_NyaaBIT

BIT (Binary Indexed Tree) 要素加算 、区間総和取得 https://atcoder.github.io/ac-library/production/document_ja/fenwicktree.html Fenwick Tree とも呼ばれる。遅延セグ木の下位互換だが、遅延セグ木に比べて定数倍高速に動作する。 namespace NyaaLIB …

ABC132 E - Hopscotch Addict

頂点を増やすことでmodの遷移を判定する https://atcoder.jp/contests/abc132/submissions/24017041 愚直な考察をすると頂点に移動回数のmod情報を持たせたくなるが、実装が複雑で難しいので逆転の発想をする。具体的には頂点を増やすことで、modの情報を持…