深さのある区間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)$
終端条件は、
計算量は、$f()$ の状態数が $O(N^2MD)$（ただし $D$ は文字種数 $=10$）、
遷移に $O(N)$ なので、$O(N^3MD)$ となる。
Python3
PyPyの再帰が遅いというのは、$10^4～10^5$ もの深い再帰が遅いのであって、
階層の浅い再帰の場合はそこまで恐れなくてもいいっぽい。
def dfs(l, r, k, d):
if l == r:
return 1
if k == m:
if l + 1 < r:
return 0
else:
return 1
if d >= 10:
return 0
if 0 <= sss[l][k] < d:
return 0
if memo[l][r][k][d] != -1:
return memo[l][r][k][d]
res = dfs(l, r, k, d + 1)
for x in range(l + 1, r + 1):
if sss[x - 1][k] != -1 and sss[x - 1][k] != d:
break
res += dfs(l, x, k + 1, 0) * dfs(x, r, k, d + 1) % MOD
res %= MOD
memo[l][r][k][d] = res
return res
n, m = map(int, input().split())
sss = []
for _ in range(n):
s = input()
s_arr = []
for c in s:
if c == '?':
s_arr.append(-1)
else:
s_arr.append(int(c))
sss.append(s_arr)
MOD = 998244353
memo = [[[[-1] * 10 for _ in range(m)] for _ in range(n + 1)] for _ in range(n)]
ans = dfs(0, n, 0, 0)
print(ans)
$b_i=a_i-B$ とし、$b_i$ をセグメント木で管理する。
今回の問題では、「一番始めに $b_1+b_2+...+b_i$ が $0$ 以上になる $i$」を求めたい。
なので、$b_i$ の「先頭からの累積和」と、さらにその「累積和の先頭からの累積MAX」を同時に管理したい。
累積和は $b_i$ の値によって上下するためはじめて $0$ 以上が出現する位置を特定しづらいが、
累積MAXを取っておけば、それを参照して二分探索が可能になる。
各セグメント木のノードに、(その区間の和, その区間の中での先頭からの累積和のMAX) を載せればよい。
ノード $n$ に対して、それぞれ $n[0],n[1]$ とする。
ノード $L$ と $R$ をマージするとき、
$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$
根以降は、自身より左の区間の総和も含めて累積MAXを計算する必要があるので、
これを繰り返して、$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)