ABC 466 G — Segment Sum Constraints

考察

変数は8個以下でも、それぞれの値は大きいので、値の組を直接列挙することはできない。一方、加算を二進数の下の桁から行えば、過去の桁から必要なのは繰り上がりだけになる。ただし、すべての区間和について繰り上がりを持つと状態が増えすぎる。まず累積和の差として条件を整理し、残した式の繰り上がりを同時に追う。

正整数という下限を扱いやすくするため、ui=Ai−1u_i=A_i-1 と置く。入力の条件 mm の右辺を Tm=Sm−(Rm−Lm+1)T_m=S_m-(R_m-L_m+1) に変えれば、求めるのは非負整数列の区間和である。Tm<0T_m<0 なら答えは0。累積和を B0=0, Bi=∑h=1iuhB_0=0,\ B_i=\sum_{h=1}^{i}u_h とすると、各条件は BRm−BLm−1=TmB_{R_m}-B_{L_m-1}=T_m となる。

添字 0,…,N0,\ldots,N を頂点、入力の差等式を辺とみなし、重み付きDSU(weighted DSU)で成分と相対差を管理する。頂点 vv の potential を wv=Bv−Broot(v)w_v=B_v-B_{\mathrm{root}(v)} と定めると、既に同成分である二点への条件は wRm−wLm−1=Tmw_{R_m}-w_{L_m-1}=T_m かを調べればよい。食い違えば答えは0である。

次に、各成分の添字を昇順に並べ、その中で隣り合う二点だけを結ぶ。抽出した式を j=1,…,qj=1,\ldots,q と番号付けし、その両端を pj<rjp_j<r_j と書くと、

∑i=pj+1rjui=Sj′,Sj′=wrj−wpj,ℓj=rj−pj\sum_{i=p_j+1}^{r_j}u_i=S'_j, \qquad S'_j=w_{r_j}-w_{p_j},\qquad \ell_j=r_j-p_j

を残せばよい。ℓj\ell_j はこの区間の長さである。元の辺の両端は同成分なので、成分内の隣接差を足すと元の条件を戻せる。逆に、抽出した差も元の条件から決まるため、この置き換えは必要十分である。成分数を kk とすると、残る式は各成分の頂点数より一つ少ないので、全体で q=N+1−k≤Nq=N+1-k\leq N 本となる。

ここで、抽出した右辺もすべて非負か調べる。入力時の右辺が非負でも、例えば u1=9, u1+u2=3u_1=9,\ u_1+u_2=3 から得る u2=−6u_2=-6 は不可能であり、DSUの差等式としては矛盾しない。以降は Sj′≥0S'_j\geq0 とする。

一つの式の桁加算から考えよう。独自の小例 u1+u2=2u_1+u_2=2 で u1=u2=1u_1=u_2=1 を選ぶと、最下位bitの和は2、目標の最下位bitは0なので、次の桁へ1を繰り上げる。次の桁では変数のbitは両方0だが、前の桁から来た1が目標のbitの1と一致し、繰り上がりが0へ戻る。下位桁の合計そのものを保存せず、この「目標との差を次の桁の単位で測った値」を持てばよい。

一般に、下位 bb bitを決めた段階で、式 jj について

∑i=pj+1rj(ui mod 2b)≡Sj′(mod2b)\sum_{i=p_j+1}^{r_j}(u_i\bmod 2^b) \equiv S'_j\pmod{2^b}

を満たす部分的な選び方だけを残す。その繰り上がり(carry)を

Cj=∑i=pj+1rj(ui mod 2b)−(Sj′ mod 2b)2bC_j=\frac{\displaystyle\sum_{i=p_j+1}^{r_j}(u_i\bmod 2^b)-(S'_j\bmod 2^b)}{2^b}

と定義する。合同条件から分子は 2b2^b の倍数である。また、各剰余は 0,…,2b−10,\ldots,2^b-1 なので、分子は −2b-2^b より大きく、ℓj2b\ell_j2^b より小さい。従って整数である CjC_j は 0≤Cj<ℓj0\leq C_j<\ell_j を満たす。目標の下位部分を引いていても負のcarryが不要なのは、この整数倍という条件による。

続いて、各変数のbit bb(2b2^b の位)を xi∈{0,1}x_i\in\{0,1\} として選び、式内のbit和を aj=∑i=pj+1rjxia_j=\sum_{i=p_j+1}^{r_j}x_i、目標のbitを sj=⌊Sj′/2b⌋ mod 2s_j=\lfloor S'_j/2^b\rfloor\bmod2 とする。下位 b+1b+1 bitでの差は

2b(Cj+aj−sj)2^b(C_j+a_j-s_j)

だから、次の桁まで合同条件を保てるのは Cj+aj−sjC_j+a_j-s_j が偶数のときに限る。そのとき次のcarryは

Cj′=Cj+aj−sj2C'_j=\frac{C_j+a_j-s_j}{2}

となる。先ほどの小例では、最初は C=0, a=2, s=0C=0,\ a=2,\ s=0 から C′=1C'=1、次は C=1, a=0, s=1C=1,\ a=0,\ s=1 から C′=0C'=0 と計算できる。

複数の式でも、同じ変数のbit選択を共有して、各式のcarryを並べたベクトル C=(C1,…,Cq)\mathbf C=(C_1,\ldots,C_q) を状態にすればよい。各式に ℓj\ell_j 通りの候補があるので、ベクトルの候補数は

C=∏j=1qℓjC=\prod_{j=1}^{q}\ell_j

で抑えられる。ただし、式を高々 NN 本に減らしただけで、この積が1024以下になるわけではない。ここからは、同成分の隣接添字の間隔(gap)だけを使って式を作ったことが効く。

各成分の最初と最後の添字をそれぞれ fc,tcf_c,t_c(c=1,…,kc=1,\ldots,k)とする。同じ成分内のgapを足すと両端の差になるため、

∑j=1qℓj=∑c=1k(tc−fc)≤k(N+1−k)=kq\sum_{j=1}^{q}\ell_j=\sum_{c=1}^{k}(t_c-f_c) \leq k(N+1-k)=kq

が成り立つ。実際、最初の添字は互いに異なるので合計は少なくとも 0+⋯+(k−1)0+\cdots+(k-1)、最後の添字も互いに異なるので合計は高々 (N−k+1)+⋯+N(N-k+1)+\cdots+N であり、その差が k(N+1−k)k(N+1-k) である。従って q>0q>0 なら、相加相乗平均の不等式から

C≤(∑jℓjq)q≤kq≤k9−kC\leq\left(\frac{\sum_j\ell_j}{q}\right)^q \leq k^q\leq k^{9-k}

を得る。最後で N≤8N\leq8 を使った。q=0q=0 ならcarryベクトルは空の一通りだけである。成分数ごとの上界は次のとおりで、最大は1024となる。

成分数 kk123456789
上界 k9−kk^{9-k}112872910246252164981

この上界は実際に達する。N=8N=8 で添字 0,…,80,\ldots,8 の成分番号を (0,1,2,3,0,1,2,3,0)(0,1,2,3,0,1,2,3,0) とすると、抽出するgapは (0,4),(4,8),(1,5),(2,6),(3,7)(0,4),(4,8),(1,5),(2,6),(3,7) の五つで、長さの積は 45=10244^5=1024 である。これはcarryの候補数の上界であり、特定の右辺で全候補へ到達するという意味ではない。この成分分割による論証は本解説で補ったもので、任意の加算式を qq 本選んだ場合へそのまま転用できない。

あとは、dpb[C]dp_b[\mathbf C] を「下位 bb bitまで合同条件を満たし、carryが C\mathbf C となる選び方の数」とする。dp0[0]=1dp_0[\mathbf0]=1、他は0で開始する。各桁で各変数のbitを一つの NN bitのmaskで選び、すべての式の偶奇検査を通るmaskだけで次のベクトルへ個数を加える。異なるmaskが同じ次状態へ移る場合も、それぞれの選び方として加算する。更新先は次の層に分ける。

条件に登場する非負変数は、それを含む元の区間和の右辺以下だから 109<23010^9<2^{30} に収まる。抽出した右辺も同じ上限に収まる。各抽出区間は元のいずれかの入力区間に含まれるためである。同成分内の隣接二点の間で頂点を左右に分けると、成分をつなぐ元の辺が必ずこの境界をまたぐ。その元の区間和は抽出した非負の区間和を足したものなので、各項は元の右辺以下となる。

従ってbit 0,…,290,\ldots,29 を処理すればよい。ただし、30bitで合同なだけでは等式とは限らない。例えば u1=u2=229, S′=0u_1=u_2=2^{29},\ S'=0 は下位30bitの和が目標と一致するが、和は 2302^{30} なので最終carryが1となり、解ではない。答えとして取り出すのは dp30[0]dp_{30}[\mathbf0] だけである。

未登場変数がある場合は、DPではそのbitを常に0へ固定する。登場変数に一つでも解があれば、未登場変数をいくらでも増やせるので Infinity、解がなければ0となる。全変数が登場するなら解数は有限である。解数は 998244353998244353 で割った余りを持つが、剰余0でも実際の解数が0とは限らないため、存在boolを別に持つ。初期状態のboolを真とし、到達可能な状態からの合法遷移では次状態を真にする。個数の剰余が0の状態も、boolが真なら遷移を続ける。

典型の発動条件

weighted DSUの差制約

発動条件: 区間和を累積和の差へ変換でき、差等式の整合性と、同成分内の別の二点の差を求めたいとき。

根に対するpotentialを持ち、既に同成分の二点へ追加する差を既存の差と照合する。ただし、差等式の整合性だけでは変数の非負条件までは保証しない。

加算式のbitwise carry DP

発動条件: 大きな値域を持つ少数の非負変数について、複数の加算式を同時に満たす組を数えたいとき。

下位bitでの合同条件を保ちながら、各式のcarryだけを次の桁へ渡す。各carryが小さくても、その候補数の積が小さいかを別に確認する。変数の範囲は式から抑えるため、数値上限との一致を追うtight flagは持たない。

問題固有の要素

累積和の成分ごとに、添字順で隣り合う二点の差を残す。この選び方なら式の数を減らすと同時に、各式の区間長を成分のgapとして評価できる。状態数の1024という上界は、独立な式の本数だけでなく、この選び方と N≤8N\leq8 の両方に支えられている。

正当性

非負化は元の正整数解との全単射である。DSUで差の矛盾を検査した後、成分内の隣接する累積和の差を残す置き換えは必要十分であり、入力時・抽出時の負の右辺は非負解を持たないので排除できる。

DPは下位 bb bitでの合同条件と、その差を 2b2^b で割ったcarryを保つ。合同条件と剰余の範囲により各carryは 0,…,ℓj−10,\ldots,\ell_j-1 に収まる。偶奇検査は次の桁まで合同条件を保つための必要十分条件であり、次carryの式はその差を 2b+12^{b+1} で割った値である。各変数のbit列とmaskの列は一対一に対応するので、合法遷移をすべて加算すると漏れも重複もない。同成分の隣接添字のgapを使うため、成分数ごとの積の評価からcarry候補数は1024以下となる。

登場変数と抽出した目標は 2302^{30} 未満なので、30bit後に全carryが0であることと、整数としてすべての等式を満たすことは同値である。未登場変数を0に固定しても可解性は変わらず、登場変数に一解があれば未登場変数の任意の増加により解は無限個となる。存在boolを剰余個数とは別に更新するので、解数が法の倍数でもこの判定を誤らない。

実装上の注意

  • 非負化した入力目標と、隣接する累積和から抽出した全目標の両方を検査し、負なら0を出す。potentialの加減算には64 bit整数を使う。
  • 長さ ℓj=1\ell_j=1 の式はcarryが0の一通りだけとなる。各carryを基数 ℓj\ell_j の桁として配列添字へ符号化すれば、候補をちょうど CC 個の配列で持てる。
  • 30桁後に全carryが0の状態だけを取る。未登場変数のbitは0に固定し、剰余個数が0でも存在boolが真の状態は捨てない。

復習の核

  • 下位桁を決めた後に何を次の桁へ渡すかは、「左辺の下位部分と目標の下位部分の差」から導く。
  • 状態をベクトルにするときは、各成分の小ささだけでなく候補数の積を評価する。本問では成分内の隣接gapという式の選び方が鍵になる。
  • 最後のcarryと、解数の剰余・存在判定を区別する。合同条件だけ、剰余0だけで終了判定をしない。

計算量と制約

時間

入力式数を MM、抽出式数を q≤Nq\leq N、bit数を B=30B=30、carry候補数を C≤1024C\leq1024 とする。DSUでの差の整理と隣接差の抽出に O(Mα(N)+N2)O(M\alpha(N)+N^2)、各maskの式内bit和の前計算に O(2NqN)O(2^NqN)、直接のDP遷移に O(BC2Nq)O(BC2^Nq) かかる。全体はこれらの和である。carryを基数の異なる桁として配列へ符号化すれば確定的な評価となり、hash表を使う場合は期待計算量となる。

空間

DPの現在・次の層と存在boolに O(C)O(C)、maskごとの式内bit和に O(2Nq)O(2^Nq)、入力・DSU・抽出式に O(N+M)O(N+M) を使う。従って全体は O(C+2Nq+N+M)O(C+2^Nq+N+M)。ここでは全状態の遷移表は保持せず、各桁で直接遷移を計算する。

制約との対応

公式制約は 1≤N≤8, 1≤M≤36, 1≤Li≤Ri≤N, 1≤Si≤1091\leq N\leq8,\ 1\leq M\leq36,\ 1\leq L_i\leq R_i\leq N,\ 1\leq S_i\leq10^9 で、区間の組は互いに異なる。時間制限2秒、メモリ制限1024 MiB。変数の値域全体を列挙せず、30桁・高々1024状態・各桁高々 282^8 個のmaskに分ける。直接遷移でも式ごとの検査は高々 30⋅1024⋅28⋅830\cdot1024\cdot2^8\cdot8 回程度である。未登場変数には有限上限がないため、30桁の列挙に含めず0に固定して可解性を判定する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Segment Sum Constraints の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 繰り上がり・借り・混合基数を状態にするDP

主題
追加で学ぶ技能
  • potential・weighted DSU: DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。
既習技能
    なし

    主タグ: 繰り上がり・混合基数DP potential・weighted DSU

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 繰り上がり・借り・混合基数を状態にするDP

    • 整除鎖の端数または加算式を下位桁から処理し、切り上げ・切り下げや次桁へのcarryだけを状態にした遷移を設計できる。
    • DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。

    先に読む単元:

    この解説で扱わないこと:

    • 数値上限とのtight flagや文字列pattern状態を接頭辞から更新する桁・automaton DP。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題