■ このスレッドは過去ログ倉庫に格納されています
天才にしか解けない激ムズアルゴリズムパズルがこちらww
- 1 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:14:31.204 ID:J/Mu/tsG0.net
- n枚のカードがあり、i番目のカードの表には整数a_i、裏には整数b_iが書いてある
n枚のカードをいくつか裏返して並べて、最大何種類の整数を表に出来るか?
- 3 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:15:25.004 ID:Gs58ueJy0.net
- 天才に聞く
- 4 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:15:44.075 ID:J/Mu/tsG0.net
- この最大種類数を出力する最適なアルゴリズムはなんでしょう??
- 5 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:15:55.522 ID:J/Mu/tsG0.net
- >>3
なーるほど
- 6 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:15:56.736 ID:O7wHgqbN0.net
- 聞き齧った問題を理解はおろか正確に伝えることすらできないの本当に見てて悲しいな
- 7 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:16:31.550 ID:J/Mu/tsG0.net
- >>6
??
どこが分からないの?
単に君が読み解けていないだけでしょ
- 8 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:17:35.925 ID:J/Mu/tsG0.net
- それにこれは参考にした元ネタはあるけど自作問題だぞ
- 9 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:18:18.806 ID:0VIkHXOD0.net
- 表に出来るって何?
- 10 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:18:19.817 ID:7xE3o7RAd.net
- 2桁の整数とか縛りは?
- 11 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:18:56.804 ID:TwCevLJH0.net
- 全部表にしたらn枚じゃね
- 12 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:19:06.810 ID:J/Mu/tsG0.net
- >>9
表になったカードに書いてある整数のことです
- 13 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:19:21.001 ID:J/Mu/tsG0.net
- >>10
ないよ
- 14 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:19:23.663 ID:7/+aDrNc0.net
- 表にできるか?って何
- 15 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:19:43.205 ID:JFVRXRzEM.net
- なんで表向きに置くの禁止されてるの?
- 16 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:19:47.940 ID:J/Mu/tsG0.net
- >>11
いやそれだといくつか整数が被るかもしれない
そうすると種類最大化にならないよ
- 17 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:20:17.707 ID:ZKCbHdF1M.net
- 何をもって最適だと言いたいんだろう
時間計算量?空間計算量?
- 18 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:21:12.057 ID:7/+aDrNc0.net
- じゃんけんというゲームにはグーとチョキとパーがある
n回勝負をして最大何回勝てるか?
みたいな問題文にみえるんだが?
- 19 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:21:30.971 ID:J/Mu/tsG0.net
- >>14
すまんちゃんと書く
n枚のカードがあり、i番目のカードの表には整数a_i、裏には整数b_iが書いてある
n枚のカードをいくつか裏返して並べて、書かれた整数は最大何種類表示できるか?
- 20 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:21:49.169 ID:J/Mu/tsG0.net
- >>15
??
禁止されてないぞ
- 21 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:22:52.650 ID:J/Mu/tsG0.net
- >>17
すまん時間最適化の方です
- 22 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:23:19.767 ID:7/+aDrNc0.net
- >>19
裏返して並べるなら表の数字何も関係ないじゃん
ちゃんと書けてないぞ
- 23 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:23:35.019 ID:ZKCbHdF1M.net
- 匿名掲示板なんかに自作の問題貼って、かしこぶって悦に浸るのって本当に惨めだな
- 24 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:24:13.596 ID:ZKCbHdF1M.net
- 書くならちゃんと書けよ
ちゃんと書けないから匿名掲示板でしか相手にされないんだろ
ばーか
- 25 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:24:16.044 ID:C/523OKL0.net
- 問題文が日本語じゃない
- 26 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:24:25.574 ID:13yoVlI90.net
- 日本語の勉強を先にした方が良いよ
- 27 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:24:29.892 ID:7xE3o7RAd.net
- これ問題が分からないのではなく問題文がわかんないやつだ
- 28 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:24:54.324 ID:J/Mu/tsG0.net
- >>18
例えば2枚あったとして
a_1とa_2がひとしくて、
b_2はそれらと異なる場合、
2番目のカードを裏返して
a_1,b_2と表示させた方が種類は多くなる
- 29 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:25:11.125 ID:/NZ6AIPp0.net
- いくつか裏返す作業を自由にしていって、表に見える数の種類が最大になるときの種類の数を答えるってこと?
- 30 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:25:35.827 ID:J/Mu/tsG0.net
- >>29
そういうこと
- 31 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:26:36.499 ID:qWNZ+4lQd.net
- 40〜50種類だと思うわ
間違ってるというなら根拠を示してみろガキが
- 32 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:26:48.857 ID:7/+aDrNc0.net
- 何回も表にしたり裏にしたりしてもいいのか?
お前の脳内の前提が俺らにはわかんねーんだわ才能ないよ君
- 33 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:27:10.966 ID:J/Mu/tsG0.net
- >>31
>>28の時点で反例
この場合は2種類が最大
- 34 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:27:55.611 ID:J/Mu/tsG0.net
- >>32
好きに裏返してよい
そんな変な書き方してないでしょ
- 35 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:28:00.995 ID:qWNZ+4lQd.net
- >>33
は?何ほざいてんだ
- 36 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:28:27.254 ID:J/Mu/tsG0.net
- >>35
いや具体的に反論しなよ
- 37 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:28:54.854 ID:/NZ6AIPp0.net
- ai,biにある値が与えられたときにどう答えを求めるかのアルゴリズムを答えればいいんか?
- 38 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:29:02.900 ID:sydA8xkv0.net
- >>33
2枚だから2が最大ってこと?
- 39 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:29:09.957 ID:36ZqEq7f0.net
- 競プロって言えばいいのに
- 40 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:29:32.593 ID:J/Mu/tsG0.net
- >>37
そういうことです
- 41 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:30:23.489 ID:qWNZ+4lQd.net
- >>36
ボールはお前にある
俺は40〜50種類だと言った
違うなら根拠を示せ
- 42 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:30:37.778 ID:J/Mu/tsG0.net
- >>38
まあそうだね
あとa_1とb_2が異なるからってのもある
a_1=a_2=b_1=b_2なら最大1種類
- 43 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:30:43.437 ID:CvMqyJD8M.net
- a_m = a_n, b_p=b_q, a_x = b_y等の場合を考慮してアルゴリズムを作れってこと?
- 44 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:31:09.467 ID:J/Mu/tsG0.net
- >>41
>>28で反例を示したんだけど
- 45 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:31:31.024 ID:J/Mu/tsG0.net
- >>43
まさしくそういうこと
- 46 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:32:39.091 ID:36ZqEq7f0.net
- 多分どっちかの数字でソートして貪欲法とかそんなんじゃないの
- 47 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:33:15.465 ID:p+N3SxCt0.net
- 困難は分割せよ定期
- 48 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:33:55.008 ID:7/+aDrNc0.net
- なんとなくやらせたい事はわかった
表同士を数が被らないように並べた後、被ってる奴らを裏にするような簡単な方法だと
表示の被ってない種類の最大数は伸ばせない(裏も被ってたりすると意味がない)から
もっと難しい方法で一番種類を稼げる方法を示せってことでいいのか?
- 49 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:34:15.495 ID:qWNZ+4lQd.net
- >>44
答えになってない
もう俺の勝ちだな
このスレいる?
- 50 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:34:25.545 ID:/NZ6AIPp0.net
- i番目のカードは表が裏の二択→ビット全探索で表裏全ての場合について数字が何種類あるか調べる→調べて記録した数の最大値が答え
これだめ?
- 51 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:35:43.793 ID:J/Mu/tsG0.net
- >>48
前半に書いてあるそのやり方だと最大種類になるとは限らないよ
- 52 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:35:59.632 ID:J/Mu/tsG0.net
- >>49
バカは黙れよ
- 53 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:36:50.438 ID:qWNZ+4lQd.net
- >>52
お前はそうやって逃げるのか
このスレいる?
- 54 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:37:16.838 ID:J/Mu/tsG0.net
- >>50
ビット全探索だと非常に遅くなりますね
実はオーダーnで解けます
- 55 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:37:19.062 ID:p+N3SxCt0.net
- な?こんなところでスレ立てること自体間違いなんだよ
専門板いってこい
- 56 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:37:26.276 ID:7/+aDrNc0.net
- >>51
本当に日本語話者か?
大丈夫か?
- 57 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:38:25.347 ID:J/Mu/tsG0.net
- >>56
いやだから
「表同士を数が被らないように並べた後、被ってる奴らを裏にする」
このやり方だと最大になるとは限らないってこと
- 58 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:39:34.380 ID:7/+aDrNc0.net
- あ、だめだこいつ
- 59 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:40:26.235 ID:J/Mu/tsG0.net
- >>48
ああすまん
最大になるとは限らないことはわかった上でのレスか
そういうことです
あとなおかつ手順の少ない方法を求めよってことね
- 60 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:40:59.586 ID:/NZ6AIPp0.net
- >>54
ですよね
- 61 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:44:08.833 ID:CvMqyJD8M.net
- 以下だと簡単すぎるけど、こういうのを効率化しろってこと?
1.各整数を配列a[], b[]に格納
2.a_x = b_yとなる全てのb[y]をb[y]=NG等として除去
2.b_p=b_qとなる全てのb[q]をb[q]=NG等として除去
3.a_m = a_nとなる全てのa[n]をa[n]=SWAP等としてフラグ付け
4.答え[SWAPが付いていないa_iの数]+[min(NGが付いていないb_iの数), SWAPが付いているa_iの数]
- 62 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:46:45.264 ID:J/Mu/tsG0.net
- >>61
min(NGが付いていないb_iの数)
ってのはiを動かしたときのminだよね?
これだと最大とは限らないよ
- 63 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:50:12.375 ID:CvMqyJD8M.net
- >>62
ごめん、書き間違い
min(NGが付いていないb_iの数, SWAPが付いているa_iの数) で、
[NGが付いていないb_iの総数]と、[SWAPが付いているa_iの総数]の小さい方
- 64 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:52:45.674 ID:J/Mu/tsG0.net
- >>63
あとごめん
a_x = b_yとなる全てのb[y]をb[y]=NG等として除去
とありますが、これは「あるxがあってa_x=b_yならb_yはNG」ってこと?
- 65 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:55:23.976 ID:CvMqyJD8M.net
- >>64
YES
- 66 :以下、?ちゃんねるからVIPがお送りします:2022/02/13(日) 23:59:23.598 ID:J/Mu/tsG0.net
- >>65
例えば
[a_i, b_i]として
カードが
[1,2]、[2,3]、[1,3]
の場合を考えましょう
そうするとb_iはすべてNGだよね?なのでNGがついてないのはゼロ
そしてa_1とa_3はSWAPになるからSWAP無しは1種類だけ
となると結局求める数1になってしまうけど
[1,3]を裏返して
[1,2]、[2,3]、[3,1]
とすれば3種類表示できる
- 67 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:00:05.814 ID:0DksHY3S0.net
- なので最大とは限らないですね
- 68 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:03:55.284 ID:zAMccW1/M.net
- >>66
1.a[]={1, 2, 1}, b[]={2, 3, 3}
2.b[]={NG, 3, 3}
3.b[]={NG, 3, NG}
4.a[]={1, 2, SWAP}
5.2+min(1, 1)=2+1=3
で、3種類
- 69 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:08:31.497 ID:dyyPYDEaa.net
- >>68
ああごめん 逐次でNG化していくのか
この場合だとオーダーn^2かかるので厳しいですね
- 70 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:14:19.022 ID:zAMccW1/M.net
- >>69
オーダーnとかわからんな
最後に正解を書いていってくれよな
- 71 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:26:51.941 ID:CNIAvGxi0.net
- 結局答え貼らずに0時でとんずらか
- 72 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:30:48.459 ID:qmcYKxe3r.net
- 話がすすんでるやつはちょっと噛み砕いて説明してくれよ
a-iとb-iって5番目だとすると何か確定するの?
- 73 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:36:34.586 ID:zAMccW1/M.net
- >>72
5番目のカードの表にa_5、裏にb_5という整数が書かれているだけで何かが確定するというわけではない
- 74 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:42:32.890 ID:dyyPYDEaa.net
- ごめん反例見つけてたわ
>>61
例えば
[3,2]、[2,3]、[2,4]、[4,3]、[1,5]
とかなら5になってしまうけど
実際には4種類が最大ですね
- 75 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:45:30.745 ID:dyyPYDEaa.net
- >>74
この場合なら最終的に
b={NG,NG,NG,NG,5}
a={3,SWAP,2,4,1}
になって
求める値は
4+min(1,1)=5になってしまう
- 76 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:47:44.660 ID:dyyPYDEaa.net
- もっと簡単に
[1,2],[2,3],[4,5]なんかも反例ですね
- 77 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:49:22.461 ID:zAMccW1/M.net
- >>74
1.a[]={3, 2, 2, 4, 1}, b[]={2, 3, 4, 3, 5}
2.b[]={NG, NG, NG, NG, 5}
3.b[]={NG, NG, NG, NG, 5}
4.a[]={3, 2, SWAP, 4, 1}
5.4+min(1, 1)=4+1=5
ans={3, 2, 5, 4, 1} で5種類が最大じゃね?
どのみち4項のオーダーもn^2なのでこの方針じゃどうしようもないくさい
解答はよ
- 78 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:49:31.754 ID:dyyPYDEaa.net
- >>76
失礼しましたこれは反例になってないわ
- 79 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:53:07.749 ID:dyyPYDEaa.net
- >>77
ちょっと吊るわ
こんどこそコードで確認した反例あるんだけど複雑になってしまった
- 80 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:53:36.370 ID:zAMccW1/M.net
- >>77
あー、カードの裏表の連動を忘れてた
めんどくせぇーwww
- 81 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:55:07.146 ID:dyyPYDEaa.net
- a b
6 19
8 20
16 8
3 20
9 13
10 11
8 15
20 11
18 17
8 14
15 16
20 1
5 2
7 11
14 7
4 11
14 15
20 5
15 1
12 1
が反例らしい
もっと簡単な反例を用意したいですが
- 82 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:57:09.931 ID:dyyPYDEaa.net
- ああいいんだ落ち着け
>>74でちゃんと反例だわ
- 83 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:57:39.577 ID:zAMccW1/M.net
- >>81
いや、[1,5]をひっくり返すと1が消えるので[3,2]、[2,3]、[2,4]、[4,3]、[1,5]が反例で合ってると思う
- 84 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:57:45.827 ID:dyyPYDEaa.net
- [1,5]で連動してるからどう頑張っても5種類表示は不可能
- 85 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:57:55.196 ID:Az+uvMVP0.net
- 日本語を先に勉強したほうが有意義
- 86 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 00:58:00.502 ID:dyyPYDEaa.net
- >>83
そうだね失礼しました
- 87 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:00:21.237 ID:zAMccW1/M.net
- ひっくり返すべきカードをオーダーnで見つけるという方針がそもそも間違いということか?
- 88 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:02:48.336 ID:dyyPYDEaa.net
- >>87
とりあえず「最大数」だけを出力すればいいのがポイントかも
- 89 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:20:16.105 ID:vEStmCbz0.net
- 整数毎にグループに振り分ける
グループ数-ぼっち数/2
- 90 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:23:15.675 ID:dyyPYDEaa.net
- >>89
グループ数がまるまる表示出来るとは限らないよ
例えば
[1,2] [2,3]
なんかが反例
{1,2,3}はグループだけど
上のばあい2種類しか表示できない
- 91 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:27:00.862 ID:OBL6jtkO0.net
- >>89
[1,3] [1,3] [1,4] [2,3]
だとグループ数4ぼっち数2だけど実際には4種類表示できる
- 92 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:54:02.690 ID:zAMccW1/M.net
- 少し改善。この方向???
0.面倒なので正の整数としても良い
1.最大の整数分の配列a[], b[]を用意。最大の正整数が65536ならa[65536]的なのを用意。a[]の初期値は0
2.a_iをa[a_i]=a[a_i]+1として格納
3.b_iをb[i]=b_iとして格納。複数ある場合は複数順番に格納
4.a[p]≠0の場合、a[b_p]=0ならa[b_p]=1とし、a[p]=a[p]-1とする。b[p]の要素数分だけ繰り返し
5.a[x]≠0の数を数える
例1:
a_i={1, 1, 1, 2}, b_i={3, 3 ,4 ,3}
2.a[]={3, 1, 0, 0,...}
3.b[]={(3, 3, 4), 3, 0, 0,...}
4.a[]={1, 1, 1 ,1}
ans=4
例2:
a_i={3, 2, 2, 4, 1, 3}, b_i={2, 3, 6, 3, 5, 3}
2.a[]={1, 2, 2, 1, 0, 0,...},
3.b[]={5, (3,6), (2, 3), 3, 0, 0,...}
4.a[]={0, 1, 2, 1, 1, 1,...},
ans=5
- 93 :以下、?ちゃんねるからVIPがお送りします:2022/02/14(月) 01:56:29.362 ID:dyyPYDEaa.net
- >>92
ありがとう
今からキチンと検証します
- 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
がマックスになる
総レス数 106
27 KB
新着レスの表示
掲示板に戻る
全部
前100
次100
最新50
read.cgi ver.24052200