torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 379, E : Sum of All Substrings

問題概要

 $1$ 以上 $9$ 以下の整数を表す数字のみからなる長さ $n$ の文字列 $S$ ($|S| = n$) が与えられる.
 文字列 $S$ の $l$ 文字目から $r$ 文字目までの部分文字列を $S[ l, r ]$ と書くことにし,数字のみからなる文字列をそれを通常の方法で読んだときに解釈される正整数に写す関数を $f$ とする.以下を求めよ:
\begin{equation*}
\sum_{ i = 1 }^n \sum_{ j = i }^n f( i, j )
\end{equation*}

制約

  • $1 \leq 2 \leq n \times 10^5$

準備

 $S$ の $i$ 文字目を $S[i]$ と書くことにし,$S[i]$ が表す一桁の整数を $d_S( i )$ と書くことにします.

解法

 部分文字列の取り方は $\Theta( n^2 )$ 個あるため,これらすべてについて $f$ の値を計算するようなことはできません.$O( n )$ 個ぐらいしかないものに着目したいです.
 $S$ の各桁(文字)は $\Theta( n )$ 個しかないので,こちらに着目します.各 $d_S( i )$ の答えへの寄与は,それが部分文字列のどの位置に現れるか(e.g., $1$ の位,$10$ の位,……)によって変わります.部分文字列での出現位置ごとに分けて考えると,ある $j$ に対して $S[j]$ が一の位として出現するのは $i \leq j$ なる $i$ で $S[ i, j ]$ と書ける部分文字列で,$j$ 個あります.各 $d_S( j )$ は $j$ 回足されるということなので,式にすれば
\begin{equation*}
\sum_{ j = 1 }^n j d_S( j )
\end{equation*}
となります.もうひとつ例として,$S[j]$ が $10$ の位として出現する場合を考えます.この場合は,$i \leq j$ なる $i$ で $S[ i, j + 1 ]$ と書ける部分文字列で $S[j]$ が $10$ の位(右から $2$ 文字目)として出現します.この個数もある $j$ に対して $j$ 個ありますが,$j = n$ に対しては $S[ i, j + 1 ]$ という部分文字列をとれないので $j$ が動ける範囲が狭くなって,
\begin{equation*}
\sum_{ j = 1 }^{ n - 1 } 10 j d_S( j )
= 10 \sum_{ j = 1 }^{ n - 1 } j d_S( j )
\end{equation*}
となります.パターンが見えてきたのでまとめると,$S[j]$ が $10^k$ の位 ($k \geq 0$) として出現する場合の答えへの寄与は
\begin{equation*}
10^k \sum_{ j = 1 }^{ n - k } j d_S( j )
\end{equation*}
となります.
 ある $10^k$ の位について上記の値を計算した結果が $10$ 未満であれば $10$ 進数の桁として正しいのでそれでよいですが,そうでない場合は問題があります.この場合は,$10$ での商 $q$ と剰余 $r$ に分けて考えます.$10^k$ の位には $r$ が足されることにして,$q$ は $10^{ k + 1 }$ の位に足される値として「繰り上がり」をすれば,出力するべき整数の各桁を下から決めていくことができます.$\sum_{ j = i }^{ n - k } j d_S( j )$ の値を毎回計算していると TLE しますが,$\sum\limits_{ j = 1 }^{ n } j d_s( j )$ から始めて桁を進めるごとに $k d_S( k )$ を引いていくことにすれば $O( 1 )$ 時間で更新できます.
 繰り上がりによって答えの桁数は $n$ より大きくなりえますが,$S$ の最上位桁から次の桁に繰り上げられる値は高々 $\frac{ 9 n }{ 10 }$ 程度で,上位桁に行く度に $\frac 1 { 10 }$ 倍になっていくので,がんばっても $\log_{ 10 } n$ 桁ぐらいしか増やせません.よって,答えの桁数は $O( n )$ 桁です.また,$S$ 自体も部分文字列として足されるので $\Omega( n )$ 桁でもあることが分かるので,答えは $\Theta( n )$ 桁です.前計算に $\Theta( n )$ 時間をかけた後,各桁の値は $O( 1 )$ 時間で求めることができるという話だったので,全体の計算量も $\Theta( n )$ 時間となります.

コード (C++)

int main()
{
	IN( int, N );
	IN( string, S );

	LL sum = 0;
	REP( i, N )
	{
		const int D = S[i] - '0';
		sum += D * LL( i + 1 );
	}

	string res;
	for ( LL curr = 0, i = 0; curr || i < N; ++i )
	{
		curr += sum;
		res += '0' + curr % 10;
		curr /= 10;
		if ( i < N )
		{
			const int D = S[ N - 1 - i ] - '0';
			sum -= D * LL( N - i );
		}
	}

	reverse( ALL( res ) );
	cout << res << endl;

	return 0;

コード (Haskell)

main = do
	n <- readInt
	ds <- map digitToInt <$> getLine
	let
		ss = zipWith (*) ds [ 1 .. ]
		res = solve 0 $ ( map ( sum ss - ) $ scanl (+) 0 $ reverse ss ) ++ repeat 0
	putStrLn $ reverse $ map intToDigit res

solve 0 (0:_) = []
solve c (s:ss) = r : solve q ss
	where
	( q, r ) = ( c + s ) `divMod` 10