概要

数直線上の原点（座標 \(0\)）から出発し、最大 \(K\) 冊の本を \(N\) 箇所の書棚へ送り届けては原点に戻る作業を繰り返します。すべての本を戻し終えて原点に帰還するまでの最小の移動距離を求める問題です。

考察

この問題を解くための重要なポイントは、「一度の移動でどの本を運ぶか」と「移動の効率化」の2点です。

1. 正の方向と負の方向を分けて考える 一度の往復で正の座標にある書棚と負の座標にある書棚を同時に回るのは非効率です。例えば、座標 \(10\) と \(-10\) に本を届ける場合、別々に往復すると距離は \(10 \times 2 + 10 \times 2 = 40\) です。一度に回ると \(10 - (-10) = 20\) の移動に見えますが、最終的に原点に戻る必要があるため、結局 \(0 \to 10 \to -10 \to 0\) と移動すると距離は \(10 + 20 + 10 = 40\) となり、分ける場合と変わりません。むしろ、途中で \(K\) 冊の制限があるため、正負を分けて管理する方がシンプルで最適です。

2. 遠い場所にある本を優先的にまとめる（貪欲法） ある地点 \(D\) まで本を届けに行くとき、その道中にある書棚（原点から \(D\) までの間にある書棚）には、追加の移動距離なしで立ち寄ることができます。 移動距離を短くするには、「最も遠い場所へ行くついでに、その近くにある本をまとめて運ぶ」のが最善です。したがって、座標を遠い順に並べ、 \(K\) 冊ずつまとめて運ぶことで、往復回数と移動距離を最小限に抑えられます。

3. すべての移動は往復である 問題文に「最終的にカウンター（原点）に戻る必要がある」と明記されているため、各グループの移動距離は「そのグループの中で最も遠い座標までの距離 \(\times 2\)」となります。

アルゴリズム

1. 与えられた座標を、正の数（pos）と負の数（neg）の2つのグループに分けます。負の数は計算しやすいように絶対値に変換しておきます。
2. それぞれのグループを、原点から遠い順（降順）にソートします。
3. 各グループにおいて、先頭（最も遠い地点）から \(K\) 冊ずつまとめて運びます。
   • 1回目： \(0\) 番目の座標（最も遠い）を往復する
   • 2回目： \(K\) 番目の座標（次に遠いグループの端）を往復する
   • 3回目： \(2K\) 番目の座標を往復する……
4. これらの往復距離（座標の絶対値 \(\times 2\)）をすべて合計したものが答えとなります。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標の仕分けに \(O(N)\)、ソートに \(O(N \log N)\)、距離の集計に \(O(N/K)\) かかります。全体としてソートが支配的です。
• 空間計算量: \(O(N)\)
  • 入力された座標を保持するためのリストのメモリが必要です。

実装のポイント

• 効率的な入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を使って一括で入力を取得すると高速です。

• スライスの活用: range(0, len(list), K) を使うことで、各グループの先頭（そのグループでの最大距離）を簡単に抽出できます。

• 負の数の扱い: 負の座標はあらかじめ abs() で絶対値にしておくことで、正の座標側と全く同じロジックで計算できるようになります。

  ソースコード

import sys

# 競技プログラミングの問題「図書館の本の返却」を解くためのプログラムです。
# この問題では、カウンター（座標0）から出発し、最大K冊の本を各書棚（座標Xi）に運び、
# 毎回カウンターに戻るという作業を繰り返します。
# すべての本を運び終えた後、最終的にカウンターに戻るまでの最小移動距離を求めます。

def solve():
    # 標準入力からすべてのデータを一括で読み込み、スペースや改行で分割します。
    # 大規模な入力（N=2*10^5）に対して効率的に処理を行うためです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 本の冊数, K: 一度に持てる最大冊数
    N = int(input_data[0])
    K = int(input_data[1])
    
    # X: 各書棚の座標
    X = list(map(int, input_data[2:]))
    
    # 正の座標と負の座標に分けます。
    # 座標が0の書棚は存在しない（Xi != 0）という制約があります。
    # 正の側と負の側は独立して（別々の往復で）運ぶのが最適です。
    pos = []
    neg = []
    for x in X:
        if x > 0:
            pos.append(x)
        else:
            # 負の座標は絶対値で管理します。
            neg.append(abs(x))
    
    # それぞれのリストを降順（原点から遠い順）にソートします。
    # 遠い場所にある本を運ぶ際、そのついでに近くの本（最大K-1冊）も運ぶことで、
    # 往復の回数を最小限にし、総移動距離を短縮できます。
    pos.sort(reverse=True)
    neg.sort(reverse=True)
    
    total_distance = 0
    
    # 正の座標側の計算:
    # 遠い順にK冊ずつまとめて運びます。
    # 各グループにおいて、最も遠い座標を往復するため、距離は 2 * pos[i] となります。
    for i in range(0, len(pos), K):
        total_distance += 2 * pos[i]
        
    # 負の座標側の計算:
    # 同様に、遠い順にK冊ずつまとめて往復の距離を加算します。
    for i in range(0, len(neg), K):
        total_distance += 2 * neg[i]
        
    # 求まった最小の総移動距離を出力します。
    # 問題文の指示通り、最後の移動後もカウンターに戻る必要があるため、
    # すべてのグループの移動距離を往復分（2倍）で計算しています。
    print(total_distance)

if __name__ == '__main__':
    solve()

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