データ構造と問い合わせ
概要
累積和・差分と局所link更新から始め、heap・ordered setと単調stackで候補を保つ。単調stackからCartesian treeを構築し、Fenwick TreeとSegment Treeの区間集約を学ぶ。monoid要約の直後にLazy Segment Treeの区間作用を置き、その後に関数合成・Sparse Table・SWAG・canonical decomposition・Merge Sort Tree・implicit Segment Treeを比較してから、run分割による動的区間管理を扱う。bucketとMo、bit列とfingerprintを用途別に比較した後、過去の版と条件付き更新へ進む。最後のSegment Tree Beatsでは遅延作用と償却解析を組み合わせる。
更新可能な最小十分要約
問い合わせの答えを合成でき、更新で保てる十分な統計量を導く。
考え方
queryでは答えそのものを毎回計算せず、次の更新・問い合わせに十分な要約を保つ。prefix、局所link、候補集合、区間の積、過去の版など、変更の単位と必要な演算から表現を選ぶ。
成立条件と計算量
初期化・更新・queryの費用を別に数える。結合則、逆元、冪等性、更新作用の閉性は異なる条件である。機能の多い構造へ直行する前に、静的な前計算や端点更新だけで済むかを考える。
章の構成
項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。
- 一次元・二次元累積和と差分で区間情報を線形化する — 茶色
- 要素索引と連結リストで局所linkを更新する — 茶色
- heap・ordered setで全候補の極値を保つ — 緑色(導入)
- priority queue・best-first列挙 — 緑色。概念上の親: heap・ordered setで全候補の極値を保つ
- ordered set・multisetの動的順序管理 — 緑色。概念上の親: heap・ordered setで全候補の極値を保つ
- 支配関係から不要な候補を単調stack・queueで削る — 水色
- 大小関係をCartesian treeへ変換する — 青色
- 反転数・重み付き接頭辞統計をFenwick Treeで保つ — 水色
- 結合的な区間要約・区間分解・合成 — 水色(導入)
- 区間monoid要約 — 水色。概念上の親: 結合的な区間要約・区間分解・合成
- 区間更新を要約へ作用させる — 青色
- 有限関数・作用の合成 — 水色。概念上の親: 結合的な区間要約・区間分解・合成
- 冪等演算のoverlap range query・Sparse Table — 水色。概念上の親: 結合的な区間要約・区間分解・合成
- SWAG・two-stack queue aggregation — 青色。概念上の親: 結合的な区間要約・区間分解・合成
- Segment Treeのcanonical区間分解 — 青色。概念上の親: 結合的な区間要約・区間分解・合成
- 静的sorted range index・Merge Sort Tree — 青色。概念上の親: Segment Treeのcanonical区間分解
- 動的・implicit Segment Tree — 青色。概念上の親: 結合的な区間要約・区間分解・合成
- 端点更新型のrun分割管理 — 青色
- 値軸のbucket分割と区間集約 — 水色
- Moの順序で区間問い合わせの差分を更新する — 青色
- bitsetで集合演算をword並列化する — 水色
- bit列をTrieで索引化する — 水色
- 上位bitの支配関係によるXOR minimax — 青色
- Rolling fingerprintで列の同値性を比較する — 水色(導入)
- 列・文字列のrolling fingerprint — 水色。概念上の親: Rolling fingerprintで列の同値性を比較する
- 構造を共有して過去の版を保存・復元する — 青色(導入)
- rollback・DFS入退場の状態復元 — 青色。概念上の親: 構造を共有して過去の版を保存・復元する
- 永続data structure・structural sharing — 黄色。概念上の親: 構造を共有して過去の版を保存・復元する
- Segment Tree Beats — 橙色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC213 F「Common Prefixes」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC214 E「Packing Under Range Regulations」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査、priority queue・best-first列挙
- ABC216 G「01Sequence」 公式問題
技能・出典
主題: difference constraints・不等式系の最短路化(差の不等式をconstraint graphへ変換し、緩和と負閉路判定により可解性・極値・具体解を求められる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: difference constraints・不等式系の最短路化 / 補助タグ: 累積和・差分配列
- ABC217 E「Sorting Queries」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調進行による償却解析 / 補助タグ: priority queue・best-first列挙
- ABC218 H「Red and Blue Lamps」 公式問題
技能・出典
主題: path matchingのheap縮約greedy(重み付きpathの最小k-matchingについて、最小edge採用後の補正縮約を証明し、heapと双方向linkで全cardinalityの最適値を求められる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 要素索引と連結リストで局所linkを更新する(要素IDから前後linkを引き、挿入・削除で変わる局所linkだけを更新して列順を復元できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: path matchingのheap縮約greedy / 補助タグ: 索引付き連結リスト、priority queue・best-first列挙、状態・配置の正規化
- ABC231 F「Jealous Two」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC233 Ex「Manhattan Christmas Tree」 公式問題
技能・出典
主題: parallel binary search・多数境界の判定共有(各queryの未確定区間を保ち、同じroundのmidをbucketして一方向更新できる判定器を共有し、全queryの最小・最大成立境界を求められる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: parallel binary search・多数境界の判定共有 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換、累積和・差分配列
- ABC233 G「Strongest Takahashi」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 累積和・差分配列
- ABC238 E「Range Sums」 公式問題主題: DSUによる連結成分管理・縮約
技能・出典
主題: DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: DSUによる連結成分管理・縮約 / 補助タグ: 累積和・差分配列
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC244 Ex「Linear Maximization」 公式問題主題: 凸包・支持方向・境界候補
技能・出典
主題: 凸包・支持方向・境界候補(目的関数に対して内部候補が不要な理由を示し、凸境界だけを列挙できる。)。既習技能: Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。)。主タグ: 凸包・支持方向・境界候補 / 補助タグ: Segment Treeのcanonical区間分解
- ABC245 E「Wrapping Chocolate」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理
- ABC249 F「Ignore Operations」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: priority queue・best-first列挙
- ABC250 G「Stonks」 公式問題主題: slope trick
技能・出典
主題: slope trick(区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: slope trick / 補助タグ: priority queue・best-first列挙
- ABC251 Ex「Fill Triangle」 公式問題
技能・出典
主題: 標数pのFrobenius恒等式による反復高速化(標数pで中間の二項係数が消える恒等式 (1+x)^(p^t)=1+x^(p^t) をシフト演算へ適用し、隣接和反復をpの冪回ずつ飛ばす。圧縮列では各段のrun数の増加も評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。) / 端点更新型のrun分割管理(互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 標数pのFrobenius恒等式による反復高速化 / 補助タグ: 組合せ係数・数え上げ、ordered interval partition・ODT
- ABC252 Ex「K-th beautiful Necklace」 公式問題
技能・出典
主題: meet-in-the-middle・半分全列挙(探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。)。既習技能: bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: meet-in-the-middle・半分全列挙 / 補助タグ: binary Trieによるbit列索引
- ABC252 F「Bread」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: priority queue・best-first列挙
- ABC253 F「Operations on a Matrix」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、累積和・差分配列
- ABC254 Ex「Multiply or Divide by 2」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: 貪欲法と交換論 / 補助タグ: binary Trieによるbit列索引
- ABC254 F「Rectangle GCD」 公式問題主題: gcd不変量・差分構造
技能・出典
主題: gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: gcd不変量・差分構造 / 補助タグ: 区間monoid要約
- ABC256 Ex「I like Query Problem」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。) / 端点更新型のrun分割管理(互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調進行による償却解析 / 補助タグ: 遅延評価する区間作用、ordered interval partition・ODT
- ABC261 F「Sorting Color Balls」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC262 Ex「Max Limited Sequence」 公式問題主題: prefix分割DP
技能・出典
主題: prefix分割DP(列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。) / 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: prefix分割DP / 補助タグ: 寄与の数え上げと順序交換、座標・値の順序保存圧縮、遅延評価する区間作用
- ABC262 F「Erase and Rotate」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC263 Ex「Intersection 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 円環順序・chord交差(円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 単調境界探索 / 補助タグ: 円環順序・chord交差、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計、幾何の基本判定・配置・座標変換
- ABC266 Ex「Snuke Panic (2D)」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC273 Ex「Inv(0,1)ving Insert(1,0)n」 公式問題
技能・出典
主題: Stern–Brocot木の経路と祖先(隣接分数の行列式が1であることを保ち、mediantとEuclidの商列からStern–Brocot木の経路を同方向の連続回数へ圧縮する。経路の共通prefixで祖先関係と必要な祖先集合を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Stern–Brocot木の経路と祖先 / 補助タグ: ordered set・multisetの動的順序管理、再帰分割・分割統治、small-to-large・DSU on Tree
- ABC275 Ex「Monster」 公式問題主題: slope trick
技能・出典
主題: slope trick(区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Cartesian treeによる区間極値分解、slope trick / 補助タグ: ordered set・multisetの動的順序管理、small-to-large・DSU on Tree
- ABC276 Ex「Construct a Matrix」 公式問題主題: 線形方程式・rank
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元、座標・値の順序保存圧縮、累積和・差分配列
- ABC280 Ex「Substring Sort」 公式問題主題: 接尾辞の順序とLCPを索引化する
技能・出典
主題: 接尾辞の順序とLCPを索引化する(接尾辞の辞書順とLCPを索引化し、出現範囲・部分文字列順位・distinct数・巡回shiftを処理できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 接尾辞順序・LCP索引 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC282 Ex「Min + Sum」 公式問題主題: 再帰分割・分割統治
技能・出典
主題: 再帰分割・分割統治(pivot・上位bit・短い側で部分問題へ再帰分割するか、部分結果をbalancedな積木・remainder tree・CDQで重複なく合成できる。)。既習技能: 冪等演算のoverlap range query・Sparse Table(冪等な演算なら重なりを許す二つの2冪区間で任意rangeを覆えることを使い、静的queryをO(1)で答える。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。主タグ: 再帰分割・分割統治 / 補助タグ: 単調進行による償却解析、冪等演算のoverlap range query・Sparse Table
- ABC282 G「Similar Permutation」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。 次の二つのrankの大小関係で遷移元が四つの長方形へ分かれる。new[j][k][l]の全rank対走査を、旧layerの二次元prefix和から定数個の長方形和へ変える。主タグ: DP遷移の集約・高速化 / 補助タグ: DPの最小十分状態、累積和・差分配列
- ABC283 F「Permutation Distance」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: event・値順のオフライン走査 / 補助タグ: 幾何の基本判定・配置・座標変換、区間monoid要約
- ABC287 Ex「Directed Graph and Query」 公式問題主題: 推移閉包
技能・出典
主題: 推移閉包(各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。主タグ: 推移閉包 / 補助タグ: bitsetによるword並列集合演算、event・値順のオフライン走査
- ABC294 G「Distance Queries on a Tree」 公式問題主題: Euler順による部分木区間化
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。追加で学ぶ技能: ancestor query・LCA(binary lifting等を前計算し、level ancestor・LCA・木距離をqueryとして取得できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: ancestor query・LCA、Euler順による部分木区間化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC296 F「Simultaneous Swap」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 状態・配置の正規化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC298 G「Strawberry War」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 有界全列挙・有限case分解、累積和・差分配列
- ABC299 G「Minimum Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 貪欲法と交換論 / 補助タグ: 区間monoid要約
- ABC300 F「More Holidays」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。 - ABC303 G「Bags Game」 公式問題
技能・出典
主題: minimax・得点差・局面値を評価するゲームDP(有限DAGの局面で手番ごとの最大化・最小化と終端値を定義し、得点差や利得を後続状態から評価できる。循環時の無限継続と独立な数ゲームの加算は別の技能として扱う。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: 有限局面DAGのminimax / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC306 F「Merge Sets」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC307 F「Virus 2」 公式問題主題: 最短路モデル
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最短路モデル / 補助タグ: 単調進行による償却解析、priority queue・best-first列挙
- ABC307 G「Approximate Equalization」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 累積和・差分配列
- ABC309 F「Box in Box」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC311 G「One More Grid Task」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: DSUによる連結成分管理・縮約、累積和・差分配列
- ABC319 F「Fighter Takahashi」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 部分集合・bitmask状態DP / 補助タグ: 貪欲法と交換論、priority queue・best-first列挙
- ABC319 G「Counting Shortest Paths」 公式問題主題: 状態グラフのモデリングと探索
技能・出典
主題: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / DP遷移を因数分解・集約して加速する(全遷移の総和から禁止辺・禁止keyの集計値を引き、例外の総数で計算量を評価できる。)。 補グラフBFSで距離層を先に確定する。dp[v]=Σ_{u∈前層,uv許可}dp[u]を前層総和−禁止隣接点のdp和へ変形する。BFSの未訪問集合走査と経路数の補集合集約は別工程として計算量を証明する。主タグ: 状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析、DP遷移の集約・高速化、ordered set・multisetの動的順序管理
- ABC320 E「Somen Nagashi」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: ordered set・multisetの動的順序管理、priority queue・best-first列挙
- ABC324 G「Generate Arrays」 公式問題
技能・出典
主題: small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: small-to-large・DSU on Tree / 補助タグ: ordered set・multisetの動的順序管理
- ABC327 F「Apples」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 遅延評価する区間作用
- ABC330 F「Minimize Bounding Square」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調境界探索 / 補助タグ: 一次元凸・単峰最適化、累積和・差分配列
- ABC330 G「Inversion Squared」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 法上の四則演算・高速累乗・逆元、累積和・差分配列
- ABC333 E「Takahashi Quest」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 構成解・witness復元 / 補助タグ: 貪欲法と交換論、累積和・差分配列
- ABC334 F「Christmas Present 2」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。 配達の直接経路をbaselineにし、補充境界iの追加費用をd_iとする。dp[i]=d_i+min_{i−K≤j<i}dp[j]。窓から出た候補と支配される候補をdequeから除き、O(NK)をO(N)へ落とす。主タグ: DP遷移の集約・高速化 / 補助タグ: 単調stack・queueによる支配候補の削除
- ABC337 G「Tree Inversion」 公式問題主題: Euler順による部分木区間化
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: Euler順による部分木区間化 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC339 E「Smooth Subsequence」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 区間monoid要約
- ABC346 G「Alone」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 遅延評価する区間作用
- ABC347 F「Non-overlapping Squares」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: グリッド・多次元表の局所DPを設計する(グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: グリッド・多次元表の局所DP、累積和・差分配列
- ABC353 G「Merchant Takahashi」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。 max_j(dp[j]−C|j−t|)+pを、j≤tのmax(dp[j]+Cj)−Ct+pとj≥tのmax(dp[j]−Cj)+Ct+pへ分ける。二本の区間最大で各イベントO(log N)。主タグ: DP遷移の集約・高速化 / 補助タグ: 区間monoid要約
- ABC354 F「Useless for LIS」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC359 F「Tree Degree Optimization」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 貪欲法と交換論、priority queue・best-first列挙
- ABC360 F「InterSections」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: event・値順のオフライン走査 / 補助タグ: 座標・値の順序保存圧縮、遅延評価する区間作用
- ABC360 G「Suitable Edit for LIS」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 値域集約による部分列DP / 補助タグ: 座標・値の順序保存圧縮、区間monoid要約
- ABC364 F「Range Connect MST」 公式問題
技能・出典
主題: cut・cycle性質から最適全域木を構成する(cut・cycle性質で辺の安全性を証明し、Kruskal法または同値な選択で最小・最大全域木を構成できる。)。既習技能: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理
- ABC366 G「XOR Neighbors」 公式問題主題: 線形方程式・rank
技能・出典
主題: 線形方程式・rank(制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: bitsetで集合演算をword並列化する(集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: 線形方程式・rank / 補助タグ: bitsetによるword並列集合演算、構成解・witness復元
- ABC368 G「Add and Multiply Queries」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 単調進行による償却解析 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、ordered set・multisetの動的順序管理
- ABC373 F「Knapsack with Diminishing Values」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。) / priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 貪欲法と交換論、資源軸knapsack DP、priority queue・best-first列挙
- ABC376 E「Max × Sum」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: ordered set・multisetの動的順序管理
- ABC376 G「Treasure Hunting」 公式問題
技能・出典
主題: 01 on Tree・親先行順序のcluster縮約(親先行制約下の交換比較をcluster統計へまとめ、01 on Treeの縮約貪欲で最適順序を構成できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 01 on Tree・親先行順序のcluster縮約 / 補助タグ: DSUによる連結成分管理・縮約、貪欲法と交換論、priority queue・best-first列挙
- ABC378 E「Mod Sigma Problem」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC380 G「Another Shuffle Window」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元、尺取り法・sliding window
- ABC388 G「Simultaneous Kagamimochi 2」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。主タグ: 単調境界探索 / 補助タグ: 区間monoid要約、尺取り法・sliding window
- ABC392 F「Insert」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 逆向きのオフライン処理 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC396 F「Rotated Inversions」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC404 G「Specified Range Sums」 公式問題
技能・出典
主題: difference constraints・不等式系の最短路化(差の不等式をconstraint graphへ変換し、緩和と負閉路判定により可解性・極値・具体解を求められる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: difference constraints・不等式系の最短路化 / 補助タグ: 累積和・差分配列
- ABC406 F「Compare Tree Weights」 公式問題主題: Euler順による部分木区間化
技能・出典
主題: Euler順による部分木区間化(Euler tourのin/out時刻を構成し、部分木または根からのpath寄与を配列の区間へ写せる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: Euler順による部分木区間化 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC406 G「Travelling Salesman Problem」 公式問題主題: slope trick
技能・出典
主題: slope trick(区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: slope trick / 補助タグ: 構成解・witness復元、ordered set・multisetの動的順序管理
- ABC407 E「Most Valuable Parentheses」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。既習技能: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 貪欲法と交換論 / 補助タグ: priority queue・best-first列挙
- ABC407 F「Sums of Sliding Window Maximum」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理、累積和・差分配列
- ABC408 F「Athletic」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。 dp[p_h]=1+max_{|j−p_h|≤R,H_j≤h−D}dp[j]。高さ順にeligibleな点だけを有効化し、残る位置条件を区間最大にする。二条件の全点走査がsortとO(N log N)の更新・取得になる。主タグ: DP遷移の集約・高速化 / 補助タグ: event・値順のオフライン走査、区間monoid要約
- ABC410 G「Longest Chord Chain」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 値域集約による部分列DP / 補助タグ: event・値順のオフライン走査、幾何の基本判定・配置・座標変換、区間monoid要約
- ABC414 G「AtCoder Express 4」 公式問題主題: 最短路モデル
技能・出典
主題: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: Segment Treeのcanonical区間分解(区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。)。主タグ: 最短路モデル / 補助タグ: Segment Treeのcanonical区間分解
- ABC421 G「Increase to make it Increasing」 公式問題
技能・出典
主題: 最小費用流・circulation(流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 最小費用流・circulation / 補助タグ: 累積和・差分配列
- ABC423 E「Sum of Subarrays」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 累積和・差分配列
- ABC427 E「Wind Cleaning」 公式問題主題: 状態グラフのモデリングと探索
技能・出典
主題: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。既習技能: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 状態グラフのモデリングと探索 / 補助タグ: DPの最小十分状態、累積和・差分配列
- ABC428 F「Pyramid Alignment」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: 端点更新型のrun分割管理(dequeなどの端点操作でrun分割を更新し、左右の境界からの削除・追加と各要素の償却回数を説明できる。)。主タグ: 単調進行による償却解析 / 補助タグ: 端点更新型のrun分割管理
- ABC436 F「Starry Landscape Photo」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC437 F「Manhattan Christmas Tree 2」 公式問題主題: 幾何の基本判定と座標変換
技能・出典
主題: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。主タグ: 幾何の基本判定・配置・座標変換 / 補助タグ: 区間monoid要約
- ABC438 G「Sum of Min」 公式問題主題: gcd不変量・差分構造
技能・出典
主題: gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: gcd不変量・差分構造 / 補助タグ: event・値順のオフライン走査、Fenwick Tree・反転数・重み付き接頭辞統計
- ABC439 F「Beautiful Kadomatsu」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 疎なkeyの順序を保ってdense indexへ圧縮する(初期値・将来更新値・疎なevent座標をsort-uniqueし、順序と等値性を保つdense indexまたは有限状態へ写せる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 座標・値の順序保存圧縮、Fenwick Tree・反転数・重み付き接頭辞統計、法上の四則演算・高速累乗・逆元
- ABC444 E「Sparse Range」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 尺取り法・sliding window / 補助タグ: ordered set・multisetの動的順序管理
- ABC449 E「A += v」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: event・値順のオフライン走査 / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC449 F「Grid Clipping」 公式問題
技能・出典
主題: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。)。既習技能: 端点更新型のrun分割管理(区間の追加・削除に応じて重複被覆を管理し、active区間の和集合長を更新できる。具体的なbackendは採用解法が指定する場合に限って固定する。)。主タグ: event・値順のオフライン走査 / 補助タグ: 動的な区間和集合長
- ABC450 F「Strongly Connected 2」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 区間更新を要約へ作用させる(更新作用の合成順と要約への適用を定義し、遅延評価で保てる。)。主タグ: DPの最小十分状態 / 補助タグ: 遅延評価する区間作用
- ABC451 G「Minimum XOR Walk」 公式問題主題: XOR線形基底
技能・出典
主題: XOR線形基底(XOR部分空間の基底をpivot bitごとにreduced formへ整え、高位bitから基底を加減してaffine cosetの最小整数代表を一意に得る。正規化写像の線形性を示し、二値のXOR最小化を各値の正規化へ分離できる。)。既習技能: cycle space・fundamental cycle basis(spanning treeのroot-to-vertex XOR potentialで辺ラベルをfundamental cycleのXORへ変換し、cycle spaceの線形像が非木辺ごとのcycle XORのspanと一致することを示して、walkへ挿入できるXOR値をbasisで表せる。) / bit列をTrieで索引化する(整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。)。主タグ: XOR線形基底 / 補助タグ: binary Trieによるbit列索引、cycle space・fundamental cycle basis
- ABC452 E「You WILL Like Sigma Problem」 公式問題主題: 整数境界と同値区間を正確に分ける
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 累積和・差分配列
- ABC452 F「Interval Inversion Count」 公式問題
技能・出典
主題: 尺取り法・sliding windowで連続区間を走査する(一列の窓または二列の現在blockに関する不変条件を保ち、各pointerを単調に進められる。)。既習技能: 反転数・重み付き接頭辞統計をFenwick Treeで保つ(処理済み値の頻度から反転数を数えるか、必要な添字付き接頭辞統計を導き、Fenwick Treeの線形結合で式を評価できる。)。主タグ: 尺取り法・sliding window / 補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計
- ABC455 E「Unbalanced ABC Substrings」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。 - ABC463 G「Random Walk Distance」 公式問題主題: 組合せ係数と対称性で数える
技能・出典
主題: 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / Moの順序で区間問い合わせの差分を更新する(区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。)。主タグ: 組合せ係数・数え上げ / 補助タグ: Mo's algorithmによるオフライン区間問い合わせ、法上の四則演算・高速累乗・逆元
前提・学習成果・出典
導入対象の目安: 緑色(800–1199)。必要な操作と保持する情報を整理し、基本コンテナから区間構造へ進む入口。
対象色の読み方は本書の読み方を参照してください。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-query
習得する技能
- 問い合わせに十分で、更新と合成で保てる要約を導ける。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
問い合わせに必要な要約と更新規則を見抜く視点を先に学び、目的に合うデータ構造の選択へつなげる。
このUnitでは扱わないもの
- なし