競プロ精進ログ

典型90 042 – Multiple of 9(★4)

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色!

今のレートは茶色です。

問題

典型90 042 - Multiple of 9(★4)を解きました。

考察

各桁の和がちょうどKになり、かつ9の倍数であるような数がいくつ作れるか、という問題。

数の性質として、各桁の和が9の倍数になるとき、その数もまた9の倍数になる。

つまり、与えられたKが9の倍数でない場合は、必然的に答えは0通りになる。

次に、Kが9の倍数である場合については、桁に0を含まないことから、足してKになるすべてのパターンを列挙すれば良い。

例えば、先頭行の値が1~9それぞれの場合、次の桁は、

  • 1 K-1
  • 2 K-2
  • 3 K-3
  • 4 K-4
  • 5 K-5
  • 6 K-6
  • 7 K-7
  • 8 K-8
  • 9 K-9

となる。

これを、dp[各桁の和] = 通り数 というDPで求めていく。

すべてのKに対して、各桁の和がKとなる場合の通り数は、各桁の和が”K-1” ~ “K-9”になる場合の通り数の和と等しい。

コード

K = int(input())
mod = int(pow(10,9) + 7)
if K % 9 != 0:
    print(0)
    exit()
 
# dp[各桁の和] = 通り数
dp = [0] * (K + 1)
dp[0] = 1


for i in range(1, K + 1):
    # 9未満の場合は0なので無視して良い
    m = min(9, i)

    # Kまでのすべての値に対して、"K-1" から "K-9" までの通り数の和を求めていく
    for j in range(1, m + 1):
        dp[i] += dp[i - j]

    dp[i] %= mod
print(dp[K])

まとめ

こういうのを自力ACするのが厳しい。

各桁の和がKとなる場合の通り数は、各桁の和が”K-1” ~ “K-9”になる場合の通り数の和と等しいことなんてどうやったら気づける?

COMMENT

メールアドレスが公開されることはありません。