ABC224 F - Problem where +s Separate Digits [解説]
ぱっと見滅茶苦茶 ad-hoc そうなのに考えれば考えるほど典型になってｳﾜｧ……ってなる
でもすき
考えること
正直サンプル $1$ を見た瞬間解法わかった人も多そうだが、自分はそれから検証の為に数分ほどは必要だった。
あと、なんならサンプル $1$ の全数式が列挙されている部分がこの問題の全てである。
以下、$|S| = N$ とする。
桁ごとに考える、という典型テクニックがある。普段は xor とかで用いるものだが、今回この全数式が列挙されている部分を執念深く睨むことで答えに近づくことが出来る。
というのも、例えばサンプル $1$ の入力のうち一番上の桁である $1$ について見ると、数式上で $1$ がある項において、$1$ が下から $1$ 桁目である場合が $4$ 回、$2$ 桁目である場合が $2$ 回、$3$ 桁目である場合が $1$ 回、$4$ 桁目である場合が $1$ 回あることがわかる。
つまり、$4$ 桁目、つまり一番上を例外として、あとは下から $i$ 桁目に出現する回数が $2^{N-i}$ 回となっている。
また、入力の $j$ 桁目になると、その数がある項において $1, 2, \ldots, j - 1$ 桁目までに出現する回数は $0$ となり、$j$ 桁目に出現する回数が $2^{j-1}$ に置き換わる。(なお、実際にはこれが $j = 1$ でも正しい)
イメージとしては、入力の一番上の桁を見ているときは、数式上でその桁が出現する項においてその項の $i$ 桁目に出現する回数が
$[1,1,2,4,8,16, \ldots]$
という感じで、入力の下の項に行くにしたがって左から順に
$[0,2,2,4,8,16, \ldots]$
$[0,0,4,4,8,16, \ldots]$
$[0,0,0,8,8,16, \ldots]$
$\vdots$
といったように変化していく。
なお、このことは、
見ている桁よりも右側にいくら + が置かれようが関係ない
ことから $2$ の階乗となること、
見ている桁が下から $i$ 番目なら、分割後のその桁がある項において下から $i$ 番目よりももっと上に来ることは無い
ことから、少しずつ $0$ が増えていくことが証明できる。厳密な証明については割愛する。
そして、これらについて、出現する桁が下から $i$ 桁目ならば $10^i$ を掛けた値をとる。つまり、
入力の $1$ 桁目 -> $[1 \times 10^N,1 \times 10^{N-1},2 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $2$ 桁目 -> $[0 \times 10^N,2 \times 10^{N-1},2 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $3$ 桁目 -> $[0 \times 10^N,0 \times 10^{N-1},4 \times 10^{N-2},4 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
入力の $4$ 桁目 -> $[0 \times 10^N,0 \times 10^{N-1},0 \times 10^{N-2},8 \times 10^{N-3},8 \times 10^{N-4}, \ldots]$
$\vdots$
各入力の桁について、係数は上の総和になるので、入力の $j$ 桁目の値と掛ける。その総和が答えになる。
ここで、各入力の桁にかかる係数を求めることになるのだが、頑張ると $Ο(N)$ で $j=1$ の場合を求めたあと、$Ο(1)$ で $j=2, 3, \ldots, N$ まで順番に求められる。
あとは、やるだけで OK。
