TopCoder SRM 611 Div1
こんにちはtatsyです。
昨日行われましたSRM611の解説をしたいと思います。今回はEasyもMediumもコンテスト中にはよく分からずでした。まだまだ練習が足りません。では、早速Easyから。
Easy (250点)
問題
自然数からなる数列A, Bが与えられる。このときLCM(A)とはAに含まれる数の部分集合のLCM(最小公倍数)を全て含むような集合になっている。このときLCM(A)とLCM(B)が同じになるかどうかを調べよ。
解法
ポイントはAの部分集合のLCMを全て含むということで、つまりAの単一の元は必ずLCM(A)に含まれることになります。
もう1つのポイントは2つの集合S, Tについてlcm(lcm(S), lcm(T)) = lcm(S∪T)だということです。
この2つのポイントから、Bの各要素についてAの部分集合でその最小公倍数がそのBの要素に一致するものが必ず存在しており、また同様にAの各要素についてもBの部分集合でその最小公倍数がAの要素に一致するものが必ず存在していないといけないということになります。
そこでBのある要素B[i]に対して、B[i]を割り切るような全てのAの要素の最小公倍数をとり、それがB[i]に一致しているかどうかを調べます。これを全てのBの要素、そして関係をいれかえて全てのAの要素について調べれば、LCM(A)とLCM(B)が同じになるかどうかが分かるというわけです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(lint i=0; i<n; i++)
#define REPP(i,s,e) for(lint i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
class LCMSet {
public:
lint gcd(lint x, lint y) {
if(x < y) swap(x, y);
while(y!=0) {
lint t = x % y;
x = y;
y = t;
}
return x;
}
lint lcm(lint x, lint y) {
return x / gcd(x, y) * y;
}
bool check(vector<int>& a, int b) {
lint l = 1;
REP(i,a.size()) {
if(b % a[i] == 0) {
l = lcm(l, a[i]);
}
}
return l == b;
}
string equal(vector <int> A, vector <int> B) {
int na = A.size();
int nb = B.size();
sort(ALL(A));
sort(ALL(B));
bool ok = true;
REP(i,na) {
if(!check(B, A[i])) ok = false;
}
REP(i,nb) {
if(!check(A, B[i])) ok = false;
}
return ok ? "Equal" : "Not equal";
}
};
Medium (550点)
問題
平面上の(x[i], y[i])という位置にn個の街がある。この街のうち2つを選んで道を間に道を作り、合計でn-1本の道を作って全ての街を結ぶことを考える。このとき、建設される道の長さの標準偏差が最小になるとき、その値はいくつか？
解法
ちょっとまだ良く分かっていないのですが、やるべきことは、与えられた街を頂点として持つような完全グラフの最小領域木を作り、その時のエッジの重みの標準偏差が最小になるようにすることです。
問題は最小領域木を計算する時のエッジの重みをどのようにして決めるかということです。いくつかのコードを見たところ、まず頂点間のユークリッド距離を求めて、2つの距離の平均を、ある意味、平均の候補としてリストに入れています。
この平均の候補を順々に使いながら、グラフのエッジの重みをabs(dist[i][j] – avg_candidate)として最小領域木を計算しています。
いくつかのコードは2つの距離の平均をさらに2つとって平均を計算し、avg_candidateとして使っていました。またあるコードは適当にn-1個の頂点を選んでエッジの重みを計算し、avg_candidateとする操作をモンテカルロ的に繰り返しておりました。
いずれにしても、どのようにavg_candidateを得るかというのがポイントのようで、十分に密な候補を使えば、正しい平均をavg_candidateとしなくて良いみたいでした。ここにある理論をちゃんと理解したいところです。
以下は、何人かのコードを参考にしながら書いたコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <climits>
using namespace std;
typedef long long lint;
typedef pair<lint,lint> pll;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
class uftree {
public:
int n;
vector<int> val;
uftree(int n_) : n(n_), val(n_, -1) {}
int root(int x) { return (val[x] < 0) ? x : (val[x] = root(val[x])); }
void merge(int x, int y) {
x = root(x); y = root(y); if(x == y) return;
val[x] += val[y];
val[y] = x;
}
bool same(int x, int y) {
return root(x) == root(y);
}
int independent(int nn) {
int ret = 0;
for(int i=0; i<nn; i++) if(val[i] < 0) ret++;
return ret;
}
};
typedef tuple<double,int,int> load;
typedef pair<double,int> node;
double dist[22][22];
double graph[22][22];
bool vis[22];
class Egalitarianism2 {
public:
double minStdev(vector <int> x, vector <int> y) {
int n = x.size();
memset(dist, 0, sizeof(dist));
vector<double> vd;
REP(i,n) {
REPP(j,i+1,n-1) {
int dx = x[i] - x[j];
int dy = y[i] - y[j];
double d = hypot(dx, dy);
dist[i][j] = dist[j][i] = d;
vd.push_back(d);
}
}
sort(ALL(vd));
int ne = vd.size();
vector<double> all;
REP(i,ne) {
REPP(j,0,i-1) {
all.push_back((vd[i]+vd[j])/2.0);
}
}
sort(ALL(all));
double res = 1.0e20;
REP(it,all.size()) {
double cand = all[it];
vector<load> loads;
REP(i,n) {
REPP(j,0,i-1) {
loads.push_back(load(abs(dist[i][j] - cand), i, j));
}
}
sort(ALL(loads));
// prim
uftree uf(n);
vector<double> edges;
for(load l : loads) {
int a = get<1>(l);
int b = get<2>(l);
if(!uf.same(a, b)) {
uf.merge(a, b);
edges.push_back(dist[a][b]);
}
}
if(edges.size() != n-1) continue;
// compute answer
double avg = accumulate(ALL(edges), 0.0) / (n-1);
double std = 0.0;
REP(i,edges.size()) {
double d = (edges[i] - avg);
std += d * d;
}
std = sqrt(std / (n-1));
res = min(res, std);
}
return res;
}
};
まとめ
昨日はコンテスト中、全く解けそうな感じがしませんでした。ここのところ、解けなくても、それなりにいい感じの考え方はできていたのですが、まだまだ練習が足りないようです。