2020年3月15日その他bit全探索,全探索,テーマ記事,競プロ,半分全列挙,テクニック

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

選択した数列の合計値を半分全列挙で探索する場合(\(2^4\)ずつに分け ...

2020年3月13日グラフグラフ,,競プロ,無向グラフ,重み付きグラフ,木の直径

木に存在する2つノード間の最大距離を木の直径と言います。

重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。

重み無しの木の例:

以下は直径が5となる木の例で ...

2020年3月13日その他テーマ記事,競プロ,ゲーム,二人零和有限確定完全情報ゲーム,Grundy数,不偏ゲーム,組み合わせゲーム,スプレイグ・グランディの定理,Nim,NimK

競技プログラミングなどで頻出のテーマである組み合わせゲームやGrundy数についてまとめました。

前半は全ての方に向けての内容で、プログラム例や競技プログラミング特有の話題については後半にあります。

組み合わせゲーム ...

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日AtCoderDP,競プロ,ゲーム,二人零和有限確定完全情報ゲーム,後退解析,最大化,最小化,区間DP

問題へのリンク

問題概要

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

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

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

問題へのリンク

問題概要

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

以下の操作を交互に行う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日AtCoder剰余,数え上げ,500点,競プロ,区間,素数,Pで割り切れる

問題概要

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

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

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

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

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

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