[AtCoder] ABC 178 C – Ubiquity

2020年9月14日

問題

方針

組み合わせ

全ての数列の組み合わせは \( 10^N \) 個あります。\( 0 \) または \( 9 \) が存在しない数列の組合せは \( 9^N \) 個あります。\( 0 \) と \( 9 \) が存在しない数列の組み合わせは \( 8^N \) 個あります。

ここで、全ての組み合わせの集合を \( U \)、\( 0 \) が存在しない集合を \( A \)、\( 9 \) が存在しない集合を \( B \) とすると、求める集合は、

\[ U – A – B + A \cap B\]

となります。したがって、求めるものは

\[ 10^N – 2 \times 9^N + 8^N\]

となります。

動的計画法

ここで、配列 \( d \) を次のように定義します。

  1. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) と \( 9 \) を含まないものの個数
  2. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) を含まないものの個数
  3. \( d(i, 0)\) : \( i \) 個の整数列で \( 9 \) を含まないものの個数
  4. \( d(i, 0)\) : \( i \) 個の整数列で \( 0 \) と \( 9 \) を含むものの個数

初期値は \( d(0, 0) = 1 \) とし、更新式は、

\begin{eqnarray}
d(i + 1, 0)&=& 8d(i, 0)\\
d(i + 1, 1)&=& d(i, 0) + 9d(i, 1)\\
d(i + 1, 2)&=& d(i, 0) + 9d(i, 2)\\
d(i + 1, 3)&=& d(i, 1) + d(i, 2) + 10d(i, 3)
\end{eqnarray}

となります。したがって、\( d(N, 3) \) が答えです。

コード

組み合わせ

動的計画法

感想

これ解けなくてちょびっと涙が出た。