How to Find the Majority Vote Winner in an Election with 10 Billion Candidates 

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

分かりやすい

Rolandアルゴリズム

と、⑨

すげえな

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

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

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

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

引いたものの中に一位のものが含まれていてもそれが一位かどうか判別できるんですかね...？ 例えば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%しか正解できません

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

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

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

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

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

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

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

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

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

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

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

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

はい。（どの部分に対しておっしゃっていますか？この動画は全体的に過半数得票者が一人以下であることを前提としています。） 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が「今見ている票」を表しているのは自明なのでは