整数境界と同値区間を正確に分ける
概要
整数境界・同値区間分割
floor値・整数根・表記桁数・圧縮block内の式が変わる整数境界を正確に分け、区間ごとに処理する。
商q=floor(N/l)が一定の最大区間は[l,floor(N/q)]である。右端の次へ進めば、i≤√Nの部分と商≤√Nの部分を合わせてO(√N)個のblockだけを処理できる。三角数・整数根・桁数の境界も、式が変わる位置を整数演算で求める。
一次式の床和を格子点領域の転置で計算するfloor_sumは別の原理である。商一定区間の列挙と混ぜず、「格子点転置によるfloor_sum」の節で引数の減少と重み付き和への拡張を学ぶ。
考え方
floor(N/i)はiが増えると非増加で、同じ商qを持つ最後の位置はfloor(N/q)になる。値が一定のblockをまとめて数えると、巨大な整数範囲を直接列挙せず集計できる。
一次・二次のblockと交点を整数へ戻す
整数域[L,R]でax+b≥0を判定すると、a>0ならx≥ceil(−b/a)、a<0ならx≤floor(−b/a)。a=0は全成立か全不成立である。この切替位置とその次を境界へ入れ、全条件の境界をsort・uniqueすれば各半開区間内の真偽は一定となる。平方根・三角数の境界は候補kに対するk²≤Nやk(k+1)/2≤Nを整数で再確認して求める。
圧縮block内の値がf(x)=ax²+bx+cなら、最大・最小の候補は両端と頂点−b/(2a)のfloor・ceilを域内へ絞った点である。順位を探すなら頂点で単調な二区間へ分け、各区間の成立数を二分探索する。a=0は一次式として扱い、二次式が区間全体で単調とは仮定しない。
一次関数群のmin/max包絡では二本の差も一次式で、優劣は高々一回しか変わらない。各交点のfloor・ceilと前後の整数を候補境界へ含める。同傾きは常に優る切片だけを残す。境界間では選ばれる直線が一定なので、inclusiveな[L,R]の和は a·(L+R)(R−L+1)/2+b·(R−L+1)。素朴な全対交点ならO(直線数²)候補を使い、直線包絡の専用構造がある場合はその有効blockだけを使う。商のO(√N)評価を別の式へ流用しない。
成立条件と計算量
正のNでは相異なる商はO(√N)個。lからq=N/l、r=N/qを求めr+1へ進む。0除算、N=0、block長と元座標の重みを確認する。別の床式にはその式に合う境界を導く必要がある。
問題一覧
- ABC230 E「Fraction Floor Sum」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: 整数境界・同値区間分割
- ABC414 E「Count A%B=C」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: 整数境界・同値区間分割
- ABC452 E「You WILL Like Sigma Problem」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 累積和・差分配列
- ABC356 E「Max/Min」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: 整数境界・同値区間分割
- ABC240 F「Sum Sum Max」 公式問題組合せ: 一次元凸・単峰最適化
技能・出典
主題: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 一次元凸・単峰最適化
- ABC293 F「Zero or One」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: 整数境界・同値区間分割
- ABC318 F「Octopus」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(成立判定が変わり得る整数境界を全て列挙し、隣り合う境界の間で判定が一定であることを示して、代表点判定と区間長で整数解の個数を求められる。)。既習技能: 二部matching・Hall・Kőnig(二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 二部matching・Hall・Kőnig、貪欲法と交換論
- ABC253 G「Swap Many Times」 公式問題
- ABC239 Ex「Dice Product 2」 公式問題
技能・出典
主題: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 確率過程・期待値DP(状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 法上の四則演算・高速累乗・逆元、確率・期待値DP
- ABC429 G「Sum of Pow of Mod of Linear」 公式問題組合せ: 固定線形遷移を巨大回数進める
技能・出典
主題: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 線形遷移・行列累乗
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC216 E「Amusement Park」 公式問題主題: 分離凸・凹の単調限界値選択
技能・出典
主題: 分離凸・凹の単調限界値選択(分離凸費用または分離凹利益を単調な限界値列へ分解し、heap mergeか閾値別の個数・総和により必要な上位・下位K項を選べる。)。既習技能: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。) / 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。主タグ: 分離凸・凹の単調限界値選択 / 補助タグ: 整数境界・同値区間分割、単調境界探索
- ABC243 G「Sqrt」 公式問題
技能・出典
主題: DP遷移を因数分解・集約して加速する(遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。)。既習技能: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。 二段先iを固定して中間状態数を数えるとΣ_{i≤r}(s+1−i²)dp[i]になる(s=⌊√X⌋,r=⌊√s⌋)。P0=Σdp、P2=Σi²dpを持てば(s+1)P0[r]−P2[r]で答えられる。主タグ: DP遷移の集約・高速化 / 補助タグ: 整数境界・同値区間分割
- ABC303 F「Damage over Time」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 整数境界と同値区間を正確に分ける(整数区間上の一次関数包絡を交点の前後で分け、各affine blockの値を等差数列和で合計できる。)。主タグ: 単調境界探索 / 補助タグ: 整数境界・同値区間分割
- ABC361 F「x = a^b」 公式問題
技能・出典
主題: 約数格子のzeta・Möbius反転(約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: 約数格子のzeta・Möbius反転 / 補助タグ: 整数境界・同値区間分割
- ABC370 G「Divisible by 3」 公式問題
技能・出典
主題: Min_25・Lucy DP型の総和篩(素数和を定数個のLucy DPで求められる乗法的関数について、floor(N/i)の商集合上で素数冪を逆順に追加する簡略版Min_25でprefix sumを求める。素数冪の評価がO(1)なら、O(N^(3/4)/log N)時間・O(√N)空間。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 整数境界と同値区間を正確に分ける(floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。)。主タグ: Min_25・Lucy DP型の総和篩 / 補助タグ: 整数境界・同値区間分割
- ABC444 F「Half and Median」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。)。主タグ: 単調境界探索 / 補助タグ: 整数境界・同値区間分割
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。床関数や整数根が変わる境界を厳密に求め、同じ値の区間をまとめる。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-integer-boundary-blocks
習得する技能
- 圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。
- 成立判定が変わり得る整数境界を全て列挙し、隣り合う境界の間で判定が一定であることを示して、代表点判定と区間長で整数解の個数を求められる。
- floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。
- 整数区間上の一次関数包絡を交点の前後で分け、各affine blockの値を等差数列和で合計できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
floorや整数根の値が変わる境界を正確に求め、同値な整数範囲をまとめて処理する。
このUnitでは扱わないもの
- 素因数指数による整数条件の分解。