第109回【JavaScript】最安値を達成するには 1、最安値を達成するには 2
現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
JavaScript をゼロから勉強してみよう、のコーナー 109 回目です。
本番環境で作業を行う際には、何重にも保険をかけておきます。手順をまとめ、各手順における正常性の確認方法、切り戻し方法をまとめ、更に、作業時には声に出して間違いないかを確認する。LeoSaki（旦那）は、本番環境でやらかしたことはありません。ただ、準備に時間がかかります。
それでは、今日も頑張ってみようと思います。
最安値を達成するには 1 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_apples_ste...八百屋にて、りんご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入力値最終行の末尾に改行が１つ入ります。
期待する出力
りんごを n 個手に入れるために必要な金額の最小値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 1,000
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b
入力例
5 100 150出力例
400算数的な考え方でも解けるものを、総当たりで解いてしまえるところがコンピューターの素敵なところ。
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const [n,a,b] = lines[0].split(/\s/).map(Number);
const dp = Array(n+1).fill(10000000);
dp[0] = 0;
dp[1] = a;
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i-1] + a, dp[i-2] + b);
}
console.log(dp[n]);
});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])最安値を達成するには 2 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_apples_ste...八百屋にて、りんご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入力値最終行の末尾に改行が１つ入ります。
期待する出力
りんごを n 個手に入れるために必要な金額の最小値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 1,000
・ 1 ≦ a ≦ 10,000
・ 1 ≦ b ≦ 10,000
・ a < b
入力例
4 110 200出力例
2002 個と 5 個の組み合わせだと、3 個ちょうどを購入することは出来ない、というのがポイントか。
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const [n,a,b] = lines[0].split(/\s/).map(Number);
const dp = Array(n+5).fill(10000000);
dp[0] = 0;
dp[1] = a;
for (let i = 2; i < n + 5; i++) {
if (i >= 2) dp[i] = Math.min(dp[i],dp[i-2] + a);
if (i >= 5) dp[i] = Math.min(dp[i],dp[i-5] + b);
}
console.log(Math.min(...dp.slice(n)));
});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:]))最後に
今回は、高々 5 要素の展開であったため、スプレッド構文を利用してみました。大きな配列を展開する場合、パフォーマンスの低下もあり得るようなので、使いどころは注意しなければならないかもしれないです。
fill で初期値を入れてしまうのと、for 文内でいちいち 1 要素ごとに十分に大きな数を入れて、min で比較するのとでは、どちらがパフォーマンス的に良いのだろう。そこまで調べきれなかったので今後の課題です。
引き続き、よろしくお願いいたします！
