概要

\(N\) 台のトラックから1台を選び、\(M\) 個の配送先すべてを回るときの燃料消費量を最小化する問題です。燃費係数が最小のトラックを選び、全配送先の距離の合計との積を計算すれば答えが求まります。

考察

重要な気づき

トラック \(i\) を選んだときの総燃料消費量を考えてみましょう。

トラック \(i\) が全配送先を回るときの燃料消費量は： \(E_i \times C_1 + E_i \times C_2 + \cdots + E_i \times C_M\)

これは \(E_i\) でくくることができて： \(E_i \times (C_1 + C_2 + \cdots + C_M) = E_i \times \sum_{j=1}^{M} C_j\)

となります。

具体例で確認

例えば、\(N = 2, M = 3\) で、\(E = [3, 2]\)、\(C = [10, 20, 30]\) の場合：

• トラック1を選ぶと：\(3 \times 10 + 3 \times 20 + 3 \times 30 = 3 \times 60 = 180\)
• トラック2を選ぶと：\(2 \times 10 + 2 \times 20 + 2 \times 30 = 2 \times 60 = 120\)

どのトラックを選んでも、距離の合計 \(\sum C_j = 60\) は変わりません。

最適な選択

総燃料消費量 \(E_i \times \sum C_j\) を最小化するには、\(\sum C_j\) は固定なので、\(E_i\) が最小のトラックを選べばよいことが分かります。

素朴なアプローチとの比較

素朴に「各トラックについて、各配送先との燃料消費を計算して足し合わせる」と \(O(N \times M)\) かかり、\(N, M\) が最大 \(10^5\) のとき \(10^{10}\) 回の計算となりTLEの危険があります。

しかし、上記の考察により、\(E_i\) の最小値と \(C_j\) の合計だけ求めれば良いので、効率的に解けます。

アルゴリズム

1. 配列 \(E\) から最小値 \(\min(E)\) を求める
2. 配列 \(C\) の総和 \(\sum C\) を求める
3. \(\min(E) \times \sum C\) を出力する

計算量

• 時間計算量: \(O(N + M)\)
  • \(E\) の最小値を求めるのに \(O(N)\)
  • \(C\) の総和を求めるのに \(O(M)\)
• 空間計算量: \(O(N + M)\)
  • 入力を格納するのに必要

実装のポイント

• Pythonでは min() 関数と sum() 関数を使うことで、簡潔に実装できます

• 制約より、答えの最大値は \(10^4 \times 10^4 \times 10^5 = 10^{13}\) 程度になる可能性がありますが、Pythonでは整数のオーバーフローを気にする必要がないため、そのまま計算できます

  ソースコード

N, M = map(int, input().split())
E = list(map(int, input().split()))
C = list(map(int, input().split()))

min_E = min(E)
sum_C = sum(C)

print(min_E * sum_C)

---

この解説は claude4.5opus によって生成されました。