How to Find the Majority Vote Winner in an Election with 10 Billion Candidates
Вставка
- Опубліковано 21 лип 2024
- Introducing the Boyer-Moore majority vote algorithm. The only prerequisite knowledge is mathematical induction.
(Reference)
en.wikipedia.org/wiki/Boyer%E...
0:00 Intro
0:26 Problem Statement
2:00 Algorithm
3:31 Proof
X: x.com/evima0 - Наука та технологія
![Can You Measure 3000√2-4211 Minutes with a 1-Minute and √2-Minute Hourglass? [English Subtitles]](http://i.ytimg.com/vi/jNHJ3z6L5AQ/mqdefault.jpg)
![How Many Guards Are Needed in an N-sided Polygon Museum? [English Subtitles]](/img/n.gif)
過半数なら自分以外全て単一の敵勢力と見做すことができるからこういうアルゴリズムが成り立つのか。多分使い所はないけど面白い。
自分と違う票同士を対消滅させるアルゴリズムですね
シンプルながら賢くて好きです
このコメントが一番助けになった
分かりやすい
Rolandアルゴリズム
アルゴリズムとその動きだけ見ると全然上手く行ってるようには思えないのに証明を見ると確かに上手くいくと認めざるを得ないのが不思議な感覚
証明まで見た後にもう一度アルゴリズムの動きを見ると何がしたかったのか分かりやすい
それにしてもこの動画に限らず前提知識を極限まで削った上で簡潔にかつわかりやすく解説できるの本当に尊敬します
1:14
89006（はくれいれいむ）
1341398（いざよいさくや）
と、⑨
今回はきちんと自力でアルゴリズム思いついて嬉しい
すげえな
電車の席の動画で知りました。難易度とテンポのバランスが心地よいです。
今後も応援してます🎉
数学と競技プログラミングのチャンネルなのにちゃんと時事ネタを入れてくるとは、さすがです。しかもメモリーの制約とか実態と合っていて最高です。
I just solved a problem on this technique 10min before you uploaded this video, would have saved me some time.
Nice video.
こんなシンプルな処理でチェックできるなんて……
鳩の巣原理みたいな感じなんだろうか
落語で、味噌汁をちゃんと混ぜたら大体味は均等になるよね、
的な話があって面白かった。
thanks so much
『cは「最多得票の人がいままでの半数からどれくらい多いか」を示している』という見方もできますかね？
もう少し複雑で、cは「新参に甘い」です。
例えば 1 1 1 1 1 2 2 2 2 2 3 と投票されると m=3, c=1 となりますが、3 は半数に全く届いていません。
@@evimalab 確かにそうですね！ありがとうございます！
魔理沙の「じゃじゃん」ちょっと珍しくてかわいい(ゆっくり解説を見過ぎている)
これって過半数がいなかった場合、cを減算する量を少し減らせば過半数より小さなある特定の割合を獲得した人がいるかどうか判別できるんでしょうか
だとすれば二分探索すれば最多得票者を求められそうに見えます（嘘？）
減算量が大きくなると最初の票の比重が大きくなりすぎて狂いますが、偶然正しい m が返ることもあるはずで、二分探索に必要な単調性がなさそうです。
@@evimalab ありがとうございます、そううまくはいきませんね……
乱択だなあ〜（一位が過半数取ってるなら適当にとって一位を引く確率が少なくとも1/2あるので、10万回ランダムに引いたときに一位を一度も引かない確率が高々1/2^10万 はまあ無視できる）
と考えてたらしっかり潰されててかなC
【追記】
（なぜか返信がうまく表示されないので追記するのですが）
10万票ランダムに引いた後にそれで出てきた最大10 万人ぞれぞれが過半数を超えるかは愚直に数えればよいです
これなら配列サイズが10万(定数)で計算時間は Θ(N) (線形) を達成します
引いたものの中に一位のものが含まれていてもそれが一位かどうか判別できるんですかね...？
例えばAという候補に51%の票が入ってBに49%票が入っている時(他は0票)はその手法での失敗率は無視できない値になりそう
@@user-qg4xz9zf2v
10万個ランダムに引いた時の候補者は高々10万種類なので、その10万種類の候補者の票数を普通にメモリで持って愚直に数えて過半数を超えるやつがいるか見れば良いです
（10万の中に一位が含まれてる確率が非常に高いため）
これなら計算量は変わらずO(N)ですが、配列サイズがNに依らずに10万固定で計算ができます
@@user-qg4xz9zf2v
過半数がいない時が辛そうですね
1億票がAさん5000万票・Bさん5000万票で割れていたとき、n票を開けて「過半数はいない」と正しく評価できる確率は comb(n, n/2) / 2^n で、10万票だと0.2%しか正解できません
初手で分割統治法がいいのではと思ったがどうなるんだろうか？
要素数が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)を返す。結果は同じと言えるか？
結果は同じではなさそう（c が表すものがかなり異なります）ですが過半数要素がある場合はそれが m になりそうです。
ただし、定数メモリで実装するのは困難だと思います。
（入力を書き換えてしまえば追加の領域はほとんど不要そうですが、定数メモリといえるかは怪しそうです。）
@@evimalab
そうですね。Ο(logn)のメモリは必要でしょう
あと、奇数番地が過半数、偶数番地ザコで死にますね
mを投票先数のbool配列にしたΟ(mlogn)はないと厳しいかもですね
投票方式がハンターハンターで草
票をソートして尺取りもどきのO(VlogV)？しか思いつかなかった
0:10山本...
過去一、一発で理解できんかったわ……
あれ、これって、「候補者1の票数だけを数える」→「候補者2の票数だけを数える」「暫定チャンピオン(1)と候補者2の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→「候補者3の票数だけを数える」「暫定チャンピオン(1か2)と候補者3の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→…でも定数メモリ解法にはなりますか？つまらなくて冗長なものではありますが
定数メモリですが、候補者数は定数でないので線形時間にはなりません。
@@evimalabああそうか！線形時間も出題の条件でしたね…ありがとうございます😊😊
2:37 ここでなぜm=8となるのでしょうか?elif m=vのvは9だと思うのですが…
3:26 あとここで表をもう一周して数えるのでは定数メモリを使った意味がないと思いますが…
> 2:37 ここでなぜm=8となるのでしょうか?
すみません、間違えました。「mが9じゃないから」です。
> 3:26 あとここで表をもう一周して数えるのでは定数メモリを使った意味がないと思いますが…
2周目に必要なメモリ量は定数（m の値とカウンター、数値2個）なので全体でも定数メモリのままです。
@evimalab
なるほど、ありがとうございます！
自分と違う種族と交配すると死ぬ生命体同士のお祭りか
そういうとなんか実際にイかせそうな気が
まず、A100を用意します（）
テーマは面白かったけど説明があっさりしすぎてほんとんど理解出来なかった、数学は好きなんだけどな...
1:29 そもそも入力読み込みする時点でメモリをvに依存させない事は不可能では…?
入力ストリームから少しずつ読み込めばメモリ量は定数で済みます（例えば C 言語の fread が使えます。なお番号がワード長に収まることは仮定してしまいます）。
@@evimalab なるほど、ご教示ありがとうございます。
このアルゴリズム偶数番目にのみ最多得票の候補者，奇数番目に常にそれ以外が来たら最多得票の人の番号mに入らなくない？（最初のデータは１番目とする）
最多得票の人を求めるアルゴリズムではありません。
1 9 2 9 3 9 4 9 5 9 と投票された場合、m=5, c=0 で終わり、過半数なしと判定されます。
@@evimalab 調べてみたら「過」半数が入力中に存在する場合のみ動作するアルゴリズムなのね
勉強になりました
過半数が存在しない場合も、動画で述べた通り入力を2周すればそのことを検出できます。
（その場合も線形時間です。なお 0:56 で 3/6 は過半数でないという例を出してはいます。）
Twitter見たら鶴崎さん（QuizKnock）やキム、すんさん（積分サークル）も良く見ていると聞いて。
僕は内容はほぼ分からないですが、惹かれる動画ですよねぇ。
2~3ヶ月くらい前に知ったという古参アピールをしておきます。
過半数二つってありえないのでは..?
あと2:12のm=vとかm==vとかのvは別の変数では?
あと証明のとこ詳しい解説が欲しいです
はい。（どの部分に対しておっしゃっていますか？この動画は全体的に過半数得票者が一人以下であることを前提としています。）
vは「いま見ている票」を表す変数です。（別とはなんでしょうか？この動画のどの部分が誤っていますか？）
今回の証明に「行間」はほぼなく、さらに詳しく解説するのはなかなか難しいと思います。
英語になってしまいますが、en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm#Correctness に文章での証明があります（この動画の V が n となっています）。
@@evimalab
最初の疑問については自己解決しました
アルゴリズムの解説のとこで右上でv=9となっています
3:15なぜ「mが過半数だろう」という推測になるのですか？
3:45mの票c枚は必ず取れますか？
このチャンネルの動画全体に言えますが行間は滅茶苦茶あります。まだこの問題に触れたことがなく理解の浅い視聴者の気持ちを投稿者が分かっていないのか、そもそも投稿者も理解していなくてただ英文を略しているだけなのかは知りませんが...
右上は V=9 です。
> 3:15なぜ「mが過半数だろう」という推測になるのですか？
2:13 の「mがその時点での勝者の候補で、」から十分こう推測できるはずです。
> 3:45mの票c枚は必ず取れますか？
そのことを含む主張をこれから証明します。
> このチャンネルの動画全体に言えますが行間は滅茶苦茶あります。
ほかの動画に行間が少なくないものがあることは否定しませんが、この動画では少なく抑えました。
このことの証明は難しいですが、他のコメントをすべて眺めていただければある程度の証拠になると思います。
なお、23:30現在のこの動画の高評価・低評価数はそれぞれ189・0です。
@@evimalab
ん？大文字と小文字の違い？だとしたら紛らわしすぎますよね？それにvはいま見ている票を表すとおっしゃいましたが動画内に説明がないですよね？これで誤解を招かないとでも思いました？
>「mがその時点での勝者の候補で、」から十分こう推測できるはずです
いや口でそう言ってるだけでなぜそうなるかの説明がないんですが。
最後に聞きますけど投稿者本当にこの問題を理解していますか？
for v in votes:
と書いてある時点でvが「今見ている票」を表しているのは自明なのでは