解説 - AtCoder Weekday Contest 0156 Beta

公式

E - 靴下のペアリング / Pairing Socks 解説 by kyopro_friends

$S$ をソートして靴下 index を振り直します。最適解において、ペアにするのは隣接する靴下のみとしてよいです。

そうでないペアが存在したとし、そのうち index が最小のものをとり $(i,j)$ $(i< j)$ とします。$i+1$ が他のペアとして使われていなければ、$(i,j)$ のペアを $(i,i+1)$ に置き換えて損をしません。$i+1$ が他の靴下 $k$ とペアとして使われているとき、ペア $(i,j),(i+1,k)$ を $(i,i+1),(j,k)$ に置き換えて損をしません（$i$ の最小性より $i+1 < j < k$ または $k < j$ が成り立つことから示せます）。よってこの操作の繰り返しにより損をすることなく全てのペアを隣接する靴下のみとすることができます。

靴下 $i$ と $i+1$ をペアにしたときの違和感を $D_i$ とします。問題は「$D_1,\dots,D_{N-1}$ から、隣接しない $M$ 個の要素を選び、その和を最小化せよ」となります。（隣接する要素を選べないのは「$i$ と $i+1$ をペアにする」「$i+1$ と $i+2$ をペアにする」を同時に実現できないことに由来します）

この問題は ABC218H などで知られている通り、次のような貪欲法により解くことができます。

問題： $A=(A_1,\dots,A_N)$ から、隣接しない $K$ 個の要素を選び、その和を最小化せよ。

解法：

スコアを $0$ とする。

以下の操作を $M$ 回繰り返す。

$A$ の最小要素を $A_i$ とする。スコアに $A_i$ を加算する。$A_i$ を $A_{i-1}+A_{i+1}-A_i$ に置き換え、$A_{i-1},A_{i+1}$ を $A$ から削除し、順序を保って連結する。（範囲外の添字に対しては $A_i=\infty$ と定める）

操作後のスコアが求める解である。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> s(n);
  for(int i=0; i<n; i++) cin >> s[i];
  sort(s.begin(), s.end());

  vector<ll> data({INF, INF});
  for(int i=0; i<n-1; i++){
    data.push_back(s[i+1]-s[i]);
  }
  data.push_back(INF);
  data.push_back(INF);
  
  n = data.size();
  vector<int> pre(n), nxt(n);
  iota(pre.begin(), pre.end(), -1);
  iota(nxt.begin(), nxt.end(), 1);
  
  priority_queue<pair<ll,int>> q;
  for(int i=0; i<n; i++){
    q.push({-data[i], i});
  }
  ll ans = 0;
  for(int x=0; x<m; x++){
    ll v;
    int i;
    while(true){
      v = q.top().first;
      i = q.top().second;
      q.pop();
      v = -v;
      if(data[i]==v) break;
    }
    ans += v;
    data[i] = data[pre[i]] + data[nxt[i]] - v;
    q.push({-data[i], i});
    // remove pre
    data[pre[i]] = INF;
    int k = pre[pre[i]];
    nxt[k] = i;
    pre[i] = k;
    // remove nxt
    data[nxt[i]] = INF;
    k = nxt[nxt[i]];
    nxt[i] = k;
    pre[k] = i;
  }

  cout << ans << endl;
}

実装例 (Python)

import heapq
N, M = map(int, input().split())
S = list(map(int, input().split()))
S.sort()

INF = 10**18
data = [INF]*2 + [S[i+1]-S[i] for i in range(N-1)] + [INF]*2
n = len(data)
pre = list(range(-1, n-1))
nxt = list(range(1, n+1))

q = [(v, i) for i, v in enumerate(data)]
heapq.heapify(q)
ans = 0
for _ in range(M):
  while True:
    v, i = heapq.heappop(q)
    if data[i] == v:
      break
  ans += v
  data[i] = data[pre[i]] + data[nxt[i]] - v
  heapq.heappush(q, (data[i], i))
  # remove pre
  data[pre[i]] = INF
  k = pre[pre[i]]
  nxt[k] = i
  pre[i] = k
  # remove nxt
  data[nxt[i]] = INF
  k = nxt[nxt[i]]
  nxt[i] = k
  pre[k] = i

print(ans)