Kazun の競プロ記録

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

AtCoder Beginner Contest 242 C問題 1111gal password

AtCoder ABC ABC242 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を見たす整数 X の個数を求めよ.

  • N 桁の正の整数
  • X の各桁を X_1, X_2, \dots, X_N としたとき, 以下を満たす.
    • 1 \leq X_i \leq 9 \quad (i=1,2, \dots, N)
    • |X_i-X_{i+1}| \leq 1 \quad (i=1,2, \dots, N-1)

制約

  • 1 \leq N \leq 10^6

解法

各桁の数字が 1 以上 9 以下の N 桁の整数と長さが N で各桁が 1 以上 9 以下の整数からなる整数列を同一視する.

動的計画法で解く. {\rm DP}[i,x] で先頭 i 項まで決定し, 末項が x であるような列の数とする.

  • ベースケースは {\rm DP}[1,x]=1 \quad (x=1,2, \dots,9) である.
  • 更新式は以下のようになる.
{\rm DP}[i,x]=\begin{cases} {\rm DP}[i-1, 1]+{\rm DP}[i-1, 2] & (x=1) \\ {\rm DP}[i-1,x-1]+{\rm DP}[i-1,x]+{\rm DP}[i-1,x+1] & (1 \lt x \lt 9) \\ {\rm DP}[i-1, 8]+{\rm DP}[i-1, 9] & (x=9) \end{cases}

この動的計画法により, 最終的な答えは

\displaystyle \sum_{x=1}^9 {\rm DP}[N,x]

であり, 計算量 O(N) で求めることができる.