自分用のメモです。

WAの時に確認すべきこと

  • 問題文は正しく読めているか？
  • オーバーフローしていないか？
  • 998244353や10^9+7で割った余りを求めるタイプの場合、余りを取っているか？ 負の値を足している時、res = (res % P + P) % Pのようなケアをしているか？
  • 二分探索をしている時、最小値、最大値に到達できるか？

探索

DFS

木を辿る

BFS

Bit全探索

DP

1次元

2次元

桁DP

タイリング/敷き詰め

ナップザック問題

ぐるぐる遷移していくやつ

区間スケジュール問題

数列/整数

約数

素数

フィボナッチ数列/漸化式

行列演算

数列の連続する項目の差の絶対値に注目

幾何

三角形

円の交点

凸性

外積で判定できる

グラフ

二部グラフ判定

DFS

ダイクストラ

ワーシャルフロイド

橋

閉路

LCA

蟻本 pp.292

\(d(u,v)=depth(u)+depth(v)-2depth(lca(u,v))\)

セグメント木

Fenwick Tree

通常のセグメント木

区間和

その他

座標圧縮

括弧

マンハッタン距離

45度回転が有用。

チェスのナイト

斜めに動くとわかりづらいので、座標変換を行う。 $$ \begin{aligned} \left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} 1 & 2 \\ 2 & 1 \end{matrix} \right) \left( \begin{matrix} s \\ t \end{matrix} \right) \end{aligned} $$ だから、逆変換 $$ \begin{aligned} \left( \begin{matrix} s \\ t \end{matrix} \right) = -\frac{1}{3} \left( \begin{matrix} 1 & -2 \\ -2 & 1 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) \end{aligned} $$ を考えることにより縦横の単純な移動に変換する。