ハイパーインフレーション (paizaランク B 相当)
解き方
大きな流れをまとめる。
問題文把握。
条件から、x日目について二分探索。
探索では、各食品の安い方の商品で、総額を求め、K以下になるか判定する。
問題文を正しく理解するところから。
N 種類の食品をそれぞれ 1 つずつ買い
それぞれの食品には 2 種類の商品があり
つまり、N種類の食品、それぞれの食品について、２種類の中から、１種類選ぶ。
例えば、3種類の食品、りんご、みかん、バナナがあったら、
それぞれの食品について、２種類あるので、りんご(サンふじ、王林)、みかん(有田、三ヶ日)、バナナ(フィリピン、エクアドル)、となり、その中から１種類だけ選ぶ。りんご(サンふじ)、みかん(有田)、バナナ(エクアドル)のように。
i 番目の食品の x (x ≧ 1) 日目の価格
N種類のうち、i番目(i種類目)の食品の、x日目の価格、ということ。
例えば、３種類のうち2番目のみかんの、３日目の価格、ということ。
それぞれ A_i x + B_i 円, C_i x + D_i 円で
A_i x + B_i 円, C_i x + D_i 円のA_i x、C_i xが何を意味しているのか、はじめよくわからなかった。
試行錯誤したが、どうやらA_i x、C_i xは掛け算、すなわち、A_i * x + B_i 円, C_i * x + D_i 円を表しているようだ。
なので、具体例を挙げると、３種類のうち2番目のみかんの入力が入力が[A_2, B_2, C_2, D_2,] = [3 200 2 300]のとき、３日目の価格はx=3なので、
有田みかんA_i * x + B_i 円, 三ヶ日みかんC_i * x + D_i 円
=有田みかん3 * 3 + 200 円, 三ヶ日みかん2 * 3 + 300 円
=有田みかん209 円, 三ヶ日みかん306 円
となる。
合計 K 円以下の価格で買いそろえる
ので、２種類の商品のうち、安い方を選ぶ。上の具体例なら、有田みかん209 円, 三ヶ日みかん306 円なので、有田みかん209 円を選ぶ。
入力の条件を見ると、
1 ≦ N ≦ 200,000 = 2 × 10^5
・ 2 ≦ K ≦ 1,000,000,000,000 = 10^12
・ 1 ≦ A_i, B_i, C_i, D_i ≦ 1,000,000 = 10^6
と、とても大きな数なので、ふつうにforループをしたら、計算が終わらなそう。
ハイパーインフレーションにより、その価格は常に上昇中です。
xが増えれば金額の増えるので、二分探索が使えそうです。
x日目かで二分探索してみる。
x日目の範囲は、1<=x<=10^6で探索する。
理由は、以下。
最小値は、1日目がスタート。
一番日数がかかりそうなのは、所持金Kが最大10^12で、商品が最安の時、つまり、N=1でA,B,C,Dが全て1で２種類の商品価格がどちらも2円の時。
細かく計算すれば、
2円*(1+2+...+x)日=10^12
1からxまでの和を求める公式より
2*1/2x(x+1)=10^12
x(x+1)=10^12
x^2+x=10^12
を満たすxだが、
ざっくり、xが十分大きい時、x^2とxなら、xは無視できるので、
x^2=10^12
x=10^6
よって、xの範囲の最大値は10^6とする。
したがって、xの範囲は[left,right]=[1,10^6]。
x=mid=(left+right)/2として、
N種類の食品から、安い方を足し合わせた合計金額が、K以下か判定。
これを、right-left<=1まで繰り返す。
実装例
解き方に沿って解いた。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [N, K] = lines[0].split(" ").map(Number);
//何日目か、で二分探索してみる
let [left, right] = [1, 1000000];//xの範囲
while (right - left > 1) { //何日か、は整数なので１以下になれば良い
const mid = Math.trunc((left + right) / 2);
//mid日目の総額
let price = 0;//総額
for (let i = 1; i <= N; i++) {
const [A, B, C, D] = lines[i].split(" ").map(Number);
price += Math.min(A * mid + B, C * mid + D);//安い方選ぶ
}
//総額がK以下か
if (price <= K) { //総額priceがK以下なら、mid日未満もK以下で買える
left = mid;
} else { //総額priceがK超えたら、mid日以上も買えない
right = mid;
}
}
console.log(left);
実装例(Python3の場合参考)
合計金額が手持ちのお金K円より大きいかチェックする、関数checkを定義した。
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
const [N, K] = lines[0].split(" ").map(Number);
const ABCD = lines.slice(1).map(line => line.split(" ").map(Number));
//合計金額が手持ちのお金K円より大きかったらtrue,以下だったらfalse
const check = (x) => {
let sum = 0;
for (let abcd of ABCD) {
const [a, b, c, d] = abcd;
sum += Math.min(a * x + b, c * x + d);
}
if(sum <= K) {
return 0;
} else {
return 1;
}
};
//leftは常に条件を満たす，rightは常に条件を満たさない
let [left, right] = [1, 1 << 47];//xの範囲
while (right - left > 1) { //何日か、は整数なので１以下になれば良い
const mid = Math.trunc((left + right) / 2);
//総額がK以下かチェック
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
console.log(left);