111. 漸化式、隣接２項間漸化式
【問題概要】
以下のような隣接２項間漸化式が与えられます。
a1=1
a2=2
an=(n-1)*a(n-1)+(n-2)*a(n-2) (n≧3)
この隣接２項間漸化式に基づき、anを計算するプログラムを作成してください。
【解説】
この問題は隣接２項間漸化式を解く問題であり、再帰的に計算することで解けます。しかし、再帰による実装では、同じ計算を何度も繰り返すため、計算時間が指数的に増大する可能性があります。そのため、メモ化再帰やループによる動的計画法を用いた効率的な実装が求められます。
【関連するAtcoderの例題】
隣接２項間漸化式を解くアルゴリズムに関連するAtcoderの問題として、「Frog 1」があります。
レーティング難易度(★): 2
ACした回答者に絞った場合のレーティング帯の範囲(数値): 400-1600
レーティング難易度(%): 59.5
レーティング(数値): 1402
AC率(%): 81.91%
ACしたスコアの高い回答者: hachimitsu_kakigoori
解説ブログ: https://qiita.com/drken/items/03c7db44ccd27820ea0d
【問題概要】
以下のような漸化式が与えられる。n番目の項を求めよ。
a_0 = 0, a_1 = 1
a_n = 2 * a_{n-1} + 3 * a_{n-2} (n >= 2)
【解説】
この問題は、隣接２項間漸化式を解く問題です。隣接２項間漸化式とは、
a_n = A * a_{n-1} + B * a_{n-2} のような形式の漸化式のことです。
この漸化式を解くには、行列累乗を使ってO(log n)で解くことができます。
具体的には、以下のような行列
| A B |
| 1 0 |
とすると、a_n = (A B)^(n-1) (1 0)^T と表すことができます。
(1) 行列Aと列ベクトルxを定義する。
行列Aは以下のように定義します。
A = |2 3|
|1 0|
列ベクトルxは以下のように定義します。
x = |a_1|
|a_0|
(2) n-1乗の行列Aを求める。
n-1乗の行列Aは以下のようになります。
A^(n-1) = |2 3|^(n-1)
|1 0|
(3) 最後に、A^(n-1)とxの行列積を計算して、a_nを求めます。
a_n = x* A^(n-1)
この式を行列累乗で計算することで、a_nをO(log n)で求めることができます。以上の手順でa_nをO(log n)で求めることができます。
python
:MOD = 10**9+7
:
:# 行列の積を計算する関数
:def matmul(a, b):
:..n = len(a)
:..m = len(b[0])
:..res = [[0]*m for _ in range(n)]
:..for i in range(n):
:....for j in range(m):
:......for k in range(len(b)):
:........res[i][j] += a[i][k] * b[k][j]
:........res[i][j] %= MOD
:..return res
:
:# 行列の累乗を計算する関数
:def matpow(a, n):
:..res = [[1 if i == j else 0 for j in range(len(a))] for i in range(len(a))]
:..while n > 0:
:....if n % 2 == 1:
:......res = matmul(res, a)
:....a = matmul(a, a)
:....n //= 2
:..return res
:
:# a_nを計算する関数
:def solve(n):
:..A = [[2, 3], [1, 0]]
:..x = [[1], [0]]
:..Apow = matpow(A, n-1)
:..res = matmul(Apow, x)
:..return res[0][0]
:
:n = int(input())
:print(solve(n))
ここで、matpow関数は行列の累乗を計算する関数、matmul関数は行列の積を計算する関数です。また、最後にres[0][0]を返しているのは、計算結果の行列resの最初の要素がa_nに相当するからです。
【例示するAtcoderの問題】
Atcoderの問題: ABC122D - We Like AGC
URL: https://atcoder.jp/contests/abc122/tasks/abc122_d
レーティング難易度(★): 1800
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1340 ~ 2155
レーティング難易度(%): 66.5%
レーティング(数値): 1961
AC率(%): 8.27%
ACしたスコアの高い回答者: -
解説ブログ: https://qiita.com/Kept1994/items/2167c075f62a0b0a8dfe#d-問題we-like-agc
この問題は、文字列の特定の条件を満たす部分文字列の数を求める問題です。文字列の長さがNであるとき、DPを使ってO(N^3)で解くことができます。この問題の解法には、隣接２項間漸化式を使ってO(N)で解く方法もあります。具体的には、以下のような式を考えます。
dp[n][0][0][0] = 1 (n = 0)
dp[n][1][0][0] = 1 (n = 1)
dp[n][0][1][0] = 1 (n = 2)
dp[n][0][0][1] = 1 (n = 3)
dp[n][i][j][k] = dp[n-1][i][j][k] * 3
+ dp[n-1][i][j][k] * (j > 0)
+ dp[n-1][i][j][k] * (k > 0)
+ dp[n-2][i][j][k][l] * (l > 0)
ここで、dp[n][i][j][k]は、長さnの文字列で、文字'a'がi個、文字'g'がj個、文字'c'がk個含まれるような文字列の数を表しています。また、lは文字't'を表しています。
文字列の末尾の3文字が'agc'であることを保証するために、n-2番目の文字が'a'、'g'、'c'のいずれかである必要があります。また、(l > 0)という条件がついているのは、't'が一つも含まれていない場合には、この項が無駄になるためです。
このように、式全体は、文字列の末尾に新しい文字を追加する場合と、'g'、'c'、'agc'を末尾に追加する場合の、それぞれの場合を考慮したものになっています。
f[i][j][k][l] := i番目までの文字列で、末尾から3文字目までの文字がjklである部分文字列の数
この式によって、DPテーブルを更新していきます。具体的には、以下のように更新します。
f[i][j][k][l] = Σf[i-1][a][j][k] (a != k) + Σf[i-1][a][g][j] (a != j, j != l, g != k)
(ただし、Σは和を表す記号であり、a, gは"A", "G", "C", "T"のいずれかを表します)
この式によって、隣接２項間漸化式を使ってO(N)で解くことができます。
Atcoderの問題: AGC019C - Prefixes and Suffixes
URL: https://atcoder.jp/contests/agc019/tasks/agc019_c
レーティング難易度(★): 2200
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1750 ~ 2674
レーティング難易度(%): 47.8%
レーティング(数値): 2358
AC率(%): 6.69%
ACしたスコアの高い回答者: https://atcoder.jp/users/Pinggwin
解説ブログ: https://drken1215.hatenablog.com/entry/2021/03/20/153400
この問題は、文字列を2つ連結させたものから、接頭辞と接尾辞が一致するような文字列を数える問題です。DPテーブルの添字として、文字列の長さと、接頭辞と接尾辞が一致しているかどうかの情報を使います。その後、漸化式を立ててDPテーブルを更新することで、この問題を解くことができます。
この問題では、隣接２項間漸化式を使って、DPテーブルをO(N)で更新することができます。具体的には、以下のような漸化式を使います。
dp[i][0] = dp[i-1][0] + dp[i-2][0]
dp[i][1] = dp[i-1][1] + dp[i-2][0]
dp[i][2] = dp[i-1][2] + dp[i-2][1]
この式によって、DPテーブルを更新していきます。ただし、dp[i][0]は、接頭辞と接尾辞が一致していない場合、dp[i][1]は、接頭辞と接尾辞が一致しているが、文字列の一部が一致していない場合、dp[i][2]は、接頭辞と接尾辞が完全に一致する場合を表します。
このように、隣接２項間漸化式を使ってDPテーブルを更新することで、O(N)でこの問題を解くことができます。
Discussion