区間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 投稿
基環樹構造上の動的計画法：アルゴリズム設計と実装手法
基環樹の定義と構造的特徴
基環樹（Base Ring Tree）とは、ノード数と辺数が等しく、かつ連結なグラフ構造を指します。その最大の特徴は、グラフ内に閉路（サイクル）がちょうど一つだけ存在することです。グラフが非連結であり、各連結成分がノード数と辺数を一致させる場合は「基環樹森」と分類されます。通常の木構造を対象とした動的計画法（木DP）と比較すると、閉路 ...
5月13日 16:44 投稿