概要

各トラックの燃費係数 \(E_i\) と、全配送先の距離 \(C_j\) が与えられるとき、1台のトラックで全配送先を回る総燃料消費 \(E_i \times \sum C_j\) を最小にする問題です。

考察

トラック \(i\) が配送先 \(j\) に行く燃料は \(E_i \times C_j\) なので、全配送先を回る総燃料は

\[ \displaystyle \sum_{j=1}^{M} (E_i \times C_j) = E_i \times \sum_{j=1}^{M} C_j \]

となります。ここで重要なのは \(\sum C_j\) はどのトラックを選んでも同じ という点です。つまり、総燃料は「トラックごとに変わるのは \(E_i\) の部分だけ」であり、

• \(\sum C_j\) は固定
• よって総燃料を最小化するには \(E_i\) を最小にすればよい

と分かります。

素朴なアプローチの問題点

例えば「各トラックについて \(M\) 個の配送先分の燃料を計算して総和を取り、最小を探す」という方法だと、計算量は \(O(NM)\) になります。
\(N, M \le 10^5\) なので最悪 \(10^{10}\) 回程度の計算になり、時間内に終わりません（TLE）。

解決策

上の式変形により、必要なのは

• \(E_i\) の最小値：\(\min(E)\)
• 距離の合計：\(\sum C\)

の2つだけで、答えは \(\min(E) \times \sum C\) で求まります。

（例）\(E=[3,5,2]\), \(C=[4,1,6]\) のとき
\(\sum C=11\), \(\min(E)=2\) なので答えは \(2 \times 11 = 22\) です。

アルゴリズム

1. 配列 \(E\) の最小値 \(e_{\min} = \min(E)\) を求める
2. 配列 \(C\) の総和 \(s = \sum C\) を求める
3. 答えとして \(e_{\min} \times s\) を出力する

計算量

• 時間計算量: \(O(N + M)\)（最小値計算と総和計算を1回ずつ）
• 空間計算量: \(O(N + M)\)（入力配列を保持するため。読み方を工夫すれば \(O(1)\) も可能）

実装のポイント

• 答えは最大で \(10^4 \times (10^5 \times 10^4) = 10^{13}\) となり得ますが、Python の int は多倍長なのでオーバーフローの心配はありません。

• 入力が大きいので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    E = data[2:2+N]
    C = data[2+N:2+N+M]
    ans = min(E) * sum(C)
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。