素数かどうかを判定するアルゴリズム

素数とは 「1 より大きい自然数で、正の約数が 1 と自分自身のみであるような数」です。 ある数 \(n\) が素数かどうかを判定するためには、単純に考えると \(O(n)\) ...

トポロジカルソート（閉路のない有向グラフDAGをソート）

トポロジカルソートとは トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。 閉路のないDAG トポロジカルソート後 上図のように全ての辺の向きが左から...

セグメント木を完全に理解する！0から遅延評価やモノイドまで

セグメント木とは セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log ...

[AtCoder] ABC156 E – Roaming (500点)

問題概要 n 個の部屋に 1 ずつ人がいる。以下を k 回行ったとき、考えられる状態は何通りあるか \(10^9+7\) で割った余りで答えよ。 ある部屋 \(i\) にいた人が...

べき乗(pow(x,n))の計算 〜繰り返し二乗法による高速化〜

多くのプログラミング言語でサポートされてる \(x^n\) を計算する関数を実装することを目指します。 Input : x=2, n=4 Output : 16 べき乗は非常に大...

ビットDP(bit DP)の考え方 ~集合に対する動的計画法~

ビットDPとは ビットDP(bit DP) とは、ビットで表現した集合を添え字に持つ動的計画法(DP)のことです。 基本的には、以下のような DPを考えます。 \(dp[ S ]...

[AtCoder] ABC023 D – 射撃王

問題概要 問題へのリンク 風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のところにあり、1 秒経過するにつれて高...

[AtCoder] ABC155 D – Pairs (400点)

ARC037 億マス計算 の上位問題です。 問題概要 問題へのリンク N個の整数 \(A_1, A_2, A_3, \cdots, A_n\) がある。2つを選んでその積を \f...

[AtCoder] ABC155 E – Payment (500点)

問題へのリンク 問題概要 \(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。 N 円払う時、支払うのに使う...

グラフにおける橋(bridge)の検出

橋(bridge)とは 無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。 「連結」とは任意の2頂点間を行き来できることを言い、「非連結...

グラフにおける関節点(Articulation Points)

関節点(Articulation Points)または切断点 (cut vertex) とは 連結グラフにおける関節点(切断点)とは、「グラフから取り除くと、グラフが非連結になっ...

桁DP(Digit DP) を考え方から問題例まで徹底解説！

競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。 桁DPとは 桁ごとに分けて考える動的計画法です。 「1からNまでの整数について、条件を満たす数は...

[AtCoder] ABC154 F – Many Many Paths (600点)

問題へのリンク 問題概要 2次元の平面上で、以下のように関数 f(r,c) を定義する。 f(r,c) := (0,0)から(r,c)までの経路の個数 この時、以下を計算せよ。た...

[AtCoder] ABC154 E – Almost Everywhere Zero (500点)

問題へのリンク 問題概要 1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。 制約 \begin{align}&1 \leq N \le...