第105回【Python】特殊な2項間漸化式 1、特殊な2項間漸化式 2

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 105 回目です。

新しい案件が始まるときはその準備で大忙しになります。お客様との打ち合わせ、メンバーへの OJT、各種書類の整備。LeoSaki（旦那）は人見知りのコミュ障なので、お客様との打ち合わせが嫌いです。それでもやらなければいけないので、心を無にして頑張っています。

それでは、今日も頑張ってみようと思います。

特殊な2項間漸化式 1

整数 x, d_1, d_2, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。

・ a_1 = x 
・ a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3) 
・ a_n = a_{n-1} + d_2 (n が偶数のとき)
x d_1 d_2 k

すべてのテストケースにおいて、以下の条件をみたします。

・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d_1 ≦ 1,000
・ -1,000 ≦ d_2 ≦ 1,000
・ 1 ≦ k ≦ 1,000

入力例

5 -7 10 5

出力例

11

条件によって式が異なる場合。人間が手動で計算しろ、と言われると頭を抱えそうだけど、コンピュータは瞬時に答えを出してくれる。素敵。

Python
x,d1,d2,k = map(int,input().split())
A = [x] * (k+1)
for i in range(2,k+1):
    if i % 2 == 0:
        A[i] = A[i-1] + d2
    else:
        A[i] = A[i-1] + d1
print(A[k])
VBA
xdk = Split(Cells(1, 1), " ")
x = Val(xdk(0))
d1 = Val(xdk(1))
d2 = Val(xdk(2))
k = Val(xdk(3))
Dim A() As Long
ReDim A(k)
A(1) = x
For i = 2 To k
    If i Mod 2 = 0 Then
        A(i) = A(i - 1) + d2
    Else
        A(i) = A(i - 1) + d1
    End If
Next
Debug.Print A(k)

特殊な2項間漸化式 2

整数 x, d_1, d_2, Q と Q 個の整数 k_1, k_2, … , k_Q が与えられます。

次のように定められた数列の k_i 項目の値を順に出力してください。

・ a_1 = x 
・ a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3) 
・ a_n = a_{n-1} + d_2 (n が偶数のとき)
x d_1 d_2
Q
k_1
k_2
...
k_Q

・ 1行目では、数列の初項 x と公差 d_1, d_2 が与えられます。
・ 2行目では、3行目以降で与えられる入力の行数 Q が与えられます。
・ 続く Q 行のうち i 行目では、k_i が与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d_1 ≦ 1,000
・ -1,000 ≦ d_2 ≦ 1,000
・ 1 ≦ Q ≦ 1,000
・ 1 ≦ k_i ≦ 1,000 (1 ≦ i ≦ Q)

入力例

3 7 -4
5
1
2
3
4
10

出力例

3
-1
6
2
11

1,000 件くらいなら一瞬で出してくれる、素敵。手計算で 1,000 件分を出せと言われたら遠い目をするしかなさそう。

Python
x,d1,d2 = map(int,input().split())
A = [x] * (1001)
for i in range(2,1001):
    if i % 2 == 0:
        A[i] = A[i-1] + d2
    else:
        A[i] = A[i-1] + d1
Q = int(input())
for _ in range(Q):
    print(A[int(input())])
VBA
xdk = Split(Cells(1, 1), " ")
x = Val(xdk(0))
d1 = Val(xdk(1))
d2 = Val(xdk(2))
Dim A(1001) As Long
A(1) = x
For i = 2 To 1001
    If i Mod 2 = 0 Then
        A(i) = A(i - 1) + d2
    Else
        A(i) = A(i - 1) + d1
    End If
Next
Q = Cells(2, 1)
For i = 1 To Q
    k = Cells(i + 2, 1)
    Debug.Print A(k)
Next

最後に

まだまだ序盤。最初に問題に取り組んだときは、なんとなくさらさらと書いて終わったけれど、こうやって見返しながら解き直してみると、更に自分の実になったように感じて良い。

ナップサック問題とかで、時々躓いて、総当たりでやろうとして、timeout みたいなことをやらかしてしまうので、基本から学習しなおすことは大きな意味があると思っている。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki