概要

\(N\) 台のトラックから1台を選び、\(M\) 個の配送先を順番に回る際に消費する燃料の総量を最小化する問題です。

考察

各トラック \(i\) には燃費係数 \(E_i\) が与えられており、配送先 \(j\) までの距離 \(C_j\) と共に、トラック \(i\) が配送先 \(j\) へ向かうときに消費する燃料は \(E_i \times C_j\) となります。

すべての配送先を訪れる必要があるため、どのトラックを選んでも走る距離の合計は \(\sum_{j=1}^{M} C_j\) で一定です。つまり、総距離はどのトラックでも同じであり、燃費係数 \(E_i\) が最も小さいトラックを選ぶのが最適になります。

したがって、単純にすべてのトラックについて総距離 × 燃費係数を計算して比較するのではなく、最小の燃費係数を選び、それに総距離をかければよいです。

この方法であれば、不要な繰り返し計算を避けられ、効率的に答えを求めることができます。

アルゴリズム

1. 各配送先の距離 \(C_1, C_2, ..., C_M\) の合計を求める：
   \(\text{total\_distance} = \sum_{j=1}^{M} C_j \)

2. 各トラックの燃費係数 \(E_1, E_2, ..., E_N\) の中から最小値を求める：
   \(\text{min\_E} = \min(E_1, E_2, ..., E_N)\)

3. 最小燃料消費量は以下のように求められる：
   \(\text{result} = \text{min\_E} \times \text{total\_distance}\)

この結果を出力すればよい。

計算量

• 時間計算量: \(O(N + M)\)
  （それぞれのリストに対して1回ずつ走査を行うため）
• 空間計算量: \(O(1)\)
  （入力データを除けば、定数個の変数のみを使用）

実装のポイント

• 総距離と最小燃費係数を別々に求めることで、効率よく計算できる。
• Python では sum() や min() を使うことで簡潔に実装可能。

ソースコード

# 入力の読み込み
N, M = map(int, input().split())
E = list(map(int, input().split()))
C = list(map(int, input().split()))

# 総距離を計算
total_distance = sum(C)

# 最小の燃費係数を求める
min_E = min(E)

# 最小燃料消費量を計算
result = min_E * total_distance

# 出力
print(result)

この解説は qwen3-coder-480b によって生成されました。