ABC242C

ABC242C の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc242/submissions/29881684

問題

桁DPの問題です．

解説

概要図です．

ABC242_overview

とりうる数字が1から9であることに注意してください．

一番大きい位の桁から順番に処理していくと（逆でも構いません），
図で千の位で9をとりうる場合の数は1つのみです．
他の数字についても，それぞれの数字をとる場合の数は，それぞれ1です．

つぎに，百の位で9をとる可能性があるのは，千のくらいが (8, 9) のどちらかの時です．この時，千の位でとりうる数字の場合の数を足すと，百の場合の数が求まります．

（百の位が9の場合の数） = （千の位が9の場合の数）+ （千の位が8の場合の数）

同様に百の位が5を取る可能性があるのは，千の位が (4, 5, 6) のどれかの時です．
百の位が1を取る可能性があるのは，千の位が (1, 2) のどれかの時です．

ここで，1と9とる時を考えるときとりうる前の桁の数字は2通り，
1 <- (1, 2)
9 <- (8, 9
それ以外のときは，3通りであることに注意が必要であることがわかります．

それでは実装します．

標準入力を読み取り，MODの値をコピペしておきます．

MOD = 998244353
N = int(input())

dpの２次元配列の定義します．初期値は1です．
配列のサイズは（桁数，9）にしました（概要図の表と同じです）．
横方向はゼロインデックスなので，index=0は数字の1を示します．

dp = [[0]*9 for _ in range(N)]
dp[0] = [1]*9

続いて，forで桁方向（縦方向）に処理，
1つの桁について1から9までの横方向に足し算の処理をします．

for i in range(N-1):
    for j in range(9):
        dp[i+1][j] = sum(dp[i][max(0, j-1):min(j+2, 9)])%MOD
ans = sum(dp[-1])%MOD
print(ans)

j=0とj=8とる時（数字の1と9）を考えるときとりうる前の桁の数字は2通りなので，
j <- (j-1, j, j+1)
としてしまうと，
0 <- (-1, 0, 1)
になってしますので，
最大と最小を用いて，
0 <- (0, 1)
8 <- (7, 8)
になるよう，0より小さい数字は取らない，9以上の数字は取らないようにしています．

以上，ABC242Cの解法でした．

＜参考解説リンク＞