■ このスレッドは過去ログ倉庫に格納されています
天才にしか解けない激ムズアルゴリズムパズルがこちらww
- 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
おっしゃる通り
今回の問題は
このグラフにおいてそれぞれの辺の両端のどちらか片方を光らせることが出来る電飾が付いていると思って、最大何個電気を付けられるのか
という問題と同じになります
総レス数 106
27 KB
掲示板に戻る
全部
前100
次100
最新50
read.cgi ver.24052200