ABC 418 F — We're teapots

考察

prefixのcoffee数が指定されている位置だけをactiveとする。隣接active p<iの間では位置p+1,…,iのcoffee数r=a_i−a_pが固定される。区間同士は境界のtea/coffeeだけで依存するので、二状態の行列へまとめられる。coffeeが隣接しないn位置へr個置く数をH(n,r)=C(n−r+1,r)とする。n≥0、0≤r≤ceil(n/2)以外は0、H(0,0)=1。選択位置から2件目以降の前の余白を一つずつ除く全単射がこの式を与える。

F(n,r)[s,t]は前端位置pがs(tea=0,coffee=1)、後端iがtで、間のn=i−p位置へr個coffeeを置く数。n≥3なら

F00=H(n−1,r)、F01=H(n−2,r−1)、F10=H(n−2,r)、F11=H(n−3,r−1)。

後端coffeeならrから一つ引き、その左隣をteaに固定する。前端coffeeなら区間先頭をteaにするので、それぞれ自由な位置が減る。短い区間ではこれらの強制teaが重なるため別に定義する。

n=1: F=[[ [r=0], [r=1] ], [ [r=0], 0 ]]
n=2: F=[[H(1,r), H(0,r−1)], [H(0,r), H(0,r−1)]]

特にn=1のF11は隣接coffeeになるので0。r<0など不可能な差なら全成分0となる。

a_0=0をsentinelとし、active iの葉へ、直前active pに対応するF(i−p,a_i−a_p)を置く。inactiveの葉は単位行列。row vectorを左から掛ける規約で、初期(1,0)へactive順の行列積Mを掛ける。最後のactiveをk(なければ0)、残り長m=N−kとする。制約なしsuffixの非隣接選択数をfib[0]=1,fib[1]=2,fib[m]=fib[m−1]+fib[m−2]とすれば、回答は

M00·fib[m]+M01·fib[max(m−1,0)]。

前端teaならm位置が自由で、coffeeなら次の一位置をteaにする。m=0ではどちらの終端状態も一通りである。

更新a_x←yでは、現在のactive xをいったん削除して葉を単位行列に戻し、次のactiveの葉を新しい前端から再計算する。y≠−1ならxを挿入して、その葉と次activeの葉を再計算する。前後activeはordered setから得る。影響はxと直後だけなのでO(log N)。毎回全prefixを再DPするO(NQ)以上の方法を、この区間依存の局所性で避けられる。

典型の発動条件

境界状態のtransfer matrix

発動条件: 列を区間分割したとき、隣接禁止の依存が左右endpointの有限状態だけに残るとき。

各制約間をtea/coffeeの2×2matrixにし、順序積で全prefixを合成する。

動的非可換積segment tree

発動条件: 列中の少数matrixが点更新され、全順序積を毎回求めたいとき。

identityをinactive位置に置き、mergeをleftMatrix×rightMatrixとする。

ordered setの前後制約

発動条件: active indexの追加削除で隣接区間分割だけが変化するとき。

predecessor/successorを探し、該当二matrixを張り替える。

問題固有の要素

prefix count制約を差分区間のexact coffee数へ変え、隣接禁止の跨ぎ情報をendpoint二bitだけに圧縮する。

別の問題へ持ち帰る視点: 動的prefix制約ではactive制約間のtransferを辺とみなし、頂点挿入削除が隣接辺だけを変更する構造を使う。

正当性

active間のcoffee個数差は元のprefix条件と同値であり、各位置をちょうど一つの区間へ所属させる。端点のtea/coffeeを固定すると、隣接禁止で自由位置を除いた残りをHで一度数えられる。n=1,2では強制位置の重複を別扱いするので境界でも正しい。row vectorと行列の積で境界状態の全接続を足し合わせ、最後の自由suffixをfibで合成した回答式が全合法配置数になる。activeの挿入・削除ではxと直後の区間だけが変わるので、この二葉の再計算で積の不変量を維持できる。

実装上の注意

  • H(0,0)=1、不可能なcoffee数は0。n=1,2を別扱いし、負の長さをbinomialへ渡さない。
  • row vector規約なので木の結合は左行列×右行列。sentinel位置0はteaでcoffee数0。
  • 最後のactiveがなくてもk=0、全行列が単位元となりfib[N]を返す。削除後と挿入後のsuccessorを再計算する。

復習の核

  • active制約なし、一点制約、矛盾するcount差、隣接二indexをともにcoffee指定、制約解除で区間が再結合する例を全bit列挙と比較する。

計算量と制約

時間

前計算O(N)、Q更新O(Q log N)、固定2×2行列。

空間

O(N)、階乗・逆階乗・fib・制約木。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq X_j \leq N (1 \leq j \leq Q); -1 \leq Y_j \leq X_j (1 \leq j \leq Q); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

We're teapots の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 区間monoid要約

    補助タグ: ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: 区間monoid要約

    • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    先に読む単元:

    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題