競プロ

貪欲

deque

スタック

キュー

BFS

DFS

Bit全探索

DP

累積和

二次元累積和

尺取法

二分探索

Union-Find

ソート

ダイクストラ

ベルマンフォード

ワーシャルフロイド

最小全域木

PQ

二分探索

セグ木

最大流

スター型グラフ

二次元座標を二部グラフにする(ABC 131 F)

dpはとりあえず立式したほうがいい

Dpは解けなそうで何でも解けるので、亜種dpを徹底的に試すと良い

ダブリング

45℃回転

imos法

調和級数で計算量落ちないか

番兵

BIT

bitset

平面走査 = x軸(もしくはy軸)でソートして小さい順に見ていくヤツ

偏角ソート → atanの扱い方に注意

複素数平面(ABC197D) → とにかく回転に強いので, 回転なら複素数

座標平面を回転させる (ABC139 F)

マージテク

再帰

判定問題は論理式に直すといい → ∀ 等

牛ゲー → 不等式の制約がいっぱいある時に使える

場合分け (ARC 107 D)

計算量を√Nに落とす (ARC 60 D)

文字列群を連結して辞書順最小にする → 「x < y ⇔ x + y < y + x」

ロリハ → 任意の区間のハッシュをO(1)で取得可能

割ったり余りを計算したりするなら M進数

HL分解 → 根方向に戻る時に逆元がないなら、オイラーツアーじゃなくてHL分解

オイラーツアー → 辺verの場合は辺パス / 頂点verの場合は部分木系

行列 → アフィン変換風にダミーの次元を作ると、加算も表現できる(同次座標系)

行列累乗 = 遷移の係数がiに依存しないDPはコレ。 特に二項間の場合は、ダミー次元があると良い(ARC 20 C)

「連結成分の個数 = 頂点数 - 辺の数」(グラフが森ならば)

A + B = (A xor B) + 2(A ∧ B)

操作をグラフに落とし込んでみる (JOI 2020/2021 第２問)

クエリ平方分割 → ブロックの出入り / ブロック内の処理　を意識すると良い

巡回シフトは２周期分で考える (ABC 150 F / maspy解説)

Kの倍数 -> mod Kのグラフで考える。(ARC 84 D)

全ての整数は1に対して + 1か x10 の操作を繰り返すことで作れる(ARC 84 D)

マンハッタン距離が最小となる点は、例の中央値問題に帰着される

中国剰余定理 = CRT

「3 で割ったあまりが 2 で、5 で割ったあまりが 3 になるような 1 以上 100 以下の整数をすべて求めよ」的なやつ

自明なケースを除けば不等式が作れて有利に働くことがある (AGC 026 B)

区間がソート済みかどうかはO(1)で確認できる → AGC038 Bの自分のコード参照

区間問題 → 左端ソートするとうまくいくことがある

期待値の線形性

最長路問題 → DAGならトポロジカルソートすれば線形に解ける (D - Restore the Tree)

トポロジカルソート (辺の見方: ソート済みの頂点集合を前から順に見ていけばg.get_edgesで辺取れる)

部分文字列問題は基本的にはO(N)で解けるみたい (けんちょん参照: next~ みたいなの使うやつ)

接続行列(opt参照)に対してEに関する操作をすれば(=xをかける)、頂点に関する特徴ベクトルが取れる

クソデカセグ木 → ノードのサイズを恣意的に取れば座圧で対応できる (ARC 115 E)

セグ木でindexがほしい → セグ木に載せたデータとindexを紐付けたpairlを用意すれば良い(それか1e9*iを足しておいて, セグ木内処理のときに逐一1e9を消したり増やしたりするか)

osak法 高速素因数分解

マージテク(小→大 で O(log n))

木の直径

MaxFlow

MinCostFlow → 流量だけでなくコストを設定して、コストの最小値を計算できる

同じ遷移のdpは行列累乗

スライド最小値

OEISで検索！

01の場合、a xor b = a(1-b) + b(1-a)

超頂点

Lucasの定理 → 素数modでcombをO(logN)でできる

popcount

二部グラフ判定はUnionFind(noshi参照)か DFS(始点の色を決めてDFSすれば良い)

パリティ(偶奇)を考える

最小値の最大化は二分探索 → 数直線・論理式に展開してみると意味がわかる.

XORで任意の値が作れる → その集合を行列で表現した時, 行基本変形で単位行列的な感じになるか → 基底のサイズがnかどうか → XORの掃き出し法(noshi基底)

区間 → しゃくとり法

積の和 ΣΠ → FPS・約数

無理やり場合分け(桁DP・ARC)

木の最短パス → オイラーツアー

集合zに対しx⊆y⊆zな組(x,y)はちょうど3^z個( 4^zが3^zになるやつ)

連続する自然数の構築問題 → ２進数的にやる (+1 or x 2で全ての整数は表せる)

Gcdのカウントは前から順にやれば良い

区間内の[x,y)を満たす値の出現数 ⇒ Wavelet Matrix (区間内xの出現数だけなら, 普通にposを持てばOK / ABC 202)

解を成長させる.(ルンルン数, AGC013B, ARC118)

LISはin-placeに出来る

SCCしたあと, 強連結成分自体を頂点としたグラフを作成する. (典型59)

Nと互いな素な数の個数はオイラー関数 でO(√n))

約数の個数は少ない (1e9以下で最大1333個くらい)

→ 素因数の種類数はもっと少ない (1e5以下で高々6個 → bit全探索 + 包除原理があるある)

互いに素な組を探す → 素因数の組み合わせの積 mul に対して, mul, 2mul, 3mul, …　という数列から, 包除原理を用いてgcd = 1(一つも素因数にかぶりが無い)であるものを出す

→ 集合を場合分けして再帰にもちこむ

愚直に考える

マッチング問題 → ホールの定理(結婚定理)

貪欲 → 損するかどうか

Baby-step Giant-step → 離散対数問題: A^x ≡ B (mod M) を満たす最小のx

座標の90度回転→ (x,y)->(y,-x) (回転行列)

座標の平行移動→左角からの相対座標を考えれば平行移動を考えなくて済む(ABC218)

領域に穴がない→空白部分が連結かどうかで判定 (ABC219 E)

永続配列

頂点倍加→ノード=状態なので, 如何に好ましい状態を設定してあげるか (ABC277E)

場合分けが多い場合は、片方を正に固定するなど、場合分けを減らせないか？

osak法

素因数分解した際の最小の素数を保存する→エラトステネスの篩と同じ要領で，各xをiterateして，2x, 3x, 4x ... のspfをxとして記憶．targetをspfで順に割っていけば高速で素因数分解できる

木の最長パスの探し方

indegreeが0のノードから最長のノードを探して，次はそのノードからスタートして再び最長のノードを探す

有向グラフのループ検出はトポロジカルソート

ただしBFSで実装すること．DFSだとループが存在しても一通り巡回してしまう

memo

ギリギリオーバーフローしそうになったら__int128 を使う

OEISでエスパーするときは「第3項目あたりから5,6項を入れて検索する」と良い

期待値問題

1. 後ろから前にいくにつれて回数は増えるので、Aから生えてる(Aの次の)状態に対して、それらすべての遷移に確率を掛けてあげて足してあげる (必ず終了条件を始点として後退解析する)

→「今 = Σ (確率)*(次の期待値 + 1)」

2. 期待値は独立であろうがなかろうが、線型性が成り立つ

3. 状態遷移図を書く。特に、自分に戻ってくる遷移を忘れない！

回数の期待値

dp(i) := 回数の期待値 とすると, 普通にdp(i)を「回数と同じものと考えて良い」

回数 x 確率 = 期待値なので, 期待値 x 確率 = 期待値

dp(i) -> dp(i-2) (確率p)

dp(i) -> dp(i-1) (確率q)

とすると, dp(i) = (dp(i-2) + 1) x p + (dp(i-1) + 1) x q

回数 x 確率 = 期待値なので, 期待値 x 確率 = 期待値

回数が一回増えるので+1

これがΣ (確率)*(次の期待値 + 1)

dp(i-2):

○ dp(i) <- dp(max(0,i-2))

☓ if (i >= 2) dp(i) <- dp(i-2)

こっちだと, dp(0)からの遷移が効かない

DP

戻すDP → いくつか要素を抜くDPに使える

両側からDP → いくつか要素を抜くDPに使える

区間DP

LCS系DP → 文字列系に使える (二次元ナップサックというらしい)

bit DP

ダブリング

In-place DP

部分和DP → bitsetで高速化できる

桁DP → 1. 普通に桁DP, 2. maspy式の桁DP(1の桁で場合分け → 再帰)

DPは場合分けの構造である→ 場合分け軸を固定して考えると良い (ARC107 D) →何を軸に場合分けするかを決め打つ (0で場合分けするとか、1の位で場合分けとか)

行列累乗

巡回セールスマン → 始点はなんでもいいらしい (algo-logic参照)

辞書順に復元するなら、後ろからDPをする

区間DPと両側からDPは違う！ → 区間DPはまず最初に幅を決めて, 次に左端を決める(典型019)

dp(i) := iは使うものとして〇〇という形式が多い

文字列

置換する問題 → 操作が可逆かどうか / 対称性があるか を見ると良い

変換可能か問題 → 返還前後で不変な値は何か？ それを用いて、返還前後での値を比べる 「Greedyからの帰着」ってやつ

操作後の状態をある程度まとめることができないか実験する (操作後、すでに見たことある状態が存在しないか？

操作系

操作を何かしらで特徴づけて、それをdpなりグラフなりで解く

→ ARC 109 D / JOI 20/21 2 /

操作の逆元・同値類(もとに戻るやつ)を探す

不変量を見る

確率・期待値

確率 p で成功する試行を、成功するまで行うときの試行回数(最後の成功した回も含む) の期待値は 1/p

→ ABC 194 D

数列問題

隣接項の差を取る

列の操作は区間DP

グラフにする

しゃくとり

ゲーム

状態をすべてグラフにすると、後ろから最適なスコアが自ずと導かれる(後退解析) → 自分に不利な手番は放棄していけば、枝刈り的な状態になってdpになる

Grundy数が何らかの性質から求まらないかを考える

スパースな多項式ならmod取らないでもできる(ABC200 E)・負の二項定理

→ 例えば(1-x^n) / (1-x) の形で表されても, ちゃんと割り算できるヨ

クソデカセグ木 → ノードのサイズを恣意的に取れば座圧で対応できる (ARC 115 E)

↓

https://gyazo.com/adcd71e119c0ac1f5cbbc6f6f388ac38

https://gyazo.com/a9970d3b786b80f2c9db47b13625ea62

思考の言語化

演算子を考える

対象を変える

計算量が多くても解法を一つ作ってみる

なるだけ図とイメージを使って糸口を掴む→解法を数式に起こす→アルゴリズムを検証する→実装

解法ガチャ

知らないテクなどは大抵問題に出ないので, 解けると思いこんで解く

ボソボソつぶやきながらやるとよい

具体的な実装の絵を考えながら紙を見ると良い

とりあえず立式したり, とりあえず変数に置いてみたり

手数が重要

「数学は言い換えの学問」と同じように、無限に「言い換え」していく

→ 言語性

単純に競プロに対する興味が薄れてる

解けないから？向上心がなくなったから？反骨精神が無いから？

手も足も出ないときにやる気なくなる

とりあえず何でも良いから書き出して手数を増やそうとしてみる

競技性を忘れ、ゆっくり考えてみる

https://gyazo.com/ec9d840e2f2857ee37a8e18fdd1ccd18

Cpp思い出し (完全にC++忘れてるので)

umap<A,B>はAにpairlを使えない

代わりにmapは使えるけど計算量がかかる

umapのイテレーションは for (auto [] k,v ] : x)

存在判定は(x.find(y) == x.end())

pairlはsort(ALL(x))で先頭の数字に対してソートしてくれる

dpはdp(i)→「iまでみて」が肝要

使う or 使わないの選択なので

chmin(dp(i+1)(j)(k),dp(i)(j)(k))が必要なときアリ