ヨーロッパ選手権 2024 解説

欧州選手権 2024 - オンラインミラー

A. グローブ#

$20 \times 20$ のグリッドが与えられ、内部の整数点に半径 $r$ の円（ $r$ は三桁の小数）をできるだけ多く置くことができます。最大でいくつ置けるか。

いくつかの密铺問題の結論を見たことがあり、配置方法には特に理論がないように感じます。

おそらく、これはメモ化 + ヒューリスティック + 爆発的探索の問題のようです。明らかに、できるだけ近くに置くべきで、メモ化によって重複した探索を排除する必要があります。仲間が書いていないので、適当に話しているだけでは全く通用しないように思えます。

B. 魅力的な食事#

仲間が 1 問書いて去りました。

C. 年次アリの集会#

木が与えられ、各点にアリが 1 匹います。毎回、点 $u$ のすべてのアリを 1 つの辺に沿って $v$ に移動させることができ、 $u$ のアリの数が $v$ の数以下である必要があります。最終的にすべてのアリを 1 つの点に集めることができるかどうかを尋ねます。

明らかに、1 つの点を空けると、その木は断絶しますので、毎回 1 つの葉を縮めることしかできません。また、小さい点の方が縮む可能性が高く、小さい点が縮むことで大きい点が他のものに移動する機会を与えます。

したがって、おそらく小さなヒープを維持し、トポロジカルソートのようなものをシミュレートすれば良いでしょう。

F. デート#

$n$ 人が与えられ、各人には 1 つの集合があります。マッチングを定義するには、2 人の集合が交差するが、互いに包含しない必要があります。良いマッチングを見つけるか、存在しないことを報告します。

適当な方法を考えましたが、この集合のサイズの種類数は平方根の量級（600 種類）です。

まず、各集合サイズについて、完全に同じ集合が重複しているかどうかを確認し、重複を取り除きます（無秩序集合ハッシュを使用）。次に、2 人の集合が交差しているかどうかを確認します。つまり、数字が重複して出現しているかどうかを確認します。重複があれば交差があり、長さが同じで完全に同じではないため、それが答えになります。

したがって、現在 600 種類の長さがあり、各長さには一堆の互いに交差しない集合があります。

次に、長さを大から小に列挙し、集合関係を含む森を構築し、各木が最後にどのノードに覆われたかを維持します。

現在の長さの各集合について、集合から各数の最後に覆われたノードを取り出し、その覆われたノード集合についていくつかの状況があります：

森の 2 つの木に 2 つの点が存在する場合、答えの組を見つけました。現在の集合と 2 つの点のいずれか：点を見つけたことは交差があることを示し、異なる木にあることは現在の集合の数が他の中に必ず存在しないことを示します。また、長さの制限により、現在の集合は間のすべての集合を必ず含まないことがわかります。
森の同じ木に 2 つの点が存在する場合、包含関係により、これら 2 つは必ず祖先関係があります。現在の集合と最も深いものを選択します：点を見つけたことは交差があることを示し、最後に覆われた 2 つの点を見つけることは、この数が祖先集合にあり、子孫集合にはないことを示します。また、長さの制限により、現在の集合は間のすべての集合を必ず含まないことがわかります。
森の同じ木に 1 つの点が存在する場合、1 つの辺をつなぎ、親子関係を見つけます。

G. スクーター#

仲間は誰も書きたがりません。

おそらく、問題の意図に従って構築すれば良いでしょう。例えば -m mc cm mc c- -c cm m- -c cm m- のように。

I. 円盤#

接触または離れている可能性のある円が与えられ、すべての円の半径を調整することで、元の接触および離れている関係を変えず、すべての円の半径の和を小さくすることが可能かどうかを尋ねます。

おそらく観察すると、接触関係を維持する必要があるため、1 つの円を縮めると、必然的に別の円が大きくなり、両者が相殺されます。

次に、サンプルを観察すると、長さ 3 の鎖が与えられ、「小 - 大 - 小」のようにすることができ、半径の和を小さくすることができます。次に、複雑なグラフがどうなるかを考えます。例えば、環がある場合、偶環は可能ですが、奇環は不可能であり、自然に二部グラフを連想します。したがって、元のグラフの二部グラフに色を付けることは、減少と増加の 2 つの変化を相当し、連結成分の左右の点数が異なるかどうかを確認します。

J. アマンダ・ザ・アメーバ#

仲間は誰も書きたがりません。

目標のグリッド内の各点を列挙し、境界上の適切に配置されていない点を削除し、一歩ずつ進んでいく感じです。

コード#

C. 年次アリの集会#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn], cnt[maxn], visited[maxn];
vector<int> edge[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }

  priority_queue<pair<int,int>> pq;
  for (int i = 1; i <= n; i++) {
    cnt[i] = 1;
    if (deg[i] == 1) {
      visited[i] = true;
      pq.push({ -1, i });
    }
  }

  bool ok = true;
  while (!pq.empty() && ok) {
    auto cur = pq.top();
    pq.pop();

    int u = cur.second;
    assert(visited[u]);

//    printf("F %d\n", u);

    for (int v: edge[u]) {
      if (visited[v]) continue;

      if (cnt[u] <= cnt[v]) {
        deg[v]--;
        cnt[v] += cnt[u];
        cnt[u] = 0;
        if (deg[v] == 1) {
          visited[v] = true;
//          printf("PUSH %d -> %d\n", u,v);
          pq.push({ -cnt[v], v });
        }
      } else {
        ok = false;
        break;
      }
    }
  }

  puts(ok ? "YES" : "NO");

  return 0;
}

F. デート#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <random>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 200000 + 5;
const int maxm = 1000000 + 5;

int n, m;

unsigned int hsh[maxn], key[maxm];
int dep[maxn], fa[maxn], bel[maxm];

vector<int> bag[maxn];
vector<int> lens[maxm];

bool check(int x, int y) {
  set<int> mp1, mp2;
  for (int t: bag[x]) mp1.insert(t);
  for (int t: bag[y]) mp2.insert(t);
  int cond1 = false, cond2 = false, cond3 = false;
  for (int t: mp1) {
    if (mp2.count(t)) cond1 = true;
    else cond2 = true;
  }
  for (int t: mp2) {
    if (mp1.count(t)) cond1 = true;
    else cond3 = true;
  }
  return cond1 && cond2 && cond3;
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &m);

  mt19937 rnd((unsigned) time(nullptr));
  for (int i = 1; i <= m; i++) {
    key[i] = rnd();
  }

  for (int i = 1; i <= n; i++) {
    int c;
    scanf("%d", &c);
    for (int j = 1, x; j <= c; j++) {
      scanf("%d", &x);
      bag[i].push_back(x);
      hsh[i] ^= key[x];
    }
    sort(bag[i].begin(), bag[i].end());
    lens[c].push_back(i);
  }

  for (int l = 1; l <= m; l++) {
    if (lens[l].empty()) continue;

    // 同じものを削除
    {
      map<unsigned, int> mp;
      vector<int> uniqued;
      for (int id: lens[l]) {
        if (mp.count(hsh[id])) {
          continue;
        }
        mp[hsh[id]] = id;
        uniqued.push_back(id);
      }
      lens[l] = uniqued;
    }
    // 交差を確認
    {
      memset(bel, 0, sizeof bel);
      for (int id: lens[l]) {
        for (int x: bag[id]) {
          if (bel[x]) {
            puts("YES");
            printf("%d %d\n", bel[x], id);
            assert(check(bel[x], id));
            return 0;
          }
          bel[x] = id;
        }
      }
    }
  }

  vector<int> groups;
  for (int l = m; l >= 1; l--) {
    if (lens[l].empty()) continue;

    if (groups.empty()) {
      // 最大の長さ
      for (int id: lens[l]) {
        groups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
    } else {
      vector<int> ngroups;
      for (int id: lens[l]) {
        // bel[x]: xを覆う最後のバッグID
        // visited: bel[x]の集合
        // roots: bel[x]の根の集合
        set<int> visited, roots;
        for (int x: bag[id]) {
          if (!visited.count(bel[x])) {
            visited.insert(bel[x]);

            int last = bel[x];
            if (bel[x]) {
              int f = bel[x];
              while (f) {
                last = f;
                f = fa[f];
              }
            }
            roots.insert(last);
          }
        }
        
        if (roots.size() == 0 || (roots.size() == 1 && *roots.begin() == 0)) {
          // 森に新しい木を作成
          fa[id] = 0;
          dep[id] = 1;
        } else if (roots.size() >= 2) {
          // 2つの木の鎖と交差
          int root = 0;
          for (int x: roots) {
            if (x) {
              root = x;
              break;
            }
          }
          puts("YES");
          printf("%d %d\n", root, id);
          assert(check(root, id));
          return 0;
        } else {
          // 1つの木の鎖と交差
          if (visited.size() == 1) {
            // 木の親を接続
            int cur = *visited.begin();
            assert(cur != 0);
            fa[id] = cur;
            dep[id] = dep[cur] + 1;
          } else {
            // 1つの鎖の複数のバッグと交差
            // つまり、idは根の部分集合ですが、最も深いノードと交差します
            int tag = -1;
            for (int x: visited) {
              if (tag == -1 || dep[x] > dep[tag]) {
                tag = x;
              }
            }
            assert(tag != -1);
            puts("YES");
            printf("%d %d\n", tag, id);
            assert(check(tag, id));
            return 0;
          }
        }
      }
      
      for (int id: lens[l]) {
        ngroups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
      groups = ngroups;
    }
  }

  puts("NO");

  return 0;
}

I. 円盤#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn];

vector<int> edge[maxn];
int flag, cnt, visited[maxn], col[maxn];

struct Circle {
    int x, y, r;
} a[maxn];

void dfs(int u) {
  cnt += col[u] == 0 ? 1 : -1;
  for (int v: edge[u]) {
    if (visited[v]) {
      if (col[v] != !col[u]) {
        flag = false;
      }
      continue;
    }
    visited[v] = true;
    col[v] = !col[u];
    dfs(v);
  }
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      long long dis = 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y);
      if (dis == 1ll * (a[i].r + a[j].r) * (a[i].r + a[j].r)) {
        deg[i]++;
        deg[j]++;
        edge[i].push_back(j);
        edge[j].push_back(i);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  memset(visited, 0, sizeof visited);
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    col[i] = 1;
    
    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  puts("NO");

  return 0;
}