概要

図書館のカウンター（座標 \(0\)）から出発し、最大 \(K\) 冊ずつ本を運んで書棚に戻す作業を繰り返すとき、総移動距離を最小化する問題です。正の側と負の側を独立に処理し、各側で遠い本からグループ化する貪欲法で解けます。

考察

重要な気づき1: 正の側と負の側は独立に考えてよい

1回の往復で正の側と負の側の両方の書棚を回ることを考えてみましょう。例えば、正の側の最遠点 \(p\) と負の側の最遠点 \(-q\)（\(q > 0\)）を同時に回る場合、最適な経路は：

\[0 \to -q \to p \to 0 \quad \text{（距離: } q + (q + p) + p = 2p + 2q\text{）}\]

これは正の側だけの往復 \(2p\) と負の側だけの往復 \(2q\) を別々に行った場合とまったく同じ距離です。しかも、同時に運ぶと \(K\) 冊の容量を両側で分け合う必要があり、かえって往復回数が増える可能性があります。

したがって、正の側と負の側は完全に独立に処理するのが最適です。

重要な気づき2: 遠い本からグループ化する

片側だけ考えます。例えば正の側に本が \([1, 3, 5, 7, 9]\) の位置にあり、\(K = 2\) の場合：

• 1回目の往復: 座標 \(9, 7\) の本を運ぶ → コスト \(2 \times 9 = 18\)
• 2回目の往復: 座標 \(5, 3\) の本を運ぶ → コスト \(2 \times 5 = 10\)
• 3回目の往復: 座標 \(1\) の本を運ぶ → コスト \(2 \times 1 = 2\)

各往復のコストはそのグループで最も遠い本の位置 \(\times 2\)（往復するため）です。遠い本を一緒にまとめることで、近い本が「タダ乗り」でき、総距離が最小になります。

なぜ遠い方からグループ化するのか

往復のコストはグループ内の最遠点で決まります。遠い本どうしを同じグループにすれば、「高コストな往復」の回数を減らせます。逆に、遠い本と近い本を混ぜると、近い本のために別途往復が必要になり損です。

アルゴリズム

1. 本を正の座標と負の座標に分ける
2. 正の側: 座標を昇順にソートし、最も遠い本から \(K\) 冊ずつグループ化。各グループのコストは \(2 \times (\text{グループ内最遠座標})\)
3. 負の側: 絶対値を降順にソートし、同様に \(K\) 冊ずつグループ化。各グループのコストは \(2 \times (\text{グループ内最大絶対値})\)
4. 正の側のコスト合計と負の側のコスト合計を足して出力

具体例: \(N=5, K=2, X = [-4, -1, 2, 5, 8]\)

• 正の側 \([2, 5, 8]\): グループ \(\{8, 5\}\) → \(2 \times 8 = 16\), グループ \(\{2\}\) → \(2 \times 2 = 4\). 合計 \(20\)
• 負の側 \([-4, -1]\): グループ \(\{-4, -1\}\) → \(2 \times 4 = 8\). 合計 \(8\)
• 答え: \(20 + 8 = 28\)

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（正負に分けたリストの保持）

実装のポイント

• 負の座標は絶対値に変換してから処理すると、正の側と同じロジックで扱える

• グループ化はソート済み配列の末尾（最遠）から \(K\) 個飛ばしでインデックスを走査するだけで実現でき、シンプルに書ける

• 正の側・負の側のどちらかが空（本がない）場合でも正しく動くことを確認する

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    X = [int(input_data[i + 2]) for i in range(N)]
    
    # Separate positive and negative positions
    pos = sorted([x for x in X if x > 0])
    neg = sorted([x for x in X if x < 0], key=lambda x: -x)  # sorted by distance from 0, descending abs value first
    # neg is sorted so that neg[0] is the most negative (farthest), etc.
    # Actually let's sort neg by absolute value descending
    # neg values are negative, sorted by ascending means most negative first
    # We want groups where each trip takes the K farthest remaining books
    
    # For positive side: sort ascending. Group from farthest.
    # Each trip of K books: go to the farthest in the group and come back = 2 * farthest
    # Optimal: group the farthest K together, next K together, etc.
    # The farthest in each group determines the trip cost (2 * that distance)
    
    # For negative side: same logic with absolute values
    
    # Positive trips: take every K-th from the end
    pos_cost = 0
    # pos is sorted ascending, so pos[-1] is farthest
    # Groups: pos[-K:], pos[-2K:-K], etc.
    # The cost for each group is 2 * max of group = 2 * pos[last_in_group]
    i = len(pos) - 1
    while i >= 0:
        pos_cost += 2 * pos[i]
        i -= K
    
    # Negative trips: absolute values
    neg_abs = sorted([abs(x) for x in neg], reverse=True)
    neg_cost = 0
    i = 0
    while i < len(neg_abs):
        neg_cost += 2 * neg_abs[i]
        i += K
    
    # Now, we can potentially save one trip by combining the last trip on one side
    # with a trip on the other side. Specifically, the farthest positive trip and
    # the farthest negative trip can potentially be combined into one trip if we
    # have capacity, but actually they can't share capacity since we must visit both sides.
    
    # Wait, actually the key optimization: on one trip, we can go both left and right.
    # In that case, the cost is 2 * max(farthest_left, farthest_right) instead of
    # 2 * farthest_left + 2 * farthest_right. But we use K capacity for both sides.
    
    # Actually, re-reading the problem: each trip starts and ends at 0. On a single trip,
    # we can carry up to K books and visit multiple shelves in any order.
    # The optimal path for a trip visiting shelves on both sides: go to one extreme, 
    # come back through 0, go to other extreme, come back. Cost = 2*max_pos + 2*max_neg.
    # Or go to one side first then the other: cost = max_pos + max_pos + max_neg + max_neg... 
    # Actually no: go right to max_pos, come back to 0, go left to max_neg, back to 0:
    # cost = 2*max_pos + 2*|max_neg|. Same as separate trips!
    # 
    # Better: go left to max_neg, then all the way right to max_pos, then back to 0:
    # cost = |max_neg| + (|max_neg| + max_pos) + max_pos = 2*max_pos + 2*|max_neg|
    # Hmm, that's the same. Wait: |max_neg| + |max_neg| + max_pos + max_pos? No.
    # Path: 0 -> max_neg -> max_pos -> 0. Distance = |max_neg| + |max_neg - max_pos| + max_pos
    #   = |max_neg| + |max_neg| + max_pos + max_pos = 2*(|max_neg| + max_pos). Same.
    # 
    # So combining doesn't help at all in terms of distance. The only saving would be
    # if we save a trip. But the distance is the same.
    # 
    # Therefore, positive and negative sides are completely independent.
    
    print(pos_cost + neg_cost)

solve()

---

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