天才にしか解けない激ムズアルゴリズムパズルがこちらｗｗ

1 ：以下、？ちゃんねるからVIPがお送りします：2022/02/13(日) 23:14:31.204 ID:J/Mu/tsG0.net

n枚のカードがあり、i番目のカードの表には整数a_i、裏には整数b_iが書いてある

n枚のカードをいくつか裏返して並べて、最大何種類の整数を表に出来るか？

94 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:02:47.313 ID:dyyPYDEaa.net

>>92
3番目ってbそのものと変わらないものを用意しろってこと？

95 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:02:58.643 ID:zAMccW1/M.net

>>93
眠いぃぃぃ、正解もお願いします！

96 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:03:45.232 ID:dyyPYDEaa.net

2番目は
aの辞書を作っているイメージだよね
iがaの中に何個ありますか？という

97 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:04:03.374 ID:dyyPYDEaa.net

>>95
じゃあ正解はります

98 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:04:32.291 ID:zAMccW1/M.net

>>94
部分集合も含めるとbの順番を入れ替えたもの。

99 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:04:50.392 ID:dyyPYDEaa.net

まずa_iとb_iを頂点として、それらを辺で結ぶグラフを考えます
例えば

100 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:05:15.645 ID:zAMccW1/M.net

>>96
そそ、超プリミティブなハッシュ的な

101 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:06:44.742 ID:dyyPYDEaa.net

[1,2]、[2,3]、[3,1]、[3,4]、[5,6]なら
こんな感じのグラフ
https://o.5ch.net/1whwb.png

102 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:08:26.418 ID:dyyPYDEaa.net

>>101
このグラフのそれぞれの連結成分について、
もし木(サイクルを持たないグラフ)であるなら「頂点数-1」
木でないなら「頂点数」
をカウントしてそれらを足せば答えになります

103 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:09:40.967 ID:dyyPYDEaa.net

>>101
のケースなら
左のグラフは木じゃないグラフなので
頂点数-1=4-1=3

右のグラフは木なので
頂点数=2

これらを足して3+2=5
がマックスになる

104 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:10:55.285 ID:zAMccW1/M.net

>>102
ありがとう！
天才っすな
キモの1つは、裏表区別しなくていいってところか

105 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:10:57.946 ID:dyyPYDEaa.net

アルゴリズムとしてはUnion find等を使い、グラフの連結成分を調べればおkです

106 ：以下、？ちゃんねるからVIPがお送りします：2022/02/14(月) 02:12:16.889 ID:dyyPYDEaa.net

>>104
おっしゃる通り

今回の問題は
このグラフにおいてそれぞれの辺の両端のどちらか片方を光らせることが出来る電飾が付いていると思って、最大何個電気を付けられるのか
という問題と同じになります