N – Slimes 解説 (Educational DP Contest / DP まとめコンテスト)
問題へのリンク
問題概要N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。
隣り合う2つ \(a, b\) を選んで取り除き ...区間DP の考え方と使える状況まとめ
競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。
区間DPとは区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。
基本的には、以下のような DP ...
L – Deque 解説 (Educational DP Contest / DP まとめコンテスト)
問題へのリンク
問題概要数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。
a の先頭要素または末尾要素を取り除く。 取り除いた要素を x& ...K – Stones 解説 (Educational DP Contest / DP まとめコンテスト)
問題へのリンク
問題概要二人で以下のゲームを行う。先手と後手のどちらが勝つか?
以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り ...A – コンテスト 解説 (Typical DP Contest)
問題へのリンク
問題概要N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。合計得点は何通り考えられるか?
制約1 ≤ N ≤ 1001 ≤ p ...
E – Divisible Substring 解説(AtCoder Beginner Contest 158)
長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか?
\(2 \leq P \leq 10000\ ...
ダイクストラ法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては
計算量が \(O(|E| \l ...ベルマンフォード法による単一始点最短経路を求めるアルゴリズム
グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。
ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、
負の辺が含まれているような場合でも適用 ...競プロでよく出る区間和問題の解き方まとめ
区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。
一次元の区間和累積和を用いることで、
前処理:\(O(N)\)クエリ:\(O(1)\)
で処理がで ...
Binary Indexed Tree (BIT) 総まとめ!区間加算や二次元BITまで
Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...