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

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻&n ...

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日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日AtCoder剰余,数え上げ,500点,競プロ,区間,素数,Pで割り切れる

問題概要

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

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