競技プログラミングにおけるグラフ理論・組合せ数学・動的計画法の応用テクニック
弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺 ...
9月14日 12:35 投稿
P4175 [CTSC2008]ネットワーク管理 解説
問題概要
ノード数が $ n $ の木が与えられ、各ノードには重み $ w_i $ が割り当てられている。$ q $ 個の操作を行う：
0 u v：ノード $ u $ の重みを $ v $ に変更する。
k u v：ノード $ u $ から $ v $ へのパス上の重みの第 $ k $ 番目の大きい値を求める。パス上にノードが $ k $ 個未満ある場合、invalid request! を出力する。
制約
$ 1 \le n, q \le 8 \cdot 10 ...
8月20日 16:41 投稿
ツリーの重軽分解：長子優先によるパス操作の高速化
セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。
木上のパスを線形構造に変換するアイデア
木は分岐構造を持つため ...
8月19日 04:01 投稿
解答：P5500 [LnOI2019] 真正的 OIer 从不女装
問題の解法
クエリを直接見ると、\(k=0\) の場合、区間の最大連続部分列を維持すればよい。
\(k=1\) の場合を考える。
元の配列:
.>>!|&>>?
変更後:
!<<.|?<<&
見にくい？回転してみる：（答えは変わらない）
&>>?|.>>!
気づいたか？区間の切り替えは二つの部分を交換することと等価である。つまり、先頭と末尾が同じ ...
8月14日 20:37 投稿
区間MEXの重要な性質とそのアルゴリズム
はじめに
この記事では、数列における区間MEX（Minimum Excluded Value）の重要な性質について考察します。MEXとは、数列に含まれていない最小の非負整数を指します。特に、「極小MEX区間」と呼ばれる概念に焦点を当て、その数がO(n)に収まることを証明し、効率的なアルゴリズムを提案します。
極小MEX区間の定義と重要性
極小MEX区間とは、区間の左端または右端を1つ削除 ...
7月15日 22:49 投稿
重み付き木の分割処理
木構造の分割処理
基本概念
木の分割処理：木構造を複数の非交差チェーンに分割する手法で、主に重み付きチェーン分割を用いる。以下の操作をサポート：
ノードxからノードyまでの最短経路上の全ノードの値の更新
ノードxからノードyまでの最短経路上の全ノード値の合計取得
ノードxとその部分木の値の更新
ノードxとその部分木の値の合計取得
重み付き子ノード：ノ ...
7月11日 23:30 投稿
CF1418G - Three Occurrences問題の解法
この問題は2500点の難易度を持つ競技プログラミングの問題です。
問題概要
二つの異なるアプローチを紹介します。
解法1
まず、各数の出現回数が3の倍数である場合を考えます。区間が有効であるためには、全ての数の出現回数を3で割った余りが0である必要があります。この条件を満たすために、出現回数を3で割った余りの配列をハッシュ化し、以前に同じハッシュ値が出現し ...
7月5日 22:08 投稿
P5298 [PKUWC2018] Minimax 解説：セグメント木マージによる木DP最適化
問題の分析
この問題は、セグメント木のマージ操作を用いて木構造上の動的計画法を最適化する手法が鍵となります。
まず、値の範囲が最大で10^9まで及ぶため、離散化（座標圧縮）が必要です。各値の出現確率を管理する必要があるため、基本的な木DPを考えます。
動的計画法の設計
dp[v][j] を頂点vにおいて、j番目に小さい値が出現する確率と定義します。遷移は以下の3 ...
6月28日 02:04 投稿
USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿
重量値セグメント木と動的ノード作成
目次- ブルートフォース法 (1)
ブルートフォース法 (2)
重量値セグメント木
演習問題
はじめに主席木を学習中に、重量値セグメント木の学習ノートを更新しておくのを思い出しました
まず、以下の問題を考えてみましょう：
配列に対して以下の操作を行います：
操作 (1)：配列中の第k小さい要素を問い合せます（答えは存在すると仮定）。
操作 (2)：ある要素を変更しま ...
5月28日 02:10 投稿