概要

\(N\) 台のトラックの中から 1 台を選び、全 \(M\) 個の配送先を順に回ったときの燃料消費量の合計を最小化する問題です。

考察

まず、特定のトラック \(i\) を選んだ場合の燃料消費量の合計を式に表してみましょう。 トラック \(i\) の燃費係数を \(E_i\)、各配送先への距離を \(C_1, C_2, \ldots, C_M\) とすると、合計燃料消費量は以下のようになります。

\[(E_i \times C_1) + (E_i \times C_2) + \dots + (E_i \times C_M)\]

この式は、共通因数である \(E_i\) でくくることができます（分配法則）。

\[E_i \times (C_1 + C_2 + \dots + C_M)\]

ここで、\((C_1 + C_2 + \dots + C_M)\) の部分は、どのトラックを選んでも変わらない一定の値（配送ルートの総距離）です。これを \(S\) と置くと、合計燃料消費量は \(E_i \times S\) と非常にシンプルな形で表せます。

\(S\) は正の値であるため、\(E_i \times S\) を最小化するためには、燃費係数 \(E_i\) が最も小さいトラックを選べばよいということがわかります。

なぜ素朴な計算ではいけないのか

もし「すべてのトラック（\(N\)台）について、すべての配送先（\(M\)個）の燃費を計算して足し合わせる」という二重ループの処理を行うと、計算量は \(O(N \times M)\) となります。 本問題では \(N, M \leq 10^5\) であるため、最大で \(10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。上記の数式変形によって、計算量を大幅に削減することが不可欠です。

アルゴリズム

1. 配送先への距離の合計 \(S = \sum_{j=1}^{M} C_j\) を計算する。
2. トラックの燃費係数の最小値 \(E_{min} = \min(E_1, E_2, \ldots, E_N)\) を求める。
3. \(E_{min} \times S\) を計算して出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • トラックの最小値を探すのに \(O(N)\)、配送先の合計を出すのに \(O(M)\) かかります。
• 空間計算量: \(O(N + M)\)
  • 入力値をリスト等に保持する場合、その要素数分のメモリが必要です。

実装のポイント

• 高速な入力: \(N, M\) が \(10^5\) 規模と大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が高速です。

• 合計と最小値: sum() 関数や min() 関数といった標準の組み込み関数を使うことで、簡潔かつ高速に処理を行うことができます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # この手法は、N, M が 10^5 程度の規模であれば Python で高速に動作します
    data = sys.stdin.read().split()
    
    if not data:
        return
    
    # トラックの数 N と配送先の数 M を取得
    n = int(data[0])
    m = int(data[1])
    
    # トラック i が全配送先を巡回する際の合計燃料消費量は、
    # Σ (E_i * C_j) = E_i * Σ C_j と計算できる。
    # これを最小化するためには、燃費係数 E_i が最小のトラックを選択すればよい。
    
    # トラックの燃費係数 E_i のリストから最小値を取得
    # E_i はリストの 2 番目から n 個分
    min_e = min(map(int, data[2 : n + 2]))
    
    # 配送先へのルート距離 C_j の合計を計算
    # C_j はリストの n + 2 番目から m 個分
    sum_c = sum(map(int, data[n + 2 : n + m + 2]))
    
    # 最小の燃料消費量を出力
    print(min_e * sum_c)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。