2020年2月15日グラフグラフ,競プロ,関節点,切断点,,lowlink,DFS,検出

連結グラフにおける関節点(切断点)とは、「グラフから取り除くと、グラフが非連結になってしまうような頂点」のことを言います。

※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があること ...

2020年2月14日動的計画法DP,桁DP,テーマ記事,競プロ

競技プログラミングで良く用いられる動的計画法の1つ「桁DP」について解説します。

桁DPとは

桁ごとに分けて考える動的計画法です。

「1からNまでの整数について、条件を満たす数はいくつあるか?」
「1からNまでの ...

2020年2月10日AtCoder二項係数,600点,二次元,区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...

2020年2月10日AtCoder動的計画法,数え上げ,DP,500点,桁DP,場合分け

問題へのリンク

問題概要

1 以上 N 以下の整数で、0 でない数字がちょうど K 個あるものの個数を求めよ。

制約

\begin{align}
&1 \leq N \leq 10^{100} \\ ...

2020年1月26日AtCoder操作,最大公約数,不変量,最大値,500点,約数

問題へのリンク

問題概要

N 個の整数列 \(A_1, A_2, \cdots, A_N\) に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作:\(A_1, A_2, ...

2020年1月25日AtCoder有向グラフ,閉路,DAG,有向非巡回グラフ,半順序,500点

問題へのリンク

問題概要

N人の選手がいる。各選手は1日1試合のみできる。総当たり戦を行う時、最短で何日かかるか?

ただし、i 番目の選手は \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, ...

2020年1月25日AtCoderbit演算,bit全探索,包除原理,,余事象,制約,600点

問題へのリンク

問題概要

N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか?

制約 i:頂点 \(u_i\) と頂点 \(v_i\) を繋ぐパス上に、黒く塗られた辺が1つ ...

2020年1月20日動的計画法入門,動的計画法,DP,競プロ,ナップサック

動的計画法とは

動的計画法(Dynamic Programming)とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。

以下のような特徴がありますが、抽象的なのでここではざっと眺 ...

2020年1月19日AtCoder数え上げ,桁の数が等しい,400点

問題へのリンク

問題

N以下の整数の組(A, B)について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか?

制約

$$1\leq N \leq 2 \times 10^5$$

2020年1月19日貪欲法入門,競プロ,貪欲法

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。

その場での最善の手を選ぶことを繰り返す

貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いので非常に重要です。

大まか ...