読者です 読者をやめる 読者になる 読者になる

Codeforces Round #317 Div1 B: Minimization

問題

codeforces.com

解法

「N人をK個のグループに分ける。グループの人数はN/KまたはN/K+1でなければならない。グループの人間を身長順にソートした時の隣接する2人の身長の差の合計を、グループのコストとする。グループのコストの合計の最小値はいくつか?」という問題に読み替える。

グループのコストは、一番大きい人と一番小さい人の差であることに気付く。なのでグループ内の身長はできるだけ近いほうが良い。

新しくグループを作る時にグループ内で一番小さい人を決めると、グループの人数をN/Kにするか、それともN/K+1にするか、ということが問題になる。それぞれの場合について動的計画法で求めてやれば良い。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private final long INF = Long.MAX_VALUE / 4;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int groups = scanner.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = scanner.nextInt();
		}
		Arrays.sort(A);

		int member = N / groups;
		int bigGroups = N % groups;// メンバーが1人多いグループの数

		long[] dp = new long[groups + 1];
		Arrays.fill(dp, INF);
		dp[0] = 0;

		long[] dp2 = new long[groups + 1];

		// dp[groupNum][bigNum]:=groupNum個グループを作った時、bigNum個bigGroupを作った時の最小値
		for (int groupNum = 1; groupNum <= groups; ++groupNum) {
			Arrays.fill(dp2, INF);

			for (int bigs = bigGroups; bigs >= 0; bigs--) {
				// bigsは今までに作ったbigGroupの数
				int start = (groupNum - 1) * member + bigs;

				// 新しく作るグループがbigGroupでない場合
				int cost = Math.abs(A[start + member - 1] - A[start]);
				dp2[bigs] = Math.min(dp[bigs] + cost, dp2[bigs]);

				// 新しく作るグループがbigGroupある場合
				if (bigs == bigGroups) {
					continue;
				}
				int bigCost = Math.abs(A[start + member] - A[start]);
				dp2[bigs + 1] = Math.min(dp2[bigs + 1], dp[bigs] + bigCost);

			}

			// コピーする
			for (int j = 0; j <= groups; j++) {
				dp[j] = dp2[j];
			}
		}
		System.out.println(dp[bigGroups]);
		scanner.close();
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}