問題
要約
-
0から9までの整数からなる長さNの数列Aがある。
-
数列の長さが1になるまで、以下の2つの操作のいずれかを繰り返し行う
- 操作F: 左端の2つの値(x,y)を削除し、(x+y)%10を左端に挿入
- 操作G: 左端の2つの値(x,y)を削除し、(x×y)%10を左端に挿入
-
K = 0, 1, ..., 9 について、以下の問題に答える。
- 最終的に残る値がKとなる操作手順は何通りあるか？
-
答えは998244353で割った余りを求める。
- N: 数列の長さ
- A = (A1, ..., AN): 初期の数列
- K: 最終的に残る値（0から9の各値について計算が必要）
既存投稿一覧ページへのリンク
アプローチ
動的計画法を用いて、各ステップでの可能な状態とその状態に至る方法の数を追跡する。
二次元のDPテーブルを使用し、dp[i][j]を「i番目の要素まで処理した時点で、現在の値がjとなる操作手順の数」と定義する。
初期状態から始めて、順次状態を更新していくことで最終的な結果を得る。
解法手順
-
入力を受け取る。数列の長さnと数列aを取得する。
-
dp[n][10]の二次元配列を作成し、0で初期化する。
-
初期状態としてdp[0][a[0]] = 1とする。これは、最初の要素a[0]から始める唯一の方法を表す。
-
i = 1からn-1まで以下の処理を繰り返す：
a. j = 0から9まで以下の処理を繰り返す：- dp[i][(j+a[i])%10] += dp[i-1][j]を計算し、998244353で割った余りを取る（操作F）
- dp[i][(j*a[i])%10] += dp[i-1][j]を計算し、998244353で割った余りを取る（操作G）
-
最終的な結果として、dp[n-1][0]からdp[n-1][9]までの値を出力する。各値は998244353で割った余りとなっている。
ACコード
ac.py
def io_func():
# 数列の長さnを入力として受け取る
n = int(input())
# 数列aを入力として受け取り、整数のリストに変換する
a = list(map(int, input().split()))
return n, a
def solve(n, a):
# dp[i][j]: i番目の要素まで処理した時点で、現在の値がjとなる操作手順の数
dp = [[0]*10 for _ in range(n)]
# 初期状態の設定
dp[0][a[0]] = 1
# 動的計画法による状態の更新
for i in range(1, n):
for j in range(10):
# 操作F: 加算
dp[i][(j+a[i])%10] += dp[i-1][j]
dp[i][(j+a[i])%10] %= 998244353
# 操作G: 乗算
dp[i][(j*a[i])%10] += dp[i-1][j]
dp[i][(j*a[i])%10] %= 998244353
# 結果の出力
for i in range(10):
print(dp[n-1][i])
# メイン処理
n, a = io_func()
solve(n, a)
###
# n: 数列の長さ
# a: 入力された数列
# dp: 動的計画法のテーブル。dp[i][j]は、i番目の要素まで処理した時点で、現在の値がjとなる操作手順の数を表す
# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
# - dpテーブルを初期化
# - 初期状態を設定
# - 動的計画法により状態を更新
# - 最終結果を出力
# 3. メイン処理でio_func関数とsolve関数を呼び出す
計算量の概算
O(n)
動的計画法について
問題
この問題では、最終的に残る値Kとなる操作手順の数を求める必要がある。
DPテーブルの設計
DPテーブルを「i番目の要素まで処理した時点で、現在の値がjとなる操作手順の数」として設計する。
状態遷移の考え方
-
初期状態: dp[0][a[0]] = 1 （最初の要素a[0]から始まる）
-
i番目の要素を処理する際:
- 操作F（加算）: dp[i][(j+a[i])%10] += dp[i-1][j]
- 操作G（乗算）: dp[i][(j*a[i])%10] += dp[i-1][j]
これは、「i-1番目まで処理して値jになる方法数」から、「i番目も処理して新しい値になる方法数」を計算しています。
結果
dp[n-1][K]が、数列全体を処理して最後にKになる操作手順の数を表す。