2020年3月19日グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理

アルゴリズム

最大フローを求めるアルゴリズム(Ford-Fullkerson法):

フロー \(f\) を 0 としてはじめる
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...

グラフフロー, フローネットワーク, 用語・定義

フローフローとフローネットワーク

関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ(フローネットワーク) \(G=(V,E)\) 上で定義されます。

2020年3月16日グラフ, 競プロ, LCA, ダブリング, 木の2頂点間の距離, 木のパス上に頂点があるか

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

頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...

2020年3月15日AtCoder競プロ, セグメント木, 区間, 更新, データ構造, set, imos法, 遅延評価セグメント木, イベントソート, 座標圧縮

問題へのリンク

問題概要

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

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

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

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

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

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

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

重み無しの木の例:

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

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

競技プログラミングなどで頻出のテーマである組み合わせゲームや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& ...