7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB::NT_ModINT

MOD 型ライブラリ #include <bits/stdc++.h> namespace NyaaLIB { /** * MOD 型ライブラリ **/ template <long long mod> struct NT_ModINT { // 非型テンプレートパラメータ using mint = NT_ModINT; using ll = long long; ll x; NT_ModINT() : x(0) {} NT_ModINT(ll init) : x(init% mod</long></bits/stdc++.h>…

NyaaLIB_GTL

グラフライブラリまとめ DFS auto dfs = [&](auto self, wgraph& g, ll now, ll root) -> void g: 重み付き隣接リスト now: 今みている頂点 root: 頂点nowに対する根(DFS1回目の呼び出しでは-1を指定するのが典型) #include <bits/stdc++.h> namespace NyaaLIB_GTL { name</bits/stdc++.h>…

ABC025C - 双子と○×ゲーム

ゲーム系の最善手は逆算 木のDFSだが「間違えて元の局面に戻る」ようなDFSが絶対に発生しないので根への遷移かどうかのチェックは不要 問題文を誤読しないよう注意、直大さんのスコアは「マス[i][j] = o かつ マス[i][j] = マス[i+1][j]」でなく単純に「マス…

NyaaLIB::GT_NyaaLCA

LCAライブラリ 木の最近共通祖先 (Lowest Common Ancestor) 前処理 することで以下のクエリに で答える Ancestor(x, y): 木頂点 (x, y) に対する最近共通祖先 Dist(x, y): 全頂点対間距離(任意の2頂点 (x, y) 間の距離) IsOnPath(x, y, z): x-y パス上に頂…

SoundHound Inc. Programming Contest 2018 D - Saving Snuuk

選択肢の少ない状態から考察すると楽 後ろから考えると値を流用できる https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/25168114 0日目から考えると全ての都市で両替できるので最善を考えるのが大変だが n-1 日目なら選択肢は1通りしか…

STL一覧

メタ構文変数 int nyaa = 0; // piyo は古い インデックスの計算(配列のサイズは 1-index) インデックスの引き算 インデックスの足し算 値を範囲に収める #include <bits/stdc++.h> int main() { long long x = -15; x = std::clamp(x, 0ll, LLONG_MAX); std::cout << x <</bits/stdc++.h>…

ABC210 E - Ring MST

https://atcoder.jp/contests/abc210/submissions/24941318最小全域木にクラスカル法というアルゴリズムがある。クラスカル法は「全ての頂点が連結になるまでコスト昇順に辺を選択してく」アルゴリズムだが、頂点と辺の数が多いため愚直にクラスカル法は使え…

典型一覧

DFS https://atcoder.jp/contests/abc236/tasks/abc236_d diff1190 https://atcoder.jp/contests/abc220/tasks/abc220_f diff1304 https://atcoder.jp/contests/abc222/tasks/abc222_e diff1491 BFS https://atcoder.jp/contests/abc224/tasks/abc224_d diff…

AGC017 B - Moderate Differences

足し算と引き算は順序関係ないので足し算と引き算の回数に着目して探索できる https://atcoder.jp/contests/agc017/submissions/24762083ABCD が なので N の線形処理と予想する。例えば A=10 で C=1, D=5 のとき+すると区間 [11, 15] まで表現できる。更に…

NyaaLIB::DS_AhriSet

欲張りマルチセット https://www.google.com/search?q=gwen+lol&source=lnms&tbm=isch multiset に標準コンテナの頻出関数を全部実装した欲張りデータ構造 色々なコンテナを使い分けて処理する操作毎に関数名を使い分けるのが面倒な人にオススメ(適当) 内…

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の情報を持…

NyaaLIB::DS_NyaaImos2D

二次元いもす法 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) #include <bits/stdc++.h> namespace NyaaLIB { /** * 二次元いもす法 * 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) **/ template <class T = int64_t> struct DS_NyaaImos2D { int64_t ys</class></bits/stdc++.h>…

マクロ一覧

#include <bits/stdc++.h> #include <bits/stdc++.h> using namespace std; //#include <atcoder/all> //using namespace atcoder; //#define BOOST #ifdef BOOST #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/integer/extended_euclidean.hpp> using …</boost/integer/extended_euclidean.hpp></boost/multiprecision/cpp_dec_float.hpp></boost/multiprecision/cpp_int.hpp></atcoder/all></bits/stdc++.h></bits/stdc++.h>

NyaaLIB::DS_NyaaImos

いもす法 区間加算 、区間総和取得 、更新処理 https://imoz.jp/algorithms/imos_method.html 累積和の機能を追加することで累積和の上位互換としても使える。 単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新も可能。 #…

ライブラリ一覧

ラムダ式ライブラリ NyaaLIB_NTL (NTライブラリまとめ) 素数判定 (IsPrime)、素数列挙 (PrimeTable) https://9871225.hatenablog.com/entry/2022/05/12/145950 NyaaLIB_GTL (GTライブラリまとめ) DFS https://9871225.hatenablog.com/entry/2021/11/25/2…

AGC018 B - Sports Festival

https://atcoder.jp/contests/agc018/submissions/23809861 最大の状態から減らすには何を減らせばよいか考える 最大の状態から始めて小さくするには「最大の要素を取り除くしかない」という貪欲 数字を変化させるには「少なくとも貪欲するしかない」なら貪…

ZONE2021 E - 潜入

https://atcoder.jp/contests/zone2021/submissions/23283470 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能 コストを増やしたい→階層化して辺を追加すれば再現可能 上下左右1マス移動しかないなら単純にダイクストラ法をするだけ…

ABC203 D - Pond

https://atcoder.jp/contests/abc203/submissions/23082310 小さい数を-1、大きい数を+1、としてカウントすると線形処理で中央値かどうか判別可能 中央値を求めるデータ構造として2個の priority_queue を持つ のアルゴリズムがあり、スライドウィンドウして…

ABC165 E - Rotation Matching

https://atcoder.jp/contests/abc165/submissions/22916768 回転するので生徒を円状に配置して考察する 向かい合った頂点に辺を貼ると距離が異なるので被りづらくなる 偶奇で場合分け サンプル2がヒントであり、生徒を並べたとき距離の異なる数字同士でペア…

DDCC2020 D - Digit Sum Replace

https://atcoder.jp/contests/ddcc2020-qual/submissions/22659513 少なくとも(桁数-1)回だけ桁を減らす必要がある 桁は減らないが数字が小さくなる変換もある、条件は2桁の数字 について 適当にシミュレーションしてみると、2桁の数字が小さいとき桁が下…

ABC065 D - Built?

https://atcoder.jp/contests/abc065/submissions/22580754 本当に本の辺を全て試す必要があるか疑うこと 最小全域木なのでクラスカル法ライブラリを貼りたいが、設問そのままグラフを処理しようとするとで間に合わない。街1と繋がるべき街は2と3、街4と繋が…

AGC038 B - Sorting a Segment

https://atcoder.jp/contests/agc038/submissions/22099887 区間の組み合わせが線形という希望的観測をする まず、区間[l,r]と区間[l+3,r+3]のように被っている2区間を各々ソートした結果が等しくなる条件を考えると、互いに被っていない部分にある数が動か…

AGC007 B - Construct Sequences

https://atcoder.jp/contests/agc007/submissions/21896735 の公式が成り立つ理由 結論から言うと が答えになる。 に比べて の制約が非常に緩いことから、ある程度の余裕を持たせて昇順数列 a を考えたほうが良いのかな、という気持ちになる。 公式のように…

Code Formula 2014 C - 決勝進出者

https://atcoder.jp/contests/code-formula-2014-quala/submissions/21743681 で二次元データに順位を付ける 昔は日本語読解が困難な問題も多く、問題文の意味を理解するのが難しいが…一番簡単なテストケースとして重複が一切ない場合は左図のように a[i][j]…

ABC195 E - Lucky 7 Battle

https://atcoder.jp/contests/abc195/submissions/21508217 初期値は dp[N][0]=1 繰り返しは repr(i, N - 1, -1) rep(j, 0, 7) 更新は if (X[i] == 'T') dp[i][j] = dp[i + 1][j] || dp[i + 1][(j + CtoL(S[i]) * NT_NyaaMod::Pow(10, N - 1 - i, 7)) % 7]; …

ABC173 E - Multiplication 4

https://atcoder.jp/contests/abc173/submissions/21143239 K個選んだときの積が負なら「負を1つ減らして正を1つ増やす」「正を1つ減らして負を1つ増やす」両方を試す必要がある 積を最大化するため、絶対値降順に貪欲にK個だけ選ぶ(実際に計算するとオーバ…