Kazun の競プロ記録

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

AtCoder Regular Contest 136 D問題 Without Carry

AtCoder ARC ARC136 D問題 600 pts

問題

提出解答

問題の概要

長さ $N$ の列 $A$ が与えられる. 以下を満たす $1$ 以上 $N$ 以下の組 $(i,j)$ の個数を求めよ.

$1 \leq i \lt j \leq N$
$A_i+A_j$ を筆算で計算すると, 繰り上がりが発生しない.

制約

$2 \leq N \leq 10^6$
$0 \leq A_i \lt 10^6$

解法1 (条件)

$d=6$ とする. $0$ 以上 $9$ 以下の整数からなる列の集合を $\mathcal{A}$ とする. このとき, $\mathcal{A}$ と $[\![10^d] \! ]$ の間には

$\displaystyle [a_0, a_1, a_2, a_3, a_4, a_5] \leftrightarrow \sum_{k=0}^5 10^k a_k$

という対応がある. 以降ではこの対応による同一視を行うことがある.

また, $a \in \mathcal{A}$ に対して, $\overline{a}$ を

$\overline{a}=[9-a_0, 9-a_1, 9-a_2, 9-a_3, 9-a_4, 9-a_5]$

とする.

このとき, $a,b \in [\![10^d] \! ]$ において, $a+b$ を筆算で求める際に繰り上がりが生じないことと, $a \lhd \overline{b}$ *1 であることは同値である.

解法2 (計上)

$b \in [\![10^d] \! ]$ において, $A_j \lhd b$ となる $j$ の個数を $Z_b$ とする. このとき, 求めるべき答えは

$\displaystyle \dfrac{1}{2} \sum_{i=1}^N \left( Z_{A_i} - \left[A_i \lhd \overline{A_i} \right] \right)$

である.

最後に, $Z_b$ を求める方法を考える. $\lhd$ は直積順序であり, $\# \mathcal{A}=10^d$ である. よって, $d$ 次元の配列における Zeta 変換を施せば良い. 詳しくは以下のサイトを参考にすること.

計算量は $O(N+d \times 10^d)$ である.

*1: $\leq$ は自然数の順序の直積順序