AtCoder Beginner Contest 224 F 問題 Problem where +s Separate Digits

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

${\tt 1}$ から ${\tt 9}$ までの数字のみで構成される文字列 $S$ に対して, 以下のような操作を行い, 文字列 $T$ を行う.

$|S|-1$ 個ある文字の間それぞれに対して, ${\tt +}$ を挿入するか, 何もしない.

そして, $T$ を計算式と満たしたときの計算結果を $\operatorname{calc}(T)$ とする.

$T$ としては $2^{|S|-1}$ 通りあるが, 全ての場合における $\operatorname{calc}(T)$ の総和を求めよ.

制約

$S$ は ${\tt 1}$ から ${\tt 9}$ までの数字のみで構成される長さ $1$ 以上 $2 \times 10^5$ 以下の文字列.

解法

$N=|S|$ とする. また, $i=1,2,\dots,N-1$ に対して, 位置 $i$ を $S$ の $i$ 文字目と $i+1$ 文字目の間とする. また, $i=1, \dots, N$ に対して, $S_i$ で $S$ の $i$ 文字目を整数と見なしたときの値とする.

$T$ を1つ固定する. このとき, $c_{T,i}$ を $T$ において, $S[i$ ] が属する項において $S[i$ ] は $10^{c_{T,i}}$ の位を表しているとする. このとき,

$\displaystyle \operatorname{calc}(T)=\sum_{i=1}^N S[i ] 10^{c_{T,i}}$

である. ここで, $0 \leq c_{T,i} \leq N-1$ であることから,

$\displaystyle 10^{c_{T,i}}=\sum_{k=0}^{N-1} [c_{T,i}=k ] 10^k$

より,

$\displaystyle \operatorname{calc}(T)=\sum_{i=1}^N S[i] \sum_{k=0}^{N-1} [c_{T,i}=k ] 10^k$

である. $T$ を動かした総和は, シグマを交換することにより

$\displaystyle \sum_{T} \operatorname{calc}(T)=\sum_{i=1}^N S[i] \left(\sum_{k=0}^{N-1} 10^k \sum_{T} [c_{T,i}=k ] \right)$

となるので, 各 $i$ において, $i$ 文字目が $10^k$ の位となるような $T$ はいくつあるか? という問題を解けば良いことになる.

$T$ において, $i$ 文字目が $10^k$ の位になるための必要十分条件は,

かつ
- のとき
  - 位置 $i, i+1, \cdots, i+k-1$ に ${\tt +}$ が挿入されていない.
  - 位置 $i+k$ に ${\tt +}$ が挿入されている.
- のとき
  - 位置 $i, i+1, \cdots, i+k-1$ に ${\tt +}$ が挿入されていない.

である. それぞれを満たす $T$ の個数を求める.

のとき
- 位置 $i, i+1, \cdots, i+k-1, i+k$ の $k+1$ 箇所に挿入の条件があり, それ以外にはないので, $2^{(N-1)-(k+1)}=\frac{2^{N-k}}{4}$ 通り
のとき
- 位置 $i, i+1, \cdots, i+k-1$ の $k$ 箇所に挿入の条件があり, それ以外にはないので, $2^{(N-1)-k}=\frac{2^{i+1}}{4}$ 通り

従って,

$\begin{align} \sum_{k=0}^{N-1} \sum_{T} [c_{T,i}=k ] 10^k &=\sum_{k=0}^{N-i-1} 10^k \cdot \frac{2^{N-k}}{4}+10^{N-i} \frac{2^{i+1}}{4} \\\\ &=\frac{2^N}{4} \left(\sum_{k=0}^{N-i-1} 5^k+2 \cdot 5^{N-i} \right)\\\\ &=\frac{2^N}{4} \left(\sum_{k=0}^{N-i} 5^k+5^{N-i} \right)\\\\ &=\frac{2^N}{4} \left(\frac{5^{N-i+1}-1}{5-1}+5^{N-i} \right)\\\\ &=\frac{2^N}{4} \left(\frac{5^{N-i+1}-1}{4}+5^{N-i} \right)\\\\ &=\frac{2^N}{16} \left(9 \cdot 5^{N-i}-1\right)\\\\ \end{align}$

となることから, 求めるべき値は,

$\displaystyle \sum_{T} \operatorname{calc}(T)=\sum_{i=1}^N S[i] \cdot \frac{2^N}{16} \left(9 \cdot 5^{N-i}-1\right)=\frac{2^N}{16} \sum_{i=1}^N S[i] \left(9 \cdot 5^{N-i}-1\right)$