C - 1, 2, 3 - Decomposition Editorial
by 
maspy
各桁の値が \(1, 2, 3\) のいずれかであるような正の整数を、良い数 と呼ぶことにします。
\(N\geqq 0\) に対して \(N\) を良い数の和として表すときの最小個数を、\(f(N)\) と表すことにします。\(f(0) = 0\) です。また、便宜上 \(N < 0\) に対して \(f(N) = \infty\) とします。
◆ 良い数の和の構造
まずは、\(K\) 個の良い数の和で表せる数はどのようなものかを考えましょう。
各 \(A_i\) を、その \(10\) で割ったときの商と余りによって \(A_i = 10a_i + b_i\) と表すことにすると、\(A_i\) が良い数であることは
- \(b_i\) は \(1, 2, 3\) のいずれか
- \(a_i\) は 良い数または \(0\)
であることと同値です。したがって、ある数が「\(K\) 個の良い数の和」として書けることは、
- \(K\) 以上 \(3K\) 以下の整数
- \(K\) 個以下の良い数の和の \(10\) 倍
の和として書けることと同値です。このことを利用して、\(f(N)\) を再帰的に計算していきましょう。
◆計算方法
\(N\geqq 1\) とし、考察を進めるために、すべての \(N' < N\) について \(f(N')\) が既知であると仮定しておきます。\(f(N)\) を計算する方法を考えましょう。
上で述べたことにより、\(K = 1, 2, 3, \ldots\) の順に、\(N\) が \(K\) 個の良い数の和で書けるかどうか \(O(K)\) 時間で判定することができます。例えば、
- \(K\) 以上 \(3K\) 以下の整数 \(r\) を全探索する
- \(N = 10n + r\) となる整数 \(n\) が存在し、\(f(n) \leqq K\) を満たすならば、\(N\) は \(K\) 個の良い数の和で書ける
これらの判定を順に行って、初めて \(K\) 個の和で表せるときに \(f(N) = K\) とすればよいです。
◆ 答えの上限・計算量解析
実は、任意の \(N\geqq 0\) に対して \(f(N) \leqq 5\) が成り立ちます。\(N\geqq 5\) のときに必ず \(N = 10n + r\) かつ \(5\leqq r\leqq 15\) となる \(n, r\) を選べることから、帰納法により容易に証明できます。
\(f(N)\) を求めるには、判定を \(K = 1, 2, 3, 4\) に対して行えばよく、すべての \(N' < N\) について \(f(N')\) が既知であるという前提のもとで \(f(N)\) は \(O(1)\) 時間で求めることができます。
さらに、\(f(N)\) は、 \(n = \lfloor N/10\rfloor\) として \(f(n), f(n-1)\) の \(2\) 値から定まることが分かります。したがって、\(n = \lfloor N/10^k\rfloor\) または \(n = \lfloor N/10^k\rfloor - 1\) と書ける \(n\) のみに対して \(f(n)\) を順に計算していけばよいことが分かります。そのような \(n\) は \(\Theta(\log N)\) 個なので、本問題は（テストケースごとに）計算量 \(\Theta(\log N)\) で解くことができます。
◆ 解答例
posted:
last update: