D – 大ジャンプ 解説 (AtCoder Beginner Contest 011)

問題へのリンク 問題概要 座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\) で \(D\) だけ移動する。 制約 \( 1 \leq N \leq 1000\)\(1 \leq D \leq 10^9\)\(-10^9 \leq X, Y \leq 10^9

「写像12相」で典型的な数え上げ問題のパターン総整理

条件を満たすものが何通りあるか数える問題、すなわち数え上げ問題には様々なものがありますが、「\(n\) 個の玉を \(x\) 個の箱に分ける方法は何通りか」などといった、典型的なものはある程度パターン化して解くことができます。 この記事では、ある集合からある集合へのマッピングが何通り存在するのかを考えるときに便利な「写像12相（the twelvefold way）」について紹介し、これを通じて典

自然数nをk個の0以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_{\leq k}(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然

自然数nをk個の1以上の整数に分割する方法の総数を求めるアルゴリズム

以下の2つを混同しそうですが、ここでは \(p_k(n)\) を求めることを考えます。 \(p_k(n)\) : 自然数 \(n\) を \(k\) 個の 1 以上の整数に分割する方法の数。言い換えると、区別できない \(n\) 個の要素を区別できない \(k\) 個ちょうどのブロックに分割する方法の数\(p_{\leq k}(n)\) : よく \(P(n,k)\) とも書く。自然数 \(n\)

ベル数を求めるアルゴリズム：第2種スターリング数の和を効率的に計算する

ベル数とは ベル数とは「区別できる \(n\) 個の要素を区別できない \(k\) 個以下のブロックに分割する方法の数」のことです。 これは、第2種スターリング数を用いて表すことが可能です。 第2種スターリング数とは、区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数のことで、\(S(n,k)\) などと表すことが多いです。 ベル数は、第2種スターリング数の

第2種スターリング数を求めるアルゴリズム

第2種スターリング数とは 第2種スターリング数 \(S(n,k)\) は、以下の3つの性質を持つ数です。 \(S(0,0)=1, ~ \forall i_{\geq 1}. S(i,0)=0\) として、\(S(n,k) = k S(n-1,k) + S(n-1, k-1)\) が成立する区別できる \(n\) 個の要素を区別できない \(k\) 個のブロックに分割する方法の数\(f_k(x)=x

部分和問題（N個の配列から和がKになるように選ぶ）とその解き方

部分和問題とは、\(N\) 個の数 \( a_1, a_2, ..., a_n\) が与えられたとき、その中からいくつかを選んで和をちょうど \(K\) にできるか判定をする問題です。 例えば配列が [1,3,8] で、\(K\) が 9 のときは、1,8 を選ぶと和が 9 になり K に一致します。 全探索による単純なアルゴリズムでは計算量が大きくなってしまいますが、\(K\)と \(N\) の

座標圧縮の解説（1次元から2次元の圧縮まで）

座標圧縮は、座標の情報から、位置関係や大小関係だけ抽出するテクニックです。 仮に座標の範囲が非常に広い場合、以下のような不都合が生じてしまいます。 例：\(0\) ~ \(10^9\) の数直線はメモリにのらない例：\(10^9 \times 10^9\) の領域はメモリにのらない このような状況では、情報を圧縮しなければ探索などを行うことができません。 情報のない空白部分が連続している場合、不要

ダブリングの基本概念とその応用

ダブリングは、全体の要素数がN個あって1回移動した時にどの要素に到達するのか定まっているとき、「K個先の要素を求めるのに \(O(K)\) かかる」ような状況において 前処理：\(O(N \log K)\) 時間, \(O(N \log K)\) 空間クエリ：\(O(\log K)\) で行うことができるようにするアルゴリズムです。 繰り返し二乗法もダブリングの一種と捉えることができ、最近共通祖先

D – Teleporter 解説 (AtCoder Beginner Contest 167)

問題へのリンク 問題概要 町が \(N\) 個ある。町 \(i\) から町 \(A_i\) に移動することを K 回繰り返す。町 1 から始めた時、最終的にどの町にたどり着くか？ 制約 \(2 \leq N \leq 2 \times 10^5\)\(1 \leq A_i \leq N\)\(1 \leq K \leq 10^{18}\) 考え方 単純にシミュレーションをしようとしても、\(K\)

再帰関数を用いた深さ優先探索(DFS)による全探索アルゴリズム

forループを用いた全探索などは比較的簡単な内容なので直感的にもわかりやすいですが、簡単なものしか全探索できません。 複雑な条件や構造を持つものを全探索したい場合には、再帰関数を用いた深さ優先探索(DFS)を用いる必要がある場合があり、競技プログラミングなどで良く出題されています。 前提知識 今回の内容を理解するために必要なことを簡単に説明しておきます。 再帰関数とは 再帰関数を詳しく考えようとす

ランレングス圧縮と復元

ランレングス圧縮（ランレングス符号化）とは、データの圧縮方法の一つで、圧縮前に正確に復元することができる可逆圧縮の一種です。 同じ文字が連続して何文字出現するかに変換します。 例： In: aaallgooooooOut: a3l2g1o6 圧縮(encode)する際は Run Length Encoding, 復元(decode)する際は Run Length Decoding と言います。 ア

重みが最小となる閉路を求めるアルゴリズム

アルゴリズム 最小コストの閉路： 任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除くv から u への最短経路 d を求める(ダイクストラ/BFS など)d+cost(u,v) を計算するグラフ G に e を戻すd+cost(u,v) の最小値が、閉路の重みの最小値 ※ ある辺 e を含む最小のコストの閉路を、全ての辺について求めます。 ※ 具体例では以下の様に

F – Division or Substraction 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 \(N\) が \(K\) 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような \(K\) が何通り存在するか答えよ。 \(N\) が \(K\) で割り切れる：\(N\) を \(\frac{N}{K}\) にする\(N\) が \(K\) で割り切れない：\(N\) を \(N-K\) にする 制約 \( 2 \leq N \leq 10^{12}\)

E – Yutori 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 N日間のうちK日働く。 一日働いたら、直後のC日間働けないi+1 日目は、Sの i 文字目が 'o' の時だけ働ける 必ず働く日を全て求めよ。 制約 \(1 \leq N \leq 2\times 10^5\)\(1 \leq K \leq N\)\(0 \leq C \leq N\) 考え方 「必ず働く日」や「必ず働かなくても良い日」というのは、どの

D – Lunlun Number 解説 (AtCoder Beginner Contest 161)

問題へのリンク 問題概要 桁ごとに見た時、隣り合う数字の差の絶対値が 1 以下になる数を考える。小さいほうから K 番目の数を求めよ 制約 \(1 \leq K \leq 10^5\) 考え方 制約が結構重要です。小さい方から1つずつ全探索することができれば、求められそうだということが分かります。 特殊な条件を持つ数を小さい方から全探索する時（パナソニックプログラミングコンテスト2020 D -

木DPと全方位木DPを基礎から抽象化まで解説【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

木DPと全方位木DPの総まとめ【競技プログラミング】

競技プログラミングでよく出題される木DPについての説明と、それを同じ計算量で全頂点について求められるように応用した全方位木DPについて解説します。 木DP 基本的な考え方とイメージ 木DP とは、根を一つ固定した木について、以下のように部分木に関する値を利用して計算する動的計画法です。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 木が N 頂点から構成されるなら、部分木

N – 木 解説（AtCoder Typical DP Contest）

問題へのリンク 問題概要 木が与えられる。辺が常に連結になるように木を描く。何通りの描き方があるか、mod 1,000,000,007 で求めよ。 制約 \(2 \leq N \leq 1000 \) 考え方 前提：木DPの考え方 俗に言う、木DP を用います。木DPでは以下のようなDPを基本に考えます。 dp[ v ] := 頂点 v を根とする部分木についての何かしらの値 それぞれの部分木から

ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。 ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。 負の辺が含まれていても動作する負の閉路がある場合は検出できる という利点があります。 アルゴリズム グラフ G = (V, E) に対するワーシャル・フロイド法は以下のようになります。 ワーシャル・フロイド法：（「dist[ i ][ j

トライ木(Trie木) の解説と実装【接頭辞(prefix) を利用したデータ構造】

Trie木は、効率的な検索(retrieval)のために使われるデータ構造です。文字列などの先頭部分(接頭辞: prefix)の共通部分を共有して保存することで、\(O(M)\) での検索を可能にします。（文字列の長さを\(M\) としました。） 以下は、「fire・firearm・firework・fireman・algo」をトライ木に保存した時の状態を表しています。 トライ木の仕組み 基本は木

平方数の判定をするアルゴリズム

Nが自然数の2乗で表現できるとき、平方数と言います。 平方数の例4 (= 2×2)9 (= 3×3)16 (= 4×4)25 (= 5×5) アルゴリズム 全探索でのアルゴリズム： \(\sqrt{N}\) 以下の自然数 \(k\) に対して以下を確かめる\(k^2 = N\) となる \(k\) が存在すれば N は平方数 ※ 平方数なら、\(k^2 = N\) となる \(\sqrt{N}\)

Nの約数の個数を求めるアルゴリズム

アルゴリズム Nの約数の個数： N を素因数分解するそれぞれの指数に1を足す「2.」で得られたものを全てかけ合わせる ※ 素因数分解のアルゴリズムに関してはこちらを参照 ※ 例と...

B – 123 Triangle 解説 (AtCoder Grand Contest 043)

問題へのリンク 問題概要 1,2,3 で構成された整数列 \(a_1 a_2 a_3 \cdots a_N\) が与えられ、\(x_{i,j}\) を以下のように再帰的に定義する...

プリム法による最小全域木を求めるアルゴリズム

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。 \(T\)...

クラスカル法による最小全域木を求めるアルゴリズム

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木（Spanning Tree) と言います。 \(T\)...

パスカルの三角形による二項係数(nCk)の計算

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}...

パスカルの三角形による二項係数(nCk)の計算

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}...

二項係数(nCk)の偶奇判定のアルゴリズム

Lucasの定理を利用することで、二項係数(nCk) が偶数なのか奇数なのかを効率よく判定することができます。 アルゴリズム Lucasの定理をそのまま利用したアルゴリズム： \...

二項係数(nCk)を素数(p)で割った余りの計算（Lucas の定理）

Lucas の定理を利用すると、\(_{n}\mathrm{C}_{k}\)% \(p\) が \(O( p^2 \log_p n)\) で計算できます。素数 \(p\) が小さ...

配列の全ての要素(N個)の最大公約数(GCD)を求めるアルゴリズム

配列 A が与えられて、その全ての要素の最大公約数(GCD)を求めることを考えます。2つの最大公約数だけではなく、N個の要素の最大公約数を求めます。 例： Input: A = ...

拡張ユークリッドの互除法

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、 $$ ax+by=gcd(a,b)$$ の形をした...

配列の全ての要素の最小公倍数(LCM)を求めるアルゴリズム

配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数...

グラフの2頂点が同じ連結成分に属するか判定するアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属...

グラフの連結成分の個数を求めるアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 連結成分は3つ アルゴリズム グラフ \(G=(V,E)\) の連結成分の個数...

区間の和を求めるアルゴリズム（区間の更新なし）

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 [L, R) の和を求めるアルゴリズムについてです。 区...

二次元での区間和を求めるアルゴリズム（区間の更新なし）

大きさが \(H × W\) の二次元配列 \(a\) 上において、 [h1,h2)×[w1,w2) の範囲の区間和を求めるアルゴリズムについてです。 input: a = {{...

フローネットワークの最小カットの容量を求めるアルゴリズム

アルゴリズム フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \( f^* \) を求める\( f^* \) が最小カットの容量 ※ カット \(...

二部グラフの最大マッチングを求めるアルゴリズム

アルゴリズム 二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G'\) を作る\(G\) にソース \(s\) とシンク \(t...

Ford-Fullkerson法による最大フローの求め方

フローの基本となる用語はこちら アルゴリズム フロー \(f\) を 0 としてはじめるソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \(...

フローネットワークの基礎と用語の定義

フローネットワークとフロー フローネットワーク 関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローネットワーク \(f\) は、以下の特...

ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）

最近共通祖先（LCA）とは 木において、ある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。 頂点 u と v...

E – Roadwork 解説（AtCoder Beginner Contest 128）

問題へのリンク 問題概要  N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 \(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−...

半分全列挙による全探索の高速化

N 個の要素の組み合わせを計算する際、N/2 ずつの2グループに分けてそれぞれを全列挙し、組み合わせ方を高速に求めるという工夫を「半分全列挙」と言います。 選択した数列の合計値を...

木の直径を求めるアルゴリズム

木（連結で閉路を持たない(無向)グラフ）について、直径の概念の説明とそのアルゴリズムの解説です。 木の直径とは 木に存在する2つノード間の最大距離を木の直径と言います。 例えば、...

組み合わせゲーム理論の基礎とGrundy数でのゲーム必勝法！

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。 前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題につい...

N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。 隣り合う...

区間DP の考え方と使える状況まとめ

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。 区間DPとは 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです...

L – Deque 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。 a の先頭要素または末尾要素を取り...

K – Stones 解説 (Educational DP Contest / DP まとめコンテスト)

問題へのリンク 問題概要 二人で以下のゲームを行う。先手と後手のどちらが勝つか？ 以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を...

A – コンテスト 解説 (Typical DP Contest)

問題へのリンク 問題概要 N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか？ 制約...

E – Divisible Substring 解説（AtCoder Beginner Contest 158）

問題概要 長さ N の数 S が与えられる。素数 P で割り切れるような区間の選び方は何通りあるか？ 制約 \(1 \leq N \leq 2 \times 10^5\)\(2 ...

ダイクストラ法による単一始点最短経路を求めるアルゴリズム

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。 ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点と...

ベルマンフォード法による単一始点最短経路

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。 ベルマンフォード法は、単一始点最短経路問題を解く時に利用されます...

累積和で高速化！区間和を求めるクエリ

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられて、区間 [L, R) の和を求めたい時を考えてみます。 区間 [L,...

Binary Indexed Tree (BIT) の仕組みとその応用

Binary Indexed Tree は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)...

約数を全列挙するアルゴリズム

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。 単純なアルゴリズムでは約数の全列挙に \(O(N)\) だけかかりますが、約数の性質を活か...

[AtCoder] ABC157 D – Friend Suggestions 解説（400点）

問題概要 N 人がいて、M 組が友達関係、K 組がブロック関係である。それぞれに対して以下を満たす「友達候補」が何人いるか答えよ。 まだ友達関係ではないブロック関係ではない友達関...

グラフの連結成分に関するアルゴリズム

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。 連結成分がいくつあるのかを求めたり、同じ連結成分に含まれるのかどうかを判定する...

[AtCoder]ABC157 E – Simple String Queries (500点)

問題概要 長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。 S の \(i_q\) 番目を \(c_q\) に変更するS の \(...

[AtCoder]ABC157 E – Simple String Queries (500点)

素因数分解のアルゴリズム

素因数分解とは「ある自然数を素数の積の形に分解すること」です。 1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と、複数の自然数を前処理 \(O(n l...

最小公倍数を求めるアルゴリズム

最小公倍数(LCM: least common multiple) とは、「0でない複数の自然数の公倍数のうち最小の自然数」のことを言います。 最小公倍数は、最大公約数を利用する...

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

素数とは 「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...

[AtCoder] ABC136 E – Max GCD (500点)

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

AtCoder ABC 139 E – League

問題へのリンク 問題概要 N人の選手がいる。各選手は1日1試合のみできる。総当たり戦を行う時、最短で何日かかるか？ ただし、i 番目の選手は \(A_{i, 1}, A_{i, ...

AtCoder ABC 152 F – Tree and Constraints

問題へのリンク 問題概要 N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか？ 制約 i：頂点 \(u_i\) と頂点 \(v_i\) を...

AtCoder ABC 152 F – Tree and Constraints

問題へのリンク 問題概要 N頂点の木がある。辺を白か黒で塗るとき、以下のような制約をM個満たすような塗り方は何通りか？ 制約 i：頂点 \(u_i\) と頂点 \(v_i\) を...

動的計画法（Dynamic Programming）

動的計画法とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。 普通に計算すると同じ計算を何度も繰り返してしまい非効率であるようなアル...

AtCoder ABC152 D – Handstand 2

問題へのリンク 問題 N以下の整数の組（A, B）について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか？ 制約 $$1\leq N \leq ...

AtCoder ABC152 D – Handstand 2

問題へのリンク 問題 N以下の整数の組（A, B）について、Aの先頭とBの末尾の数が等しく、Aの末尾とBの先頭の数が等しいのは何通りあるか？ 制約 $$1\leq N \leq ...

貪欲なアルゴリズム（greedy）

貪欲なアルゴリズムとは以下のような性質を持つアルゴリズムのことを言います。 その場での最善の手を選ぶことを繰り返す 貪欲法を用いたアルゴリズムは、実装が簡単な上に応用範囲が広いの...

AtCoder キーエンスプログラミングコンテスト2020 D – Swap and Flip

問題へのリンク 問題 表が\(A_i\)、裏が\(B_i\)、と書かれた\(N\)枚のカードがある。「隣り合う2枚を選択して、入れ替えて裏返す」という操作をして、カードの並びが広...

互いに素な集合(Disjoint-set・Union-find)

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。 素集合系の例 素集合系は、いくつかの木構造を用いることで管理...

AtCoder ABC 135 D – Digits Parade

問題へのリンク 問題 一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。 答えを 1e9+7 で割った余りで答えよ。 制約 $...

ユークリッドの互除法とその拡張

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。 このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズム...

二項係数(nCk)を素数で割った余りの計算

競技プログラミングの問題などでは、二項係数を非常に大きい素数 P で割った余りを出力させる問題が出題されることがあります。 \(P = 1000000007 = 10^9 + 7...

【AtCoder Beginner Contest 145】C – Average Length

問題 元の問題: C - Average Length N個の全ての点を1回ずつ通るような動き方は\(N!\)通りある。総移動距離の平均を求めよ。 解き方 順列を使って解く方法 ...

順列(n!)の全探索

順列の全探索とは \(n!\)通りの全探索を行いたい時に順列が用いられます。 順列(permutation)とは、n個のものを順番に並べるのは何通りあるかを考える問題です。n個全...

幅優先探索(Breadth First Search)

幅優先探索とは 全探索アルゴリズムの一種です。グラフやグラフと同一視できるものを探索する際に良く使われます。深さ優先探索と似ていますが、幅優先探索は始めの状態に近いものから順番に...

【AtCoder Beginner Contest 146】D – Coloring Edges on Tree

問題 AtCoderでの問題：D - Coloring Edges on Tree 木構造について、頂点から見た時に、自身から伸びる枝に重複が無いように色を塗る問題です。使う色の...

深さ優先探索(Depth First Search)

深さ優先探索とは 全探索アルゴリズムの一種です。木などのグラフやグラフと同一視できるものを探索する際に良く使われます。幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達...

グラフ(Graph)

グラフとは グラフとは、頂点(ノード)と、頂点同士の関係を表したデータ構造です。 数学的には、グラフは以下の2つから構成されます。 頂点（ノード）の集合頂点同士がつながっているか...

セット(Set)・集合

Setとは、数学における集合をデータ構造として表したものです。順序はなく、変更可能で、重複した要素を持ちません。 要素の挿入・削除・検索を高速に行うことができる特徴があります。 ...

キュー(Queue)・待ち行列

キューは待ち行列とも呼ばれます。最初に格納したデータが最初に出てくるような、線形なデータ構造をしていて、このような順序をFirst In First Out (FIFO)と言いま...

スタック(Stack)

スタックとは 線形なデータ構造の1つです。データを格納する操作(push)と取り出す操作(pop)について、対象になるデータの順番が決められています。 スタックは、最後に格納した...

連結リスト(Linked List)

連結リストとは 連結リストはノードと呼ばれるデータの塊が、複数繋がってできたデータ構造です。 1つのノードは、格納する値自体と、次のノードへのアドレスを保持します。先頭から各ノー...