AtCoder Beginner Contest 292 G,Ex問題メモ

AtCoder Beginner Contest 292

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