Union-Findデータ構造の基礎アルゴリズム
Union-Findデータ構造
基本的なテンプレート実装から始めましょう。
この種の問題は比較的単純で、主要な関数を正しく実装すれば解決できます。
int findRoot(int node){return (node == parent[node] ? node : parent[node] = findRoot(parent[node]));}
豆知識：多くの人はこの関数をFindやfindと命名しますが、私の場合はなぜfindRootという名前を使用しているので ...
7月21日 01:43 投稿
ICPC南京2025 区域赛 CFGIJ 解法まとめ
C. キャンディの均等配分
問題の本質は「奇数個のキャンディは必ず偶数を生むため分割不可」という観察にある。したがって入力が偶数であれば単純に半分に分ければよく、奇数なら即座に不可と判定する。
void judge() {
long long N;
std::cin >> N;
if (N & 1) {
std::cout
7月18日 21:14 投稿
アカウントのメールアドレスを統合するUnion-Findアプローチ
問題概要
複数のアカウント情報が「名前, メール1, メール2, …」という形式で与えられる。同一人物のアカウントは少なくとも1つのメールアドレスが共通しているため、それらを1つにまとめて返却せよ。
Union-Findを用いた解法
「共通のメールアドレスを持つアカウントは同一人物」という条件は、「同一要素を含む集合をすべて結合」というUnion-Findの典型的な利用シーン ...
7月16日 21:36 投稿
Union-Findアルゴリズムによるグラフの連結成分とその応用
無向グラフにおける連結成分の数え上げ
この問題では、与えられた無向グラフに含まれる連結成分の総数を求める必要があります。Union-Find（素集合データ構造）を用いることで効率的に解決できます。各ノードを初期状態で自身を親とする木として扱い、エッジを通じてノードを結合していきます。パス圧縮により探索効率を高め、最終的なルートノードの数が答えとなります。
...
7月16日 16:06 投稿
並查集の高度な応用：敵対関係と種類管理
並查集（Union-Find）は集合の結合と検索を効率的に行うデータ構造である。基本操作は結合（Union）と検索（Find）で、経路圧縮を適用することで平均計算量をO(α(n))に低下させる。結合時のランクを考慮した最適化（ランク統合）も有効である。
削除操作を扱う際は、逆順処理が有効である。初期状態で全ての削除を適用した後の連結成分数を計算し、逆順に各削除を復元しな ...
7月12日 19:05 投稿
SMU Summer 2023 Contest Round 4のアルゴリズム解説
A. Telephone Number
この問題では、与えられた文字列から標準的な11桁の電話番号を作成できるかを判定します。電話番号の最初の数字は'8'でなければならないため、最初の'8'が現れる位置が重要です。文字列の長さを n とすると、最初の'8'のインデックスが n - 11 以下であれば、その後ろに残りの10桁を配置するための十分な文字数が存在します。
#include <iostream&g ...
6月24日 00:42 投稿
主要アルゴリズムとデータ構造の実践: セグメントツリー、ハンガリー法、素因数分解Union-Find
競技プログラミング問題解決のヒント
競技プログラミングでは、時間計算量の制約をクリアするために効率的なアルゴリズムやデータ構造の理解が不可欠です。以下に、いくつかの実践的なアプローチとコード例を紹介します。
繰り返しの多いクエリに対する前計算（累積和）
多数のクエリに対して同じ計算を繰り返す場合、事前に結果を前計算しておくことで、各クエリの処理時 ...
6月21日 22:28 投稿
グラフアルゴリズムの実装と応用
グラフの冗長接続検出
無向グラフにおいて、ツリー構造を維持しながら冗長な接続を特定する方法について説明します。
Union-Findによる冗長接続の検出
#include <iostream>
#include <vector>
using namespace std;
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int n) : parent(n + 1) {
for (int i = 0; i &l ...
6月19日 19:16 投稿
農場ネットワークの最小全域木問題
問題概要
ジョン農場主が町長に選出されました！彼の選挙公約の一つは、町全体にインターネットを導入し、すべての農場を接続することです。もちろん、彼はあなたの助けが必要です。
ジョンはすでに自身の農場に高速ネットワーク回線を設置済みであり、これを他の農場と共有したいと考えています。費用を最小限に抑えるため、すべての農場を接続する最短の光ファイバーを ...
6月14日 18:40 投稿
競技プログラミング問題精選: 考察技法と実装(ICPC/APIO/NOI対策)
P6880 JOI 2020 Final オリンピックバス
有向グラフが与えられる。辺を通るコスト \(C_i\)、1本の辺を反転させるコストを \(D_i\) とする。頂点 \(1\) から \(n\) へ、さらに \(n\) から \(1\) へ移動するとき、辺の反転を高々1回まで許したときの最小コスト和を求めよ。
全ての辺に対して反転を試すのは非効率なので、影響を解析する。\(f(s,t)\) を元のグラフでの \(s\) ...
6月3日 16:05 投稿