paizaラーニング レベルアップ問題集 二分探索メニュー応用編 JavaScript ハイパーインフレーション

ハイパーインフレーション (paizaランク B 相当)

https://paiza.jp/works/mondai/binary_search_advanced/binary_search_advanced__hyperinflation

# 解き方

## 大きな流れをまとめる。

問題文把握。

条件から、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まで繰り返す。



# 実装例
解き方に沿って解いた。
```javascript
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を定義した。

```javascript
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);
```