ABC 270 Ex — add 1

考察

counter vector Cの進捗をk=max_i(A_i−C_i)へ圧縮すると、k=0が終了条件で、次状態は具体的なCではなくkだけから定まる。Aは昇順でA_1=0。A_r<k≤A_{r+1}なら、選んだindexがi≤rのとき次状態k−1、i>rのときA_iになる。

x_kを状態kからの期待残り回数とすると、

x_k=1+(r/N)x_{k−1}+(1/N)Σ_{i>r}x_{A_i}、x_0=0。

この式は大きい添字を参照し、全整数状態を消去してもA_N≤10^18では幅が大き過ぎる。y_k=x_{A_N}−x_kとおけば、既知のy_{A_N}=0から降順に進められ、回答はy_0=x_{A_N}になる。

s_r=Σ_{i>r}y_{A_i}を固定して変形すると、

y_{k−1}=(N/r)y_k+(N−s_r)/r。

r<Nなのでc_r=(N−s_r)/(N−r)と置ける。するとy_{k−1}+c_r=(N/r)(y_k+c_r)になり、同じrを持つΔ=A_{r+1}−A_r段を一度に飛ばして

y_{A_r}=(N/r)^Δ(y_{A_{r+1}}+c_r)−c_r

と求められる。ここで割り算と累乗は法998244353上で行う。

y_{A_N}=0,s=0からr=N−1,…,1の順に、c=(N−s)/(N−r)、上のジャンプ式、s←s+y_{A_r}を実行する。最後にy_{A_1}=y_0を返す。A_iが重複してもΔ=0で同じyを得て、sには添字ごとに一回ずつ加える。rとN−rは1以上N未満で法より小さいため逆元が存在する。

各gapの二分累乗でO(log A_N)、逆元前計算を使えば全体O(N log A_N)。最大不足量による状態圧縮と、区分的に一定な係数の漸化式をaffine shiftで幾何級数へ変える方法が再利用できる。

典型の発動条件

確率過程の状態圧縮

発動条件: 高次元状態でも終了までの遷移分布が一つのpotentialだけで決まるとき。

全counterの不足量の最大値kだけを状態とし、reset対象のA_iから次状態を分類する。

一次漸化式の区間累乗

発動条件: 長大なindex区間でaffine recurrenceの係数が変化しないとき。

定数項をshiftして等比漸化式にし、A_{r+1}−A_r段をmodular powerで一括遷移する。

問題固有の要素

rはA_i<kを満たすcounter数であり、Aの値を跨がない間はtransition probabilityとreset先集合が一定である。

別の問題へ持ち帰る視点: 巨大な数直線上のDPは、transition ruleが変わるevent pointsだけを列挙し、同一区間をclosed formで飛ばす。

正当性

最大不足量kに対する一歩の次状態は、選んだ添字がr以下か否かだけで決まり、xの式は全確率の分割である。y=x_{A_N}−xと置くと最高状態の初期値が0になり、降順の漸化式が得られる。区間内ではs_rが一定なのでc_rを足す変形で倍率N/rの更新になり、Δ段の累乗は一段更新の反復と等しい。sを各breakpointの計算後に更新すれば、次区間でも必要なΣ_{i>r}y_{A_i}が維持される。最後のy_0はx_0=0より求めるx_{A_N}そのものである。

実装上の注意

  • Aに重複があってgapが0でも降順index処理を保ち、s_rへy_{A_{r+1}}を正しい時点で追加する。
  • inverseを取るrとN−rは1,…,N−1なのでmodulusより小さく非零であることを利用する。

復習の核

  • 多次元random processでは、終了条件を表すpotentialが次状態の分布まで決めるかを検証する。
  • 漸化式の向きが初期条件と逆なら、求める端点との差を新変数にして計算方向を反転する。

計算量と制約

時間

O(N log Amax)、N breakpoint間のmodular累乗。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2\leq N\leq 2\times 10^5; 0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}; A_N>0; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

add 1 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 確率過程・期待値DP

主題
  • 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 確率・期待値DP

    補助タグ: 線形遷移・行列累乗 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 確率過程・期待値DP

    • 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。

    先に読む単元:

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

    • 二人零和ゲームの勝敗・Grundy数。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題