過半数なら自分以外全て単一の敵勢力と見做すことができるからこういうアルゴリズムが成り立つのか。多分使い所はないけど面白い。

自分と違う票同士を対消滅させるアルゴリズムですね シンプルながら賢くて好きです

@activitydestory

Ай бұрын

このコメントが一番助けになった

@bbbda179-ecac-cde9

Ай бұрын

分かりやすい

@rairaikun1

28 күн бұрын

Rolandアルゴリズム

アルゴリズムとその動きだけ見ると全然上手く行ってるようには思えないのに証明を見ると確かに上手くいくと認めざるを得ないのが不思議な感覚 証明まで見た後にもう一度アルゴリズムの動きを見ると何がしたかったのか分かりやすい それにしてもこの動画に限らず前提知識を極限まで削った上で簡潔にかつわかりやすく解説できるの本当に尊敬します

1:14 89006（はくれいれいむ） 1341398（いざよいさくや）

@USER-jb2er3xr1t

Ай бұрын

と、⑨

電車の席の動画で知りました。難易度とテンポのバランスが心地よいです。 今後も応援してます🎉

I just solved a problem on this technique 10min before you uploaded this video, would have saved me some time. Nice video.

今回はきちんと自力でアルゴリズム思いついて嬉しい

@malc3497

Ай бұрын

すげえな

数学と競技プログラミングのチャンネルなのにちゃんと時事ネタを入れてくるとは、さすがです。しかもメモリーの制約とか実態と合っていて最高です。

thanks so much

こんなシンプルな処理でチェックできるなんて…… 鳩の巣原理みたいな感じなんだろうか

『cは「最多得票の人がいままでの半数からどれくらい多いか」を示している』という見方もできますかね？

@evimalab

Ай бұрын

もう少し複雑で、cは「新参に甘い」です。 例えば 1 1 1 1 1 2 2 2 2 2 3 と投票されると m=3, c=1 となりますが、3 は半数に全く届いていません。

@Chottoshitami

Ай бұрын

@@evimalab 確かにそうですね！ありがとうございます！

乱択だなあ〜（一位が過半数取ってるなら適当にとって一位を引く確率が少なくとも1/2あるので、10万回ランダムに引いたときに一位を一度も引かない確率が高々1/2^10万 はまあ無視できる） と考えてたらしっかり潰されててかなC 【追記】 （なぜか返信がうまく表示されないので追記するのですが） 10万票ランダムに引いた後にそれで出てきた最大10 万人ぞれぞれが過半数を超えるかは愚直に数えればよいです これなら配列サイズが10万(定数)で計算時間は Θ(N) (線形) を達成します

@user-qg4xz9zf2v

Ай бұрын

引いたものの中に一位のものが含まれていてもそれが一位かどうか判別できるんですかね...？ 例えばAという候補に51%の票が入ってBに49%票が入っている時(他は0票)はその手法での失敗率は無視できない値になりそう

@smuuukn

Ай бұрын

​​@@user-qg4xz9zf2v 10万個ランダムに引いた時の候補者は高々10万種類なので、その10万種類の候補者の票数を普通にメモリで持って愚直に数えて過半数を超えるやつがいるか見れば良いです （10万の中に一位が含まれてる確率が非常に高いため） これなら計算量は変わらずO(N)ですが、配列サイズがNに依らずに10万固定で計算ができます

@JD-is8yg

29 күн бұрын

@@user-qg4xz9zf2v 過半数がいない時が辛そうですね 1億票がAさん5000万票・Bさん5000万票で割れていたとき、n票を開けて「過半数はいない」と正しく評価できる確率は comb(n, n/2) / 2^n で、10万票だと0.2%しか正解できません

これって過半数がいなかった場合、cを減算する量を少し減らせば過半数より小さなある特定の割合を獲得した人がいるかどうか判別できるんでしょうか だとすれば二分探索すれば最多得票者を求められそうに見えます（嘘？）

@evimalab

Ай бұрын

減算量が大きくなると最初の票の比重が大きくなりすぎて狂いますが、偶然正しい m が返ることもあるはずで、二分探索に必要な単調性がなさそうです。

@user-eh3oi5rh7g

Ай бұрын

@@evimalab ありがとうございます、そううまくはいきませんね……

魔理沙の「じゃじゃん」ちょっと珍しくてかわいい(ゆっくり解説を見過ぎている)

初手で分割統治法がいいのではと思ったがどうなるんだろうか？ 要素数が1 → m=n,c=1 要素数が2以上なら2つに分割して得られた解(m1,c1)と(m2,c2)を 　　if(m1==m2) then m=m1,c=c1+c2 　　elseif(c1>c2) then m=m1,c=c1 　　else m=m2,c=c2 でマージした(m,n)を返す。結果は同じと言えるか？

@evimalab

27 күн бұрын

結果は同じではなさそう（c が表すものがかなり異なります）ですが過半数要素がある場合はそれが m になりそうです。 ただし、定数メモリで実装するのは困難だと思います。 （入力を書き換えてしまえば追加の領域はほとんど不要そうですが、定数メモリといえるかは怪しそうです。）

@gochuui1

27 күн бұрын

@@evimalab そうですね。Ο(logn)のメモリは必要でしょう あと、奇数番地が過半数、偶数番地ザコで死にますね mを投票先数のbool配列にしたΟ(mlogn)はないと厳しいかもですね

投票方式がハンターハンターで草

0:10山本...

票をソートして尺取りもどきのO(VlogV)？しか思いつかなかった

あれ、これって、「候補者1の票数だけを数える」→「候補者2の票数だけを数える」「暫定チャンピオン(1)と候補者2の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→「候補者3の票数だけを数える」「暫定チャンピオン(1か2)と候補者3の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→…でも定数メモリ解法にはなりますか？つまらなくて冗長なものではありますが

@evimalab

29 күн бұрын

定数メモリですが、候補者数は定数でないので線形時間にはなりません。

@user-yn1mu2eb8t

29 күн бұрын

⁠@@evimalabああそうか！線形時間も出題の条件でしたね…ありがとうございます😊😊

過去一、一発で理解できんかったわ……

2:37 ここでなぜm=8となるのでしょうか?elif m=vのvは9だと思うのですが…

@user-yz3fz5cn1t

28 күн бұрын

3:26 あとここで表をもう一周して数えるのでは定数メモリを使った意味がないと思いますが…

@evimalab

28 күн бұрын

> 2:37 ここでなぜm=8となるのでしょうか? すみません、間違えました。「mが9じゃないから」です。 > 3:26 あとここで表をもう一周して数えるのでは定数メモリを使った意味がないと思いますが… 2周目に必要なメモリ量は定数（m の値とカウンター、数値2個）なので全体でも定数メモリのままです。

@user-yz3fz5cn1t

28 күн бұрын

@evimalab なるほど、ありがとうございます！

まず、A100を用意します（）

自分と違う種族と交配すると死ぬ生命体同士のお祭りか そういうとなんか実際にイかせそうな気が

数学って便利だな(浅い意見)

Twitter見たら鶴崎さん（QuizKnock）やキム、すんさん（積分サークル）も良く見ていると聞いて。 僕は内容はほぼ分からないですが、惹かれる動画ですよねぇ。 2~3ヶ月くらい前に知ったという古参アピールをしておきます。

落語で、味噌汁をちゃんと混ぜたら大体味は均等になるよね、 的な話があって面白かった。

1:29 そもそも入力読み込みする時点でメモリをvに依存させない事は不可能では…?

@evimalab

Ай бұрын

入力ストリームから少しずつ読み込めばメモリ量は定数で済みます（例えば C 言語の fread が使えます。なお番号がワード長に収まることは仮定してしまいます）。

@HelloingBoi-pk4io

Ай бұрын

@@evimalab なるほど、ご教示ありがとうございます。

テーマは面白かったけど説明があっさりしすぎてほんとんど理解出来なかった、数学は好きなんだけどな...

このアルゴリズム偶数番目にのみ最多得票の候補者，奇数番目に常にそれ以外が来たら最多得票の人の番号mに入らなくない？（最初のデータは１番目とする）

@evimalab

Ай бұрын

最多得票の人を求めるアルゴリズムではありません。 1 9 2 9 3 9 4 9 5 9 と投票された場合、m=5, c=0 で終わり、過半数なしと判定されます。

@YN-zx8qd

Ай бұрын

@@evimalab 調べてみたら「過」半数が入力中に存在する場合のみ動作するアルゴリズムなのね 勉強になりました

@evimalab

Ай бұрын

過半数が存在しない場合も、動画で述べた通り入力を2周すればそのことを検出できます。 （その場合も線形時間です。なお 0:56 で 3/6 は過半数でないという例を出してはいます。）

過半数二つってありえないのでは..? あと2:12のm=vとかm==vとかのvは別の変数では? あと証明のとこ詳しい解説が欲しいです

@evimalab

Ай бұрын

はい。（どの部分に対しておっしゃっていますか？この動画は全体的に過半数得票者が一人以下であることを前提としています。） vは「いま見ている票」を表す変数です。（別とはなんでしょうか？この動画のどの部分が誤っていますか？） 今回の証明に「行間」はほぼなく、さらに詳しく解説するのはなかなか難しいと思います。 英語になってしまいますが、en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm#Correctness に文章での証明があります（この動画の V が n となっています）。

@user-rn4kt1bl1w

Ай бұрын

@@evimalab 最初の疑問については自己解決しました アルゴリズムの解説のとこで右上でv=9となっています 3:15なぜ「mが過半数だろう」という推測になるのですか？ 3:45mの票c枚は必ず取れますか？ このチャンネルの動画全体に言えますが行間は滅茶苦茶あります。まだこの問題に触れたことがなく理解の浅い視聴者の気持ちを投稿者が分かっていないのか、そもそも投稿者も理解していなくてただ英文を略しているだけなのかは知りませんが...

@evimalab

Ай бұрын

右上は V=9 です。 > 3:15なぜ「mが過半数だろう」という推測になるのですか？ 2:13 の「mがその時点での勝者の候補で、」から十分こう推測できるはずです。 > 3:45mの票c枚は必ず取れますか？ そのことを含む主張をこれから証明します。 > このチャンネルの動画全体に言えますが行間は滅茶苦茶あります。 ほかの動画に行間が少なくないものがあることは否定しませんが、この動画では少なく抑えました。 このことの証明は難しいですが、他のコメントをすべて眺めていただければある程度の証拠になると思います。 なお、23:30現在のこの動画の高評価・低評価数はそれぞれ189・0です。

@user-rn4kt1bl1w

Ай бұрын

@@evimalab ん？大文字と小文字の違い？だとしたら紛らわしすぎますよね？それにvはいま見ている票を表すとおっしゃいましたが動画内に説明がないですよね？これで誤解を招かないとでも思いました？ >「mがその時点での勝者の候補で、」から十分こう推測できるはずです いや口でそう言ってるだけでなぜそうなるかの説明がないんですが。 最後に聞きますけど投稿者本当にこの問題を理解していますか？

@bbbda179-ecac-cde9

Ай бұрын

for v in votes: と書いてある時点でvが「今見ている票」を表しているのは自明なのでは