SRM611D1Med Egalitarianism2
こういう系，まったく思いつかない
問題概要(原文)
$N(1 \leq N \leq 20)$ 個の格子点がある．これに $N-1$ 本の辺を張って木にしたい．ここで，辺のコストはユークリッド距離に等しい．
木の得点を木に使われた辺のコストの標準偏差とする．木の得点の最小値を求めよ．
考察
標準偏差を最小化するには $\sum (avg - A_i)^2, avg= \frac{\sum A_i}{|A|}$ を最小化すればよい．
ここで，ある辺 $i,j$ のどちらかを使うべきか？というのは $avg$ の値により変化するが， $avg$ の値に近い方を使うべきである．平均値を全探索することはできないが，使うべき辺が変化する近傍は $2$ つの辺のコストの平均値を用いて全探索できる(というのもクラスカル法でのコストが平均値との差の絶対値で決まるから)． 計算量は $O(N^6logN)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class Egalitarianism2
{
public double minStdev(int[] X, int[] Y)
{
var n = X.Length;
var D = Enumerate(n * n, x =>
{
var p = x / n;
var q = x % n;
long dx = X[p] - X[q];
long dy = Y[p] - Y[q];
return Math.Sqrt(dx * dx + dy * dy);
}).Distinct().OrderBy(x => x).ToArray();
var min = double.MaxValue;
foreach (var a in D)
foreach (var b in D)
{
if (a <= b) break;
var c = (a + b) / 2;
var e = Enumerate(n * n, x =>
{
var p = x / n;
var q = x % n;
long dx = X[p] - X[q];
long dy = Y[p] - Y[q];
return new KeyValuePair<int, double>(x, Math.Sqrt(dx * dx + dy * dy));
});
Array.Sort(e, (l, r) => ((l.Value - c) * (l.Value - c)).CompareTo((r.Value - c) * (r.Value - c)));
var set = new DisjointSet(n);
var cost = new List<double>();
for (int i = 0; cost.Count < n - 1; i++)
{
if (set.Unite(e[i].Key / n, e[i].Key % n))
cost.Add(e[i].Value);
}
var avg = 0.0;
var val = 0.0;
foreach (var x in cost)
avg += x / (n - 1);
foreach (var x in cost)
val += (avg - x) * (avg - x);
min = Math.Min(min, val);
}
return Math.Sqrt(min / (n - 1));
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
#region DisjointSet
public class DisjointSet
{
public int[] par, ranks, count;
public DisjointSet(int n)
{
par = new int[n];
count = new int[n];
for (int i = 0; i < n; i++)
{
par[i] = i;
count[i] = 1;
}
ranks = new int[n];
}
public int this[int id] { get { return (par[id] == id) ? id : this[par[id]]; } }
public bool Unite(int x, int y)
{
x = this[x]; y = this[y];
if (x == y) return false;
if (ranks[x] < ranks[y])
{
par[x] = y;
count[y] += count[x];
}
else
{
par[y] = x;
count[x] += count[y];
if (ranks[x] == ranks[y])
ranks[x]++;
}
return true;
}
public int Size(int x) { return count[this[x]]; }
public bool IsUnited(int x, int y) { return this[x] == this[y]; }
}
#endregion
コメント
- どちらの辺を使うべきか？というのが変化する点の付近だけ試すというのは典型
- こういう系は定式化と，何ができれば解けるかというのがやっぱり大事
