E - 靴下のペアリング / Pairing Socks 解説 by admin
gemini-3.5-flash-thinking概要
この問題は、与えられた \(N\) 枚の靴下から \(M\) 組のペアを作り、それぞれのペアの色の濃さの差（違和感）の合計を最小化する問題です。
靴下を色の濃さでソートしたとき、ペアは必ず「隣り合う靴下同士」で組むのが最適になります。しかし、単純に差が小さい順に貪欲にペアを決めてしまうと、全体での最小値を得られないことがあります。そこで、「一度選んだペアをキャンセルして別のペアを選び直す（後悔）」 という操作を許容する「後悔付き貪欲法（反転可能貪欲法）」を用いて解きます。
考察
1. 靴下のソートと隣接要素の差
直感的に、色の濃さが近い靴下同士をペアにするのが最適です。靴下の配列 \(S\) を昇順にソートすると、最適なペアは必ずソート後の配列で隣り合う要素同士になります。 したがって、ソート後の隣り合う要素の差 \(D_i = S_{i+1} - S_i\) を要素とする配列を考え、この中から互いに隣接しないように \(M\) 個の要素を選び、その総和を最小化する問題に帰着されます（1つの靴下は複数のペアに属せないため、隣り合う \(D_i\) と \(D_{i+1}\) は同時に選べません）。
2. 単純な貪欲法の失敗
「差 \(D_i\) が小さいものから順に、隣接しないように \(M\) 個選ぶ」という単純な貪欲法では、以下のようなケースで最適な解が得られません。
- 具体例: \(S = [1, 10, 11, 20]\) で \(M=2\) の場合
- 隣り合う差は、\([9, 1, 9]\) です。
- 単純な貪欲法では、最も差が小さい中央の \(1\)（靴下 \(10\) と \(11\) のペア）をまず選びます。
- すると、両隣の \(9\) は選べなくなり、残りの靴下 \(1\) と \(20\) でペアを組むしかありません。このときの合計は \(1 + 19 = 20\) です。
- しかし、最適な選び方は \((1, 10)\) と \((11, 20)\) のペアで、合計は \(9 + 9 = 18\) です。
このように、「ある要素を選ぶと、その両隣が選べなくなる」という制約があるため、一時的に最適な選択が全体としての最適解を阻害することがあります。
3. 「後悔」を許す貪欲法
この問題を解決するために、「要素 \(i\) を選ぶ代わりに、その両隣の要素 \(i-1\) と \(i+1\) の両方を選ぶ」という選択肢を後から選べるようにします。
要素 \(i\) をすでに選んでいる状態から、それをキャンセルして両隣を選ぶときの「追加コスト（後悔値）」は以下のようになります。 $\(\text{追加コスト} = D_{i-1} + D_{i+1} - D_i\)$
この追加コストを新たな選択肢として優先度付きキュー（ヒープ）に挿入し、両隣の要素をリストから削除して繋ぎ直すことで、次のステップでこの「後悔」を選択できるようになります。
アルゴリズム
双方向連結リストと優先度付きキュー（最小ヒープ）を組み合わせてシミュレーションを行います。
初期化:
- 靴下の配列 \(S\) を昇順にソートします。
- 隣り合う要素の差 \(val[i] = S_i - S_{i-1}\) を計算します（1-indexed）。
- 双方向連結リストを表す配列
prev_node,next_nodeを作成し、各要素の左右のインデックスを保持します。端（\(0\) と \(N\)）には番兵として無限大（\(INF\)）を配置します。 - 優先度付きキュー
hqに、すべての \((val[i], i)\) を追加します。
\(M\) 回の選択ループ:
hqから最も値が小さい要素 \((v, idx)\) を取り出します。すでに削除されているインデックスの場合は無視して次を取り出します。- 答えに \(v\) を加算します。
- \(idx\) の両隣のインデックスを \(l = prev\_node[idx]\), \(r = next\_node[idx]\) とします。
- \(idx\), \(l\), \(r\) を使用済み（削除済み）にします。
- 後悔値の挿入: 新しい値 \(new\_val = val[l] + val[r] - v\) を計算し、これを \(val[idx]\) に代入して \(idx\) を未削除に戻します。
- 連結リストを更新し、\(idx\) の新しい両隣を \(ll = prev\_node[l]\) と \(rr = next\_node[r]\) に繋ぎ直します。
- 新しい選択肢 \((new\_val, idx)\) を
hqに追加します。
出力:
- \(M\) 回のループ終了後の合計値を書き出します。
計算量
- 時間計算量: \(O(N \log N)\)
- 靴下のソートに \(O(N \log N)\) 時間かかります。
- 優先度付きキューの操作（ポップ・プッシュ）は \(M\) 回のループでそれぞれ \(O(\log N)\) で行われるため、全体で \(O(M \log N)\) 時間です。\(M \le N/2\) より、全体の時間計算量は \(O(N \log N)\) となり、実行時間制限に十分間に合います。
- 空間計算量: \(O(N)\)
- 双方向連結リストや優先度付きキュー、削除フラグの管理に \(O(N)\) のメモリを使用します。
実装のポイント
双方向連結リストの配列表現: ポインタを使わずに、
prev_nodeとnext_nodeという配列を用いてインデックスで前後関係を管理することで、シンプルかつ高速に実装しています。番兵（\(INF\)）の配置: 配列の端（インデックス \(0\) と \(N\)）に非常に大きな値 \(INF\) を設定しておくことで、端の要素が選ばれた際にそれ以上外側を参照しようとすると無限大のコストがかかるようになり、境界条件の例外処理をスマートに回避しています。
遅延評価（Lazy Deletion）: 要素が削除されたかどうかを
deleted配列で管理し、キューから取り出した際にすでに削除されているものをスキップする「遅延評価」を行うことで、ヒープ内の不要な要素をその都度削除する手間を省いています。ソースコード
import sys
import heapq
def solve():
# Fast I/O
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
M = int(input_data[1])
S = [int(x) for x in input_data[2:]]
S.sort()
INF = 10**16
# Initialize the differences and doubly linked list
val = [0] * (N + 1)
val[0] = INF
val[N] = INF
for i in range(1, N):
val[i] = S[i] - S[i-1]
prev_node = list(range(-1, N))
next_node = list(range(1, N + 2))
next_node[N] = -1
deleted = [False] * (N + 1)
# Priority queue for greedy selection
hq = [(val[i], i) for i in range(1, N)]
heapq.heapify(hq)
ans = 0
for _ in range(M):
while hq:
v, idx = heapq.heappop(hq)
if not deleted[idx]:
break
ans += v
deleted[idx] = True
l = prev_node[idx]
r = next_node[idx]
deleted[l] = True
deleted[r] = True
# Insert the "regret" value to allow backtracking
new_val = val[l] + val[r] - v
val[idx] = new_val
deleted[idx] = False
ll = prev_node[l]
rr = next_node[r]
prev_node[idx] = ll
next_node[idx] = rr
if ll != -1:
next_node[ll] = idx
if rr != -1:
prev_node[rr] = idx
heapq.heappush(hq, (new_val, idx))
print(ans)
if __name__ == '__main__':
solve()
この解説は gemini-3.5-flash-thinking によって生成されました。