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

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

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

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

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

以下だと簡単すぎるけど、こういうのを効率化しろってこと？

１．各整数を配列a[], b[]に格納
２．a_x = b_yとなる全てのb[y]をb[y]=NG等として除去
２．b_p=b_qとなる全てのb[q]をb[q]=NG等として除去
３．a_m = a_nとなる全てのa[n]をa[n]=SWAP等としてフラグ付け
４．答え[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
１．a[]={1, 2, 1}, b[]={2, 3, 3}
２．b[]={NG, 3, 3}
３．b[]={NG, 3, NG}
４．a[]={1, 2, SWAP}
５．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
１．a[]={3, 2, 2, 4, 1}, b[]={2, 3, 4, 3, 5}
２．b[]={NG, NG, NG, NG, 5}
３．b[]={NG, NG, NG, NG, 5}
４．a[]={3, 2, SWAP, 4, 1}
５．4+min(1, 1)=4+1=5

ans={3, 2, 5, 4, 1} で5種類が最大じゃね？

どのみち４項のオーダーも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
あー、カードの裏表の連動を忘れてた
めんどくせぇーｗｗｗ

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

少し改善。この方向？？？

０．面倒なので正の整数としても良い
１．最大の整数分の配列a[], b[]を用意。最大の正整数が65536ならa[65536]的なのを用意。a[]の初期値は0
２．a_iをa[a_i]=a[a_i]+1として格納
３．b_iをb[i]=b_iとして格納。複数ある場合は複数順番に格納
４．a[p]≠0の場合、a[b_p]=0ならa[b_p]=1とし、a[p]=a[p]-1とする。b[p]の要素数分だけ繰り返し
５．a[x]≠0の数を数える

例１：
a_i={1, 1, 1, 2}, b_i={3, 3 ,4 ,3}
２．a[]={3, 1, 0, 0,...}
３．b[]={(3, 3, 4), 3, 0, 0,...}
４．a[]={1, 1, 1 ,1}
ans=4

例２：
a_i={3, 2, 2, 4, 1, 3}, b_i={2, 3, 6, 3, 5, 3}
２．a[]={1, 2, 2, 1, 0, 0,...},
３．b[]={5, (3,6), (2, 3), 3, 0, 0,...}
４．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
がマックスになる

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
おっしゃる通り

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