問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$10$ 進表記において, $N$ 桁の整数 $X$ が与えられる. $X$ の全ての桁は $0$ ではない.

$\{1,2, \dots, N-1\}$ の部分集合 $S$ に対して, $f(S)$ を次のように定める.

$X$ を長さ $N$ の文字列とみなす. $i \in S$ となる全ての $i$ に対して, $X$ の $i$ 文字目の $(i+1)$ 文字目に区切りを入れ, $X$ を $(\lvert S \rvert+1)$ の文字列に分解する.
その後, $(\lvert S \rvert+1)$ 個の文字列それぞれに対して, その文字列を $10$ 進表記された整数とみなしたとき, $f(S)$ をその $(\lvert S \rvert+1)$ 個の整数の総積と定義する.

$S$ としては $2^{N-1}$ 個考えられるが, それにおける $f(S)$ の総和を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$X$ は $10$ 進表記で全ての桁は $0$ ではない.

解法

$X$ の上から $i$ 桁目を $X_i$ と書く.

動的計画法で解く. $i=0,1,2, \dots, N$ に対して, ${\rm DP}[i]$ で $X$ の先頭 $i$ 桁に限定した時の答えとする. また, $Y_{l,r}$ で $X$ の上から $l$ 桁目から $r$ 桁目を $10$ 進表記とみたときの整数とする. ただし, $l \gt r$ のときは $Y_{l,r}=0$ とする.

$i=0$ のときは ${\rm DP}[0]=0$ である.

$i \geq 1$ のとき, 区切りを入れるか入れないか, 入れるとしたらも最も左の位置はどこかで場合分けをすることにより,

$\displaystyle {\rm DP}[i]=Y_{1,i}+\sum_{j=1}^{i-1} {\rm DP}[j] Y_{j+1,i}$

となるが, 式変形によって, $Y_{j,i}$ における下 $1$ 桁は全て $X_i$ であるので,

$\begin{align} {\rm DP}[i] &=Y_{1,i}+\sum_{j=1}^{i-1} {\rm DP}[j] Y_{j+1,i} \\ &=(10 Y_{1,i-1}+X_i)+\sum_{j=1}^{i-1} {\rm DP}[j] (10 Y_{j+1,i-1}+X_i) \\ &=X_i \left(\sum_{j=1}^{i-1} {\rm DP}[j]+1\right)+10 \left(Y_{1,i-1}+\sum_{j=1}^{i-1} {\rm DP}[j] Y_{j+1, i-1} \right) \\ &=X_i \left(\sum_{j=1}^{i-1} {\rm DP}[j]+1\right)+10 \left(Y_{1,i-1}+\sum_{j=1}^{i-2} {\rm DP}[j] Y_{j+1, i-1} \right) \\ &=X_i \left(\sum_{j=1}^{i-1} {\rm DP}[j]+1\right)+10 {\rm DP}[i-1]\\ \end{align}$

となる. よって,

$\displaystyle T_i:=\sum_{j=1}^i {\rm DP}[j]$

とする.

以上から,

$\begin{cases} {\rm DP}[i]=X_i (T_{i-1}+1)+10 {\rm DP}[i-1] \\ T_i=T_{i-1}+{\rm DP}[i] \end{cases} ~(i \geq 1), \quad \begin{cases} {\rm DP}[0]=X_0 \\ T_0=0 \end{cases}$

と計算していくことで, ${\rm DP}[N]$ が求めるべき解答であり, $O(N)$ 時間で求めることができた.

Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 288 F問題 Integer Division

問題

提出解答

問題の概要

制約

解法