深さ優先探索のテンプレート 引数の頂点変数について、大雑把な方針としては 頂点インデックスが不要なとき→頂点の値 vx 陽にグラフを持つとき→頂点インデックス vi 複雑な状態を持つとき→必要な状態全部 状態のオーバーヘッドが大きいときは参照渡しにして…

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

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

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

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

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

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

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

遅延評価セグメント木 (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/…

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

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

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

二次元いもす法 矩形区間加算処理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>…

型 primitive using ll=long long; using ld=long double; using bo=bool; using ch=char; using st=string; using bi=bitset<1>; using ull=unsigned long long; container template<class T>using ve=vector<T>; template<class T>using de=deque<T>; template<class T>using se=set<T>; vector</t></class></t></class></t></class>…

LIB::Imos 区間加算 、区間和取得 、更新処理 https://imoz.jp/algorithms/imos_method.html 累積和の機能を持つので累積和の上位互換として使える。 単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新が出来る。 メンバ関…

graph 深さ優先探索 auto dfs https://9871225.hatenablog.com/entry/2021/11/25/232020 ダイクストラ法（単一始点最短経路） auto dijkstra LIB::Dijkstra 単一始点から全ての終点までの最短経路を求める https://9871225.hatenablog.com/entry/2022/05/22/…

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

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

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

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

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

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

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

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

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

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

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

https://atcoder.jp/contests/arc043/submissions/20924727 初期値は dp[0][0] = ... = dp[0][N-3] = 1 繰り返しは each(i, e, D) rep(j, 1, 4) 漸化式は dp[j].Add(i, dp[j - 1].Sum(0, distance(D.begin(), upper_bound(all(D), e / 2)))) 最終目標は Sum(…

https://atcoder.jp/contests/abc036/submissions/20748614 初期値はall(dp) = 1; 繰り返しは DFS 漸化式は dp[now][B] *= dp[next][W], dp[now][W] *= dp[next][B] + dp[next][W]; 最終目標は dp[0][B] + dp[0][W]; 葉からDPを更新することで根が答えになる…

https://atcoder.jp/contests/agc006/submissions/20609588 中央値なので小中大（x-1, x, x+1）で並べる x, x, y の中央値は x まず、一番上の段がxになるようにしないといけないので真ん中にxを置きたくなる（ぇ 次に、中央値なので x-1, x, x+1 と数字を並…