過去にやった問題が役に立ったので嬉しかったです。
問題リンク
https://atcoder.jp/contests/arc111/tasks/arc111_b
問題概要
$N$ 枚のカードがあり、各カードの両面には $a_i,\ b_i$ の色がついています。どちらかを表にするとき、表側の色の種類数の最大値はいくつになるでしょうか。
制約
- $1\le N\le 2\times 10^5$
- $1\le a_i,\ b_i\le 4\times 10^5$
考察
入力例 1 でどういう選び方をすればいいか確認してみましょう。入力例 1 のカードを順番に見ていきます。
4
1 2
1 3
4 2
2 3
1 枚目のカード
1 と 2 どちらでもいいです。1 色を達成できます。2 枚目のカード
最初に 1 を選んだなら 3、2 を選んだならどちらでもいいです。3 色の内 2 色を達成できます。3 枚目のカード
2 枚目と同様に、4 色のうち 3 色を達成できます。4 枚目のカード
2 と 3 はどちらも前までに現れていますが、順番に 1, 3, 4 または 2, 1, 4 を選ぶことで 2 または 3 を選ぶことが出来ます。
ここまでの観察から、次のようなことが言えそうです。以下、2 枚目のカードを選んだときの 1, 2, 3 のように、$k$ 色のうち $k-1$ 色を達成できるような色の集まりを便宜上「色の繋がり」と称します。また、4 枚目のカードを選んだときの 1, 2, 3, 4 のように、$k$ 色のうち $k$ 色すべてを達成できるような色の集まりを便宜上「固定された色の集まり」と称します。
- 次の色が別の色の繋がりになっていて、どちらも固定された色の繋がりでないとき
両者を繋げることができます。全色のうち $1$ 色以外を達成できるようであるような状態は保てるので、達成できる色数は $1$ 増えます。 - 次の色が同じ色の繋がりに属しているが、固定された色の繋がりでないとき
両者を繋げることができますが、新たに出来る色の繋がりは固定されます。達成できる色数は $1$ 増えます。 - 次の色のどちらも固定された色の繋がり、または同じ固定された色の繋がりであるとき
次のカードでは達成できる色数は増やすことはできません。
また、入力例 1 にはありませんが、$a_i=b_i$ である場合もあります。そのときは次のようにできます。
- その色が固定されていない色の繋がりに属している場合
その色の繋がりを固定できます。達成できる色数は $1$ 増えます。 - その色が固定された色の繋がりに属している場合
次のカードでは達成できる色数は増やすことはできません。
以上のように色数を数えることができます。これは Union Find などで達成できそうです。Union Find で実装する場合、その色の繋がり (連結集合ですね) が固定されているかどうかを根に bool で持てば良さそうですが、これは実は超頂点を作ることで対処できます。エレガントです。
解法
Union Find で管理します。色は $1,\ 2,\ \dots,\ 400000$ であり、超頂点を $0$ とします。
カードの色が違う場合は以下のように辺を追加します。
両者が同じ連結集合でない場合
両者を繋ぎ、使える色数を $1$ 増やします。両者が同じ連結集合である場合
- 超頂点と同じ連結集合でない場合
その連結集合を超頂点に繋ぎ、使える色数を $1$ 増やします。 - 超頂点と同じ連結集合である場合
使える色数は増やせません。
- 超頂点と同じ連結集合でない場合
カードの色が同じ場合は以下のように辺を追加します。
- その色が超頂点と同じ連結集合でない場合
その色の連結成分と超頂点を繋ぎ、使える色数を $1$ 増やします。 - その色が超頂点と同じ連結集合である場合
使える色数は増やせません。
以上のように簡潔に解答することが出来ます。
実装
実装を展開する
public void Solve()
{
var n = sr.ReadInt();
var (a, b) = sr.ReadValueArray<int, int>(n);
var uf = new UnionFind(400001);
int ans = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == b[i])
{
if (!uf.IsSame(a[i], 0))
{
ans++;
uf.Unite(a[i], 0);
}
}
else if (!uf.IsSame(a[i], b[i]))
{
ans++;
uf.Unite(a[i], b[i]);
}
else if (!uf.IsSame(a[i], 0))
{
ans++;
uf.Unite(a[i], 0);
}
}
Console.WriteLine(ans);
}
ACコード: https://atcoder.jp/contests/arc111/submissions/19281760
感想
この問題は既出だったようです。Chokudai SpeedRun 002 - K 種類数β です。
Union Find に超頂点を持たせるテクを年明け前のこどふぉで学びました。解説にはしていませんが、Good Bye 2020 - F Euclid’s nightmare です。簡単に言うと、$\mathbb{Z}/2\mathbb{Z}$ 上で $m$ 次元ベクトルの基底を求める (ただし、そのベクトルは要素のうち $1,\ 2$ 個のみが $1$ であるようなベクトル) 問題です。この問題も似たような方法で Union Find で処理でき、また超頂点を持つことで実装を簡単にすることが出来る問題でした。本番では解けませんでしたが Upsolve をして強く記憶に残っていました。
この問題の反省が早速生きました (というかほとんど同じ発想だったので一瞬でした)。序盤の簡単な問題ですが満足な速度での早解きができたため嬉しかったです。
精進はすぐには実力には現れないと言いますが、ここまですぐに現れると楽しいですね。