2020年3月10日AtCoderDP,競プロ,区間DP,区間の除去・圧縮・合体

問題へのリンク

問題概要

N 個の数列 \({a_1, a_2, a_3, \cdots, a_N\}\) があり、以下の操作を数列の要素数が 1 になるまで繰り返す。

隣り合う2つ \(a, b\) を選んで取り除き ...

2020年3月10日動的計画法区間DP,区間の除去・圧縮・合体,DP,テーマ記事,競プロ,区間

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。

区間DPとは

区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。

基本的には、以下のような DP ...

2020年3月10日AtCoder区間DP,DP,競プロ,ゲーム,二人零和有限確定完全情報ゲーム,後退解析,最大化,最小化

問題へのリンク

問題概要

数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。

a の先頭要素または末尾要素を取り除く。 取り除いた要素を x& ...

2020年3月10日AtCoderゲーム,二人零和有限確定完全情報ゲーム,後退解析,DP,競プロ

問題へのリンク

問題概要

二人で以下のゲームを行う。先手と後手のどちらが勝つか？

以下の操作を交互に行うA = \( a_1, a_2, \ldots, a_N\) の元 x を一つ選び、K 個の山から丁度 x 個取り ...

2020年3月10日AtCoder数え上げ,DP,競プロ,ナップサック,合計得点が何通りか

問題へのリンク

問題概要

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

制約1 ≤ N ≤ 100
1 ≤ p ...

2020年3月8日AtCoder500点,競プロ,区間,素数,Pで割り切れる,剰余,数え上げ

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか？

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

2020年3月7日グラフ重み付きグラフ,単一始点最短経路,最短経路,ダイクストラ法,ヒープ,優先度付きキュー,貪欲法,グラフ,競プロ

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては

計算量が \(O(|E| \l ...

2020年3月7日グラフグラフ,競プロ,重み付きグラフ,ベルマンフォード法,単一始点最短経路,最短経路,負の閉路,負の辺

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ベルマンフォード法は、単一始点最短経路問題を解く時に利用され、

負の辺が含まれているような場合でも適用 ...

2020年3月6日その他区間和,テーマ記事,競プロ,区間,累積和,imos法,二次元区間和

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理：\(O(N)\)
クエリ：\(O(1)\)

で処理がで ...

2020年3月5日データ構造転倒数,二次元BIT,BIT,区間和,競プロ,二分探索,セグメント木,区間,データ構造,RAQ

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...