THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）の参加記録です。
ヒューリスティックコンテストには参加したこと無かったのですが、今回は4時間と短めの時間設定だったので参加してみました。
問題概要
800x800の二次元座標上に400個の頂点と1995個の辺がランダムに与えられるので、すべての頂点が連結になるように辺を採択せよ。ただし、採用した辺のコストの総和が小さいほうがより良い得点になる（理想は最小全域木になる）。
得点：6,600,871,568（何も考えずUnionFind）
問題文を誤読していて、入力で各辺の実際のコストlが与えられるのに気づかずに提出して、意図しない形でACしました。
順番に与えられた辺に対して、「連結じゃないなら併合する」というUnionFindをし続けるとこの点数になります。
その後、実際の辺のコストの決まり方が一様分布と仮定して95%予言的中区間的なものを計算しようとしたり、「UnionFindで2点間の辺を取り除いたときにまだ連結しているか」みたいなのを実装してごちゃごちゃしてましたが、結局、最後まで時間内にこの得点を上回ることができないという悲しい結果になりました。
以下はUnionFindの実装。
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define intceil(a,b) ((a+(b-1))/b)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long,long>;
const long long INF = LONG_LONG_MAX - 1001001001001001;
void chmax(int& x, int y) { x = max(x,y); }
void chmin(int& x, int y) { x = min(x,y); }
template <typename T>
struct UnionFindVerSize {
private:
vector<T> sizes;
vector<T> parents;
T group_num;
public:
vector<set<ll>> graph;
UnionFindVerSize(T N=0): sizes(N,1), parents(N) {
for (T i=0; i<N; i++) {
parents[i] = i;
}
this->group_num = N;
graph.resize(N);
}
T find_root(T x) {
if (this->parents[x] == x) return x;
this->parents[x] = this->find_root(this->parents[x]);
return this->parents[x];
}
void unite(T x, T y) {
T gx = this->find_root(x); T gy = this->find_root(y);
if (gx == gy) return;
if (this->sizes[gx] < this->sizes[gy]) {
this->parents[gx] = gy;
this->sizes[gy] += this->sizes[gx];
}
else {
this->parents[gy] = gx;
this->sizes[gx] += this->sizes[gy];
}
this->group_num--;
graph[x].insert(y);
graph[y].insert(x);
}
void disunite(T x, T y) {
graph[x].erase(y);
graph[y].erase(x);
}
bool is_cycle_if_disunite(T x, T y) {
deque<T> deq;
set<T> visited;
deq.push_back(x);
while(!deq.empty()) {
T u = deq.front(); deq.pop_front();
if (visited.count(u)) continue;
visited.insert(u);
for(T v: graph[u]) {
if (u==x && v==y) continue;
if (visited.count(v)) continue;
if (v == y) {
return true;
}
deq.push_back(v);
}
}
return false;
}
T get_size(T x) {
return this->sizes[this->find_root(x)];
}
bool is_same_group(T x, T y) {
return this->find_root(x) == this->find_root(y);
}
T get_group_num() {
return this->group_num;
}
void print_parents() {
for (T i=0; i<this->parents.size(); i++) {
cout << this->parents[i] << endl;
}
}
void print_sizes() {
for (T i=0; i<this->sizes.size(); i++) {
cout << this->sizes[i] << endl;
}
}
};
以下はこの手法の実装。誤読して実際のコストlの入力を受け取ってない。うーん。
ll distance(ll x1, ll y1, ll x2, ll y2) {
return (ll)round(sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)));
}
void solve() {
ll N = 400, M = 1995;
vector<ll> X(N), Y(N);
for(ll i=0; i<N; i++) {
cin >> X[i] >> Y[i];
}
UnionFindVerSize uf = UnionFindVerSize<ll>(N);
for(ll i=0; i<M; i++) {
ll u, v;
cin >> u >> v;
if (uf.get_group_num() == 1) {
printf("0\n"); cout << flush;
continue;
}
if (uf.is_same_group(u, v)) {
printf("0\n"); cout << flush;
continue;
}
printf("1\n"); cout << flush;
uf.unite(u, v);
}
}
int main() {
solve();
return 0;
}
得点：1,338,761,965（バグらせ）
すべての出力を1にする（すべての辺を採択する）とこの点数になります。
後述するクラスカル法をバグらせてこれをやりました。
得点：12,599,835,049（クラスカル法）
ここからはコンテスト後の話になります。
与えられる辺の順番はわかっているので、2点間の距離dは求めることができます。しかしこの問題のミソは、実際の辺のコストはdじゃなくて[d, 3d]の区間でランダムに決まるというものです。
でもまあ辺のコストを全て2dと仮定してクラスカル法で最小全域木を求めてもそれなりに良いスコアがでるだろう（そしてそれを改良していけばいいだろう）という仮説のもと、普通にクラスカル法を実装しました。するとこの点数になります。
以下はクラスカル法の実装。
struct edge {long long u, v, cost; };
bool comp(const edge& e1, const edge& e2) {
return e1.cost < e2.cost;
}
pair<UnionFindVerSize<long long>, long long> kruskal(vector<edge> es, long long V, long long E) {
sort(es.begin(), es.end(), comp);
UnionFindVerSize uf = UnionFindVerSize<long long>(V);
long long res = 0;
for (long long i=0; i<E; i++) {
edge e = es[i];
if (!uf.is_same_group(e.u, e.v)) {
uf.unite(e.u, e.v);
res += e.cost;
}
}
return {uf, res};
}
以下はこの手法の実装。
void solve() {
ll N = 400, M = 1995;
ll MAX_DISTANCE = distance(0,0,800,800);
vector<ll> X(N), Y(N);
for(ll i=0; i<N; i++) {
cin >> X[i] >> Y[i];
}
vector<edge> es(M);
for(ll i=0; i<M; i++) {
ll u, v;
cin >> u >> v;
edge e = {u, v, 2*distance(X[u], Y[u], X[v], Y[v])};
es[i] = e;
}
auto [kuf, kuf_cost] = kruskal(es, N, M);
for(ll i=0; i<M; i++) {
ll l; cin >> l;
auto [u, v, d] = es[i];
if (kuf.graph[u].count(v)) {
cout << "1" << endl << flush;
}
else {
cout << "0" << endl << flush;
}
}
}
int main() {
solve();
return 0;
}
得点：13,901,664,333（毎回クラスカル法）
頂点数Nが400で辺数Mが1995なので、O(M2)くらいでもいけることに（ようやく）気づきます。
クラスカル法の計算量がO(|M| log|N|)なので（実際はソートやUnionFindを使うので違うが）、実際のコストlが与えられたときに毎回クラスカル法で最小全域木を構築しても計算量はO(M2 log|N|)で間に合います。
具体的には以下のような実装をしました。
- 最初に辺(u, v)が与えられるとき、2点間の距離dを求めて、この辺のコストを2dと仮定しておく。
- 実際の辺(u, v)のコストlが与えられるとき、辺のコストを2dからlに更新し、クラスカル法で最小全域木を求める。求めた最小全域木で辺(u, v)が採択されていれば、この辺を採択する。そうでなければこの辺は採択しない。
- 採択した辺は覚えておく。これ以降のクエリで最小全域木を構築するときに、必ずこの辺を使わなければならないから。
- 採択しなかった辺も覚えておく。これ以降のクエリで最小全域木を構築するときに、必ずこの辺を除外しなければならないから。
以下がこの手法の実装になります。
pair<UnionFindVerSize<long long>, long long> kruskal2(vector<edge> es, long long V, long long E, const vector<edge> &connected, const set<pair<ll,ll>> &disconnected) {
sort(es.begin(), es.end(), comp);
UnionFindVerSize uf = UnionFindVerSize<long long>(V);
long long res = 0;
for(edge e: connected) {
uf.unite(e.u, e.v);
res += e.cost;
}
for (long long i=0; i<E; i++) {
edge e = es[i];
if (disconnected.count({e.u, e.v})) continue;
if (!uf.is_same_group(e.u, e.v)) {
uf.unite(e.u, e.v);
res += e.cost;
}
}
return {uf, res};
}
void solve() {
ll N = 400, M = 1995;
ll MAX_DISTANCE = distance(0,0,800,800);
vector<ll> X(N), Y(N);
for(ll i=0; i<N; i++) {
cin >> X[i] >> Y[i];
}
vector<edge> es(M);
for(ll i=0; i<M; i++) {
ll u, v;
cin >> u >> v;
edge e = {u, v, 2*distance(X[u], Y[u], X[v], Y[v])};
es[i] = e;
}
vector<edge> connected;
set<pair<ll,ll>> disconnected;
for(ll i=0; i<M; i++) {
ll l; cin >> l;
auto [u, v, d] = es[i];
es[i] = {u, v, l};
auto [kruskal_uf, kruskal_cost] = kruskal2(es, N, M, connected, disconnected);
if (kruskal_uf.graph[u].count(v)) {
cout << "1" << endl << flush;
connected.push_back(es[i]);
}
else {
cout << "0" << endl << flush;
disconnected.insert({es[i].u, es[i].v});
}
}
}
最初の辺のコストをすべて2dと仮定しましたが、うまい値に設定すれば上振れ狙えると思います。（モンテカルロ法を使えばいい？）
まとめ
- コンテスト中の得点は意図せずACした6,600,871,568で、順位も539/632と残念な結果でした。最終的には得点を倍以上の13,901,664,333まで上げる実装を見つけることができました。
- 解説はプリム法と書いてあるけどプリム法を知らなかった。
- 4時間というコンテスト時間は個人的にはちょうど良かったです。
- ビジュアライザがうまく実装されていてきれいで、動かすのが楽しかった。
- C++のstd::setに構造体を入れることができないことを知りました。
得点：13,921,417,428【追記2021/12/15】
Twitter見てたら上のように書いている方がいて、なるほど多数決を採る手法があるのかと思いました。
というわけで以下の実装をしてみました。
- 並行世界
world[WORLD_NUM]を作成する。並行世界は各辺の情報をそれぞれ持つ。
- 最初に辺(u, v)が与えられるとき、2点間の距離dを求めて、この辺のコストを[d, 3d]の区間でランダムに決める。これをすべての並行世界にやる。
- 実際の辺(u, v)のコストlが与えられるとき、辺のコストをlに更新し、クラスカル法で最小全域木を求める。求めた最小全域木で辺(u, v)が採択されていれば、この辺を採択する。そうでなければこの辺は採択しない。これをすべての並行世界でやる。
- 各並行世界で「辺を採択した/しなかった」のどちらが多かったかを多数決を採り、多かったほうを採用する。
それを実装したのが以下になるのですが、WORLD_NUM = 3程度でもTLEしました。
void solve() {
random_device rnd;
mt19937 mt(rnd());
ll N = 400, M = 1995;
vector<ll> X(N), Y(N);
for(ll i=0; i<N; i++) {
cin >> X[i] >> Y[i];
}
ll WORLD_NUM = 19;
vector<vector<edge>> world(WORLD_NUM, vector<edge>(M));
for(ll i=0; i<M; i++) {
ll u, v;
cin >> u >> v;
ll d = distance(X[u], Y[u], X[v], Y[v]);
uniform_int_distribution<> myrand(d, 3*d);
for(ll w=0; w<WORLD_NUM; w++) {
edge e = {u, v, 2*d};
world[w][i] = e;
}
}
vector<edge> connected;
set<pair<ll,ll>> disconnected;
for(ll i=0; i<M; i++) {
ll l; cin >> l;
ll u = world[0][i].u;
ll v = world[0][i].v;
ll vote = 0;
for(ll w=0; w<WORLD_NUM; w++) {
world[w][i] = {u, v, l};
auto [kruskal_uf, kruskal_cost] = kruskal2(world[w], N, M, connected, disconnected);
if (kruskal_uf.graph[u].count(v)) {
vote++;
}
}
if (vote > WORLD_NUM/2) {
cout << "1" << endl << flush;
connected.push_back({u, v, l});
}
else {
cout << "0" << endl << flush;
disconnected.insert({u, v});
}
}
}
TLEの主な原因は、毎回最初からクラスカル法をするのが重いからでしょう。
よくよく考えてみれば毎回最初からUnionFind木を構築する必要はなく、実際の辺のコストが与えられてその辺を採択する/しないを決めたあとは、そのときのUnionFind木を保存しといて次回はそこから再開すればいいです。
また辺のソートについても毎回最初からする必要はなく、確定した辺についてはソートしなくてよいので、sort(es.begin()+i, es.end(), comp);のように必要のある辺だけソートすればいいはずです（本当？）。
そのように改良したのが以下になり、これをするとWORLD_NUM = 5でも実行可能になり、得点は13,918,225,210～13,921,417,428くらいになりました。
pair<UnionFindVerSize<long long>, long long> kruskal3(ll start, vector<edge> es, long long V, long long E, const set<pair<ll,ll>> &disconnected, UnionFindVerSize<ll> uf, ll target_u, ll target_v) {
TODO
sort(es.begin()+start, es.end(), comp);
for (long long i=start; i<E; i++) {
edge e = es[i];
if (disconnected.count({e.u, e.v})) continue;
if (!uf.is_same_group(e.u, e.v)) {
uf.unite(e.u, e.v);
}
if (e.u==target_u && e.v==target_v) break;
}
return {uf, -1};
}
void solve() {
random_device rnd;
mt19937 mt(rnd());
ll N = 400, M = 1995;
vector<ll> X(N), Y(N);
for(ll i=0; i<N; i++) {
cin >> X[i] >> Y[i];
}
ll WORLD_NUM = 5;
vector<vector<edge>> world(WORLD_NUM, vector<edge>(M));
for(ll i=0; i<M; i++) {
ll u, v;
cin >> u >> v;
ll d = distance(X[u], Y[u], X[v], Y[v]);
uniform_int_distribution<> myrand(d, 3*d);
for(ll w=0; w<WORLD_NUM; w++) {
edge e = {u, v, (ll)myrand(mt)};
world[w][i] = e;
}
}
set<pair<ll,ll>> disconnected;
UnionFindVerSize uf = UnionFindVerSize<ll>(N);
for(ll i=0; i<M; i++) {
ll l; cin >> l;
ll u = world[0][i].u;
ll v = world[0][i].v;
ll vote = 0;
for(ll w=0; w<WORLD_NUM; w++) {
world[w][i] = {u, v, l};
auto [kruskal_uf, kruskal_cost] = kruskal3(i, world[w], N, M, disconnected, uf, u, v);
if (kruskal_uf.graph[u].count(v)) {
vote++;
}
}
if (vote > WORLD_NUM/2) {
cout << "1" << endl << flush;
uf.unite(u, v);
}
else {
cout << "0" << endl << flush;
disconnected.insert({u, v});
}
}
}
元ツイートの方は並行世界を19個作れているのでまだ改良の余地はありますが、キリがないのでこのくらいにしようと思います。
