AtCoder Beginner Contest 292 G,Ex問題メモ

G - Count Strictly Increasing Sequences

問題

$N$ 個の長さ $M$ の数字列 $S_1,...,S_N$ があり、一部の文字は '?' で隠されている
全ての '?' を独立に '0'～'9' に置き換える
置き換える方法のうち、 $S_1 \lt S_2 \lt ... \lt S_N$ となるものが何通りあるか、 $\mod{998244353}$ で求めよ
- 先頭が'0'であってもよい
$1 \le N,M \le 40$

解法

深さのある区間DP。
制約の小さな問題は、階層の深いDPである可能性が高いので、組み立て方の自由度が高い分難しい。

大小が関係あるので、桁DPっぽく上の桁から'?'を確定させていきたくなるが、その場合は「 $S_i$ は、 $S_{i-1}$ より大きいことが確定しているので次の桁には何を置いてもよい」のか、「まだ確定していないので次の桁には $S_{i-1}$ 以上の数字を置かないといけない」のか、管理しないと決められない。

だが、 $S_{i-1}$ 自体も、 $S_{i-2}$ より大きいことが確定している場合と未確定の場合で、上の桁の状態が変わり、次の桁における数字も異なってきて、とても上手くまとめて管理できない。

「上位桁から見ていって、 $k$ 桁目の前までまだ $S_l～S_{r-1}$ の範囲の大小関係が区別できていない」という状態を管理して、これを再帰的に分割していくことを考える。

           k
Sl    XXXX ? ???
Sl+1  XXXX ? ???
Sl+2  XXXX ? ???
Sl+3  XXXX ? ???
 :
Sr-2  XXXX ? ???
Sr-1  XXXX ? ???
      ~~~~
      同じ

$S_l$ から続く何個かの $k$ 桁目をまとめて決めると、

           k
Sl    XXXX 4 ???
Sl+1  XXXX 4 ???
 :
Sx-1  XXXX 4 ???
Sx    XXXX ? ???
 :
Sr-1  XXXX ? ???

$[l,x)$ と $[x,r)$ の区間に分けられ、後者の区間の値に制約を持たせれば、この2区間の間の大小関係は確定する。

           k k+1
Sl    XXXX 4  ? ??  ┐
Sl+1  XXXX 4  ? ??  │[l, x) が k+1 桁目の前まで同じ
 :                  │
Sx-1  XXXX 4  ? ??  ┘
Sx    XXXX ?  ? ??  ┐[x, r) が k 桁目の前まで同じ
 :                  │ただし Sx の k 桁目は '5' 以上
Sr-1  XXXX ?  ? ??  ┘

よって、以下の関数を定義してやれば、

$f(l,r,k,d)=S$ の $[l,r)$ の範囲が上位 $k-1$ 桁までは同じで、 $S_l$ の $k$ 桁目は $d$ 以上である場合に、 $k$ 桁目以降の '?' の決め方で、 $[l,r)$ 内の全ての大小関係が昇順に確定する場合の数

上の例は、 $f(l,r,k,d)$ を、 $f(l,x,k+1,0)$ と $f(x,r,k,5)$ に分割したことになる。

$f(0,N,0,0)$ が答えとなる。ここからはじめて再帰的に答えを求めていく。
何度も同じ係数が呼ばれうるため、 $f()$ はメモ化再帰で実装する。

遷移を考えると、

$[l,x)$ （ $x=l+1,...,r$ ）の範囲の $k$ 桁目に $d$ を配置する
- $f(l,r,k,d) += f(l,x,k+1,0) \times f(x,r,k,d+1)$
- $[l,x)$ の $k$ 桁目に1つでも、 $d$ 以外の数字がある場合は不可
$S_l$ の $k$ 桁目に置くのを $d+1$ 以上にする
- $f(l,r,k,d) += f(l,r,k,d+1)$

終端条件は、

$l=r$ なら $1$ （遷移で $x$ として $r$ を選んだとき用）
$d \ge 10$ なら $0$
$k=M$ まで進んだとき、
- $[l,r)$ の長さが1なら $1$
- そうでないなら全く同じ複数の $S_i$ ができてしまったということなので $0$

計算量は、 $f()$ の状態数が $O(N^2MD)$ （ただし $D$ は文字種数 $=10$ ）、遷移に $O(N)$ なので、 $O(N^3MD)$ となる。

Python3

Ex - Rating Estimator

問題

あなたはこれから $N$ 回のコンテストに参加し、それぞれで $a_1,...,a_N$ のパフォーマンスを得る予定である
レーティングという値がある
- 各コンテスト終了後、それまでに参加したコンテストのパフォーマンスの平均値で更新される
- ただしレーティングが一度でも $B$ 以上になると、それ以降は変動しない
$Q$ 個のクエリが与えられる
- $c_i,x_i$ が与えられる
- 獲得予定のパフォーマンス $a_1,...,a_N$ のうち、 $a_{ci}$ を $x_i$ に（永続的に）変更する
- その上で、 $N$ 個のコンテストで予定通りのパフォーマンスが得られた場合の最終的なレーティングを求めよ
$1 \le N \le 5 \times 10^5$
$0 \le a_i,x_i,B \le 10^9$

解法

AtCoderのレーティングと似たような設定で題意はわかりやすい。（レーティングの算出方法は違うが）

平均の変換

セグメント木などで区間の“平均”を管理しようと思うと、 $[l,r)$ の和とその長さ $r-l$ を持つことになる。

ただし、「平均がある決まった1つの値 $B$ より大きいか小さいか」の判定だけなら、載せる値から一律に $B$ を引いておくことで、「区間和が $0$ より大きいか小さいか」だけで判定でき、長さを省略できて楽になる。

セグメント木で管理する値

$b_i=a_i-B$ とし、 $b_i$ をセグメント木で管理する。

今回の問題では、「一番始めに $b_1+b_2+...+b_i$ が $0$ 以上になる $i$ 」を求めたい。

もしそのような $i$ があるなら、答えは $\dfrac{b_1+b_2+...+b_i}{i}+B$
ないなら、答えは $\dfrac{b_1+...+b_N}{N}+B$

なので、 $b_i$ の「先頭からの累積和」と、さらにその「累積和の先頭からの累積MAX」を同時に管理したい。
累積和は $b_i$ の値によって上下するためはじめて $0$ 以上が出現する位置を特定しづらいが、累積MAXを取っておけば、それを参照して二分探索が可能になる。

各セグメント木のノードに、(その区間の和, その区間の中での先頭からの累積和のMAX) を載せればよい。
ノード $n$ に対して、それぞれ $n[0],n[1]$ とする。

ノード $L$ と $R$ をマージするとき、

区間和は普通に $L[0]+R[0]$
累積和MAXは $\max(L[1],L[0]+R[1])$

$R$ の部分の累積MAXは、マージすると $L$ の区間和分だけスタート位置がずれるので、 $L[0]+R[1]$ で求められる。

セグメント木上の二分探索

クエリ $c_i,x_i$ に対して、更新作業は、 $b_{ci}$ の値を $(x_i-B,x_i-B)$ で上書きする、という操作になった。

あとは、累積MAXが最初に $0$ 以上になる位置を二分探索で求めたい。

セグメント木に区間クエリ $[1,i)$ を何度か投げて $i$ を二分探索してもよいが、それだと1回毎に $O(\log^2{N})$ かかる。
速い言語なら間に合うかも？だが、制約の大きさから、厳しめに設定してあるように感じる。

ここでは、セグメント木に投げるクエリではなく、直接的にセグメント木上で二分探索を行う。

一度でも累積和が $0$ 以上となるか否かは根ノードを参照すれば簡単に分かるので、どこかでは $0$ 以上となる場合のみを考える。

今いるノードを $n$ とし、根ノードからスタート
左の子の累積MAX $L[1]$ が0以上なら、答えは左にある→左ノードへ $n←L$
左の子の累積MAX $L[1]$ が0未満なら、答えは右にある→右ノードへ $n←R$
- また、自身より左の区間の総和 $L[0]$ を $LS$ に記録しておく

根以降は、自身より左の区間の総和も含めて累積MAXを計算する必要があるので、

$LS+L[1]$ が0以上なら、左ノードへ
$LS+L[1]$ が0未満なら、 $LS$ に $L[0]$ を加算し、右ノードへ

これを繰り返して、 $n$ が葉になったらその位置が、累積MAXが最初に $0$ 以上となる位置となる。

これなら $O(\log{N})$ で求められ、全体で $O(N+Q\log{N})$ となる。

Python3

        
          
          
              
              from itertools import accumulate
from operator import add
 
 
class SegmentTreeInjectable:
    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory
 
    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins
 
    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)
 
    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)
 
    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            if i & 1:
                tree[i >> 1] = func(tree[i ^ 1], tree[i])
            else:
                tree[i >> 1] = func(tree[i], tree[i ^ 1])
            i >>= 1
 
    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()
 
        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1
 
        return func(result_l, result_r)
 
    def get_all(self):
        return self.tree[1]
 
    def get_point(self, i):
        return self.tree[i + self.offset]
 
    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1
 
    def leftmost2(self, b):
        """ ABC292-Ex問題に特有の二分探索関数 """
        tree = self.tree
        l = 0
        r = self.offset
        i = 1
        left_sum = 0
        while l + 1 < r:
            m = (l + r) >> 1
            lch = i << 1
            rch = lch | 1
 
            if left_sum + tree[lch][1] >= 0:
                r = m
                i = lch
                continue
 
            if m < b:
                if left_sum + tree[lch][0] + tree[rch][1] >= 0:
                    l = m
                    i = rch
                    left_sum += tree[lch][0]
                    continue
            return -1
        return l
 
 
n, b, q = map(int, input().split())
aaa = list(map(int, input().split()))
INF = 1 << 60
 
 
def func(x, y):
    return (x[0] + y[0], max(x[1], x[0] + y[1]))
 
 
aaa_init = [(a - b, a - b) for a in aaa]
sgt = SegmentTreeInjectable.from_array(aaa_init, lambda: (0, -INF), func)
 
for _ in range(q):
    c, x = map(int, input().split())
    c -= 1
    x -= b
    sgt.update(c, (x, x))
 
    li = sgt.leftmost2(n)
    if li == -1:
        ans = sgt.get_all()[0] / n + b
    else:
        ans = sgt.get_range(0, li + 1)[0] / (li + 1) + b
    print(ans)

            

        
      