第109回【Python】最安値を達成するには 1、最安値を達成するには 2

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

はじめに

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

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

コーヒーを飲みすぎるとダメらしいです。750 ml くらいまでが限度とか。会社で大抵 500 ml くらい飲んでいる気がするので、帰ってからは飲まない方が無難そうです。それでも、自分で挽いた豆から淹れるコーヒーは最高なんですよね。

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

最安値を達成するには 1

八百屋にて、りんご1個が a 円で、りんご2個が b 円で売られています。

りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

(ヒント)

りんご1つあたりの値段を計算し、安いほうのりんごを買うことで金額の最小値を達成することもできますが、練習だと思ってDPで解いてみましょう。

部分問題として、りんご i 個 (1 ≦ i ≦ n-1) を買うのに必要な金額の最小値を求める問題を考えてみましょう。これらの問題の答えがすべて分かっているとして、n 個のりんごを買うのに必要な金額の最小値はどうなるかを考えてみましょう。少し考えると、n 個のりんごを最も安く買う方法は、

  • n-1 個のりんごを最も安く買ってから最後に1個のりんごを a 円で買う
  • n-2 個のりんごを最も安く買ってから最後に2個のりんごを b 円で買う

の2通りのうち安いほうであることがわかります。なお、a < b という制約があるため、n-1 個のりんごを最も安く買ってから最後に1個買う代わりに2個買うのは常に無駄であることに注意しましょう。これで、部分問題と元の問題との関係が明らかになりました。dp[n] をちょうど n 個のりんごを買うのに必要な金額の最小値として、漸化式を立ててみましょう。(次セクションに答え)

漸化式を自力で立てられましたか？漸化式は dp[n] = min(dp[n-1] + a, dp[n-2] + b) となります。以下の疑似コードに従って、あなたの得意な言語で実装してみましょう。

dp[0] <- 0
dp[1] <- a

for i = 2 to n
    dp[i] <- min(dp[i-1] + a, dp[i-2] + b)

print dp[n]
n a b

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

・ 1 ≦ n ≦ 1,000
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b

入力例

5 100 150

出力例

400

りんご 1 個あたりの値段を出して、比較すれば解けそう。小学生の算数の範囲？ それを、コードで書こうとすると・・・何やら難しく考えてしまう。

Python
n,a,b = map(int,input().split())
dp = [10000000] * (n+1)
dp[0] = 0
dp[1] = a
for i in range(2,n+1):
    dp[i] = min(dp[i-1] + a,dp[i-2] + b)
print(dp[n])
VBA
NAB = Split(Cells(1, 1), " ")
N = Val(NAB(0))
A = Val(NAB(1))
b = Val(NAB(2))
Dim dp() As Long
ReDim dp(N)
dp(0) = 0
dp(1) = A
For i = 2 To N

    dp(i) = 10000000
    dp(i) = Application.WorksheetFunction.Min(dp(i - 1) + A, dp(i - 2) + b)
Next
Debug.Print dp(N)

最安値を達成するには 2

八百屋にて、りんご2個が a 円で、りんご5個が b 円で売られています。
りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

(ヒント)

前問の八百屋ではりんごが1個と2個で売られていましたが、本問の八百屋では2個と5個で売られています。この変更により、前問と同じようにして解こうとするとうまくいかなくなりました。理由を考えてみてください。

前問と同じように dp[n] をちょうど n 個のりんごを買うのに必要な金額の最小値とすると、dp[3] の値が正しく計算されないことがわかります。これは、りんごは2個ずつか5個ずつでしか買うことが出来ないため、3個のりんごをちょうど買う方法が存在しないからです。では、どうしたら dp[3] のような、2と5の組合せでは作れないような個数について最安値を計算することが出来るでしょうか。

問題文の最後の文に注目すると、買うりんごの数が3個以上になってもよいことがわかるので、ここで dp2[n] を n 個以上のりんごを買うのに必要な金額の最小値としてみましょう。dp と dp2 の定義から、dp2[n] = min(dp[n], dp[n+1], ...) であることがわかります。dp2[n] が求めたい答えになっています。

dp は dp[n] までではなく、余裕をもって dp[n+4] 程度まで計算しておく必要があることに注意しましょう (実はこの問題においては dp[n+2] まで計算しておけば十分なのですが、ある程度多めに計算しておくと安心です) 。また、実は新しく dp2 という配列を用意せずとも、dp をうまく書き換えることで答えを求めることもできます。余裕があれば考えてみてください (ヒント:ループを回す順番を工夫) 。

n a b

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

・ 1 ≦ n ≦ 1,000
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b

入力例

4 110 200

出力例

200

これ、多分、りんごが n + 1 個以上になっても良いってところがポイント。初見で解いていたとき、dp を表示させてみると、3 個、4 個買うときより、5 個買うときのほうが安くなっていることに気づいた。

Python
n,a,b = map(int,input().split())
dp = [10000000] * (n+5)
dp[0] = 0
dp[1] = a
for i in range(2,n+5):
    if i >= 2:
        dp[i] = min(dp[i],dp[i-2] + a)
    if i >= 5:
        dp[i] = min(dp[i],dp[i-5] + b)
print(min(dp[n:]))
VBA
NAB = Split(Cells(1, 1), " ")
N = Val(NAB(0))
A = Val(NAB(1))
b = Val(NAB(2))
Dim dp() As Long
ReDim dp(N + 4)
dp(0) = 0
dp(1) = A
For i = 2 To N + 4
    dp(i) = 10000000
    If i >= 2 Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - 2) + A)
    End If
    If i >= 5 Then
        dp(i) = Application.WorksheetFunction.Min(dp(i), dp(i - 5) + b)
    End If
Next
For i = N To N + 4
    dp(i - N) = dp(i)
Next
ReDim Preserve dp(UBound(dp) - N)
Debug.Print Application.WorksheetFunction.Min(dp)

最後に

Python のスライスはとても使いやすい。VBA でやっていることは、先頭から詰めていって、配列のサイズを変更することで余計なものを切り捨てている。かなり以前の課題でやったやつ。引き出しがあるというのは強みになります。

ふと、それ以外の方法だと何があるだろうと考えてみる。多分、所定位置から最後まで for 文でまわして、要素ごとに大小を判定して小さければ変数に格納する、みたいな感じだろうか。言葉で書くと分かりづらい。

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

Python学習,Python,paiza

Posted by LeoSaki