トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート）
トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。
左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。
閉路のないDAGセグメント木を徹底解説！0から遅延評価やモノイドまで
セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。
区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...
[AtCoder] ABC156 E – Roaming (500点)
n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。
ある部屋 \(i\) にいた人が、\(i \neq j\) を満たす任意の部屋 \( ...繰り返し二乗法によるべき乗(pow(x,n))の計算のアルゴリズム
多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数のアルゴリズムです。
Input : pow(2,4) (x=2, n=4)
Output : 16
べき乗は非常に大きな数値に ...
ビットDP(bit DP)の考え方 ~集合に対する動的計画法~
競技プログラミングで良く使われる動的計画法の1種、「ビットDP」と呼ばれるものについてまとめました。
ビットDPとはビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 ...
[AtCoder] ABC023 D – 射撃王
問題へのリンク
風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のとこ ...
競技プログラミングで解法を思いつくための典型的な考え方
競技プログラミングの問題を解くためには２つのステップがあります。
問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く
必要な（知っておくべき）アルゴリズムやデータ構造は色 ...
[AtCoder] ABC155 D – Pairs (400点)
ARC037 億マス計算 の上位問題です。
問題概要問題へのリンク
N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。
2つを選んでその積を \(\frac{N(N-1) ...
[AtCoder] ABC155 E – Payment (500点)
問題へのリンク
問題概要\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。
N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の ...
グラフにおける橋(bridge)を検出するアルゴリズム
無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。
※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。（くわしくはグラフ ...