[Codeforces] Codeforces Round #675 (Div. 2) C. Bargain

2020年10月12日

問題

数字列 \( n \) の部分列を取り除いて得られる整数の総和と求めます。

方針

部分列について

自然数 \( l \) を \( l = |n| \) とします。ここで、総和に対する \( i \) 文字目の整数 \( n_i \) の影響度を考えます。\( n_i \) を含まない文字列は、\( n_1 \) から \( n_{i – 1}\) の文字で構成される部分列 \( L_i \) と \( n_{i + 1} \) から \( n_l \) で構成される部分列 \( R_i \) のどちらかを \( n \) から取り除いたものとなります。 取り除くことができる部分列は連続なので、両方を取り除くことはできません。

\( n \) から \( L_i \) を取り除くとき

このとき、\( n_i \) の位は変化しません。これは、\( i + 1 \) 文字目以降の文字が取り除かれないためです。\( |L_i| = k \  ( 1 \leq k \leq i – 1 ) \) となる \( L_i \) の個数は、\( i – k \) 個あるので、累計で

\[ \dfrac{i(i -1)}{2}\]

個存在します。したがって、影響度は、

\[\dfrac{10^{i-1}n_ii(i -1)}{2}\]

となります。

\( n \) から \( R_i \) を取り除くとき

このとき、\( i + 1 \) 文字目以降の文字を取り除くことになるので、\( n_i \) の位が変化します。\( n_i \) の位が \( k \ (1 \leq k \leq l – i)\) となるときの \( R_i \) の個数は \( k \) となります。したがって、影響度は、

\[n_i \sum_{k = 1}^{l – i} k 10^{k – 1}\]

となります。\( \sum_{k = 1}^{l – i} k 10^{k – 1} \) は累積和を用いて高速に求めることができます。

\( n_i \) の影響度

上記より、\( n_i \) の影響度は、

\[ \dfrac{10^{i-1}n_ii(i -1)}{2} + n_i \sum_{k = 1}^{l – i} k 10^{k – 1}\]

となるので、全ての文字について全探索します。

コード

感想

最初は非連続な部分列について考えてて誤読しました。