概要

数直線上にある書棚へ本を返却する作業を、1回に最大 \(K\) 冊運べるという制約のもとで行い、カウンター（座標 \(0\)）に戻るまでの総移動距離を最小化します。

考察

重要な気づき 1：左右（正・負）を混ぜて運んでも得しない

書棚は数直線上にあり、カウンターは \(0\) です。
1回の移動で「正の位置」と「負の位置」を両方回ろうとすると、必ず \(0\) をまたいで移動することになります。

例えば、正側の最遠が \(a>0\)、負側の最遠が \(-b<0\) の本を同じ回で運ぶと、どんな順番でも移動距離は結局 - \(0 \to a \to -b \to 0\) とすると距離は \(a + (a+b) + b = 2a+2b\)

となり、正側だけの往復 \(2a\) と負側だけの往復 \(2b\) を足したのと同じです。
つまり 左右を混ぜても距離は減らない ので、正側・負側を独立に考えて最適化できます。

重要な気づき 2：片側だけなら「最遠まで往復」が最適

正側（あるいは負側）だけを考えます。ある回で持っていく本の書棚が同じ側にあるなら、

• 近い順（または遠い順）に寄りながら、最も遠い地点まで行って戻る

のが最適です。なぜなら数直線上では寄り道しても「最遠地点まで行く」こと自体は避けられず、途中の棚は通り道で回収できるからです。

よって、その回の移動距離は
\(2 \times (\text{その回で運ぶ本の中で最も遠い距離})\)
になります。

素朴にやるとダメな理由

「どの本をどの回に割り当てるか」を全探索したり、複雑なDPを組むと、組合せが爆発して \(N \le 2\times 10^5\) では到底間に合いません。

上の観察により、問題は - 正側の距離集合 - 負側の距離集合（絶対値）

をそれぞれ「1回で最大 \(K\) 個ずつ、最遠距離の往復コストでまとめる」だけに帰着します。

アルゴリズム

1. 座標 \(X_i\) を
   • \(X_i>0\) は pos にそのまま追加
   • \(X_i<0\) は neg に \(-X_i\)（絶対値）を追加
     （負側も「距離」として正の値で扱う）
2. pos, neg をそれぞれ 降順ソートする。
3. 各リストについて、先頭から \(K\) 個ずつまとめて運ぶのが最適：
   • 降順に並んでいるので、各グループの「最遠」はグループ先頭
   • よってインデックス \(0, K, 2K, \dots\) の要素だけ見て、合計に \(2 \times \text{その値}\) を足す
4. 正側と負側の合計が答え。

具体例：\(K=3\)、正側距離が [10, 8, 3, 2] なら
- 1回目に {10,8,3} を運ぶ：コスト \(2\times 10\) - 2回目に {2} を運ぶ：コスト \(2\times 2\)
合計 \(2\cdot 10 + 2\cdot 2\)。

計算量

• 時間計算量: \(O(N\log N)\)（正側・負側それぞれのソートが支配的）
• 空間計算量: \(O(N)\)（pos, neg の保持）

実装のポイント

• 負の座標は -x にして「距離」として扱うと、正側と同じ処理を流用できます。

• 降順ソートしておけば、for i in range(0, len(list), K): ans += 2*list[i] だけで「各回の最遠距離」を拾えます。

• \(N\) が大きいので、入力は sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    X = list(map(int, input().split()))

    pos = []
    neg = []
    for x in X:
        if x > 0:
            pos.append(x)
        else:
            neg.append(-x)

    pos.sort(reverse=True)
    neg.sort(reverse=True)

    ans = 0
    for i in range(0, len(pos), K):
        ans += 2 * pos[i]
    for i in range(0, len(neg), K):
        ans += 2 * neg[i]

    print(ans)

if __name__ == "__main__":
    main()

---

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