「n = 10^10000 などの巨大なケースを考えると、c の保持などに必要な領域は n に依存するのでは」というご指摘かと思っていました。 （これに対する答えは「それはどうしようもないので許してください」です。） 唯一の過半数の候補 m が実際に過半数であるかの判定（二周目）はどうするのかということでしたか？ 一周目終了時の m の値を残したまま c = 0 for v in votes: if v == m: c += 1 とすれば追加のメモリは不要です。 （100億個の数値を保持するのに80GB必要というのは、[0, 0, 0, ..., 0] という長さ100億の配列を作ったらということです。）
はい。（どの部分に対しておっしゃっていますか？この動画は全体的に過半数得票者が一人以下であることを前提としています。） vは「いま見ている票」を表す変数です。（別とはなんでしょうか？この動画のどの部分が誤っていますか？） 今回の証明に「行間」はほぼなく、さらに詳しく解説するのはなかなか難しいと思います。 英語になってしまいますが、en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm#Correctness に文章での証明があります（この動画の V が n となっています）。
![21 Weird Ways to Say Hello, World! 1,000,000 Times [English Subtitles]](http://i.ytimg.com/vi/OHOTGcQmndQ/mqdefault.jpg)
過半数なら自分以外全て単一の敵勢力と見做すことができるからこういうアルゴリズムが成り立つのか。多分使い所はないけど面白い。
自分と違う票同士を対消滅させるアルゴリズムですね
シンプルながら賢くて好きです
このコメントが一番助けになった
分かりやすい
Rolandアルゴリズム
アルゴリズムとその動きだけ見ると全然上手く行ってるようには思えないのに証明を見ると確かに上手くいくと認めざるを得ないのが不思議な感覚
証明まで見た後にもう一度アルゴリズムの動きを見ると何がしたかったのか分かりやすい
それにしてもこの動画に限らず前提知識を極限まで削った上で簡潔にかつわかりやすく解説できるの本当に尊敬します
今回はきちんと自力でアルゴリズム思いついて嬉しい
すげえな
数学と競技プログラミングのチャンネルなのにちゃんと時事ネタを入れてくるとは、さすがです。しかもメモリーの制約とか実態と合っていて最高です。
I just solved a problem on this technique 10min before you uploaded this video, would have saved me some time.
Nice video.
電車の席の動画で知りました。難易度とテンポのバランスが心地よいです。
今後も応援してます🎉
1位の番号をメモリに記憶して2周目forの頭に「1位の票の場合continue」とすれば2位候補も出せるから、決選投票にも対応できますね
こんなシンプルな処理でチェックできるなんて……
鳩の巣原理みたいな感じなんだろうか
対象とした候補を巣、それ以外の候補を鳩とすればすっきりするね
少なくとも巣が全部埋まらなければ対象以外の候補は過半数な訳がない
乱択だなあ〜（一位が過半数取ってるなら適当にとって一位を引く確率が少なくとも1/2あるので、10万回ランダムに引いたときに一位を一度も引かない確率が高々1/2^10万 はまあ無視できる）
と考えてたらしっかり潰されててかなC
【追記】
（なぜか返信がうまく表示されないので追記するのですが）
10万票ランダムに引いた後にそれで出てきた最大10 万人ぞれぞれが過半数を超えるかは愚直に数えればよいです
これなら配列サイズが10万(定数)で計算時間は Θ(N) (線形) を達成します
引いたものの中に一位のものが含まれていてもそれが一位かどうか判別できるんですかね...？
例えばAという候補に51%の票が入ってBに49%票が入っている時(他は0票)はその手法での失敗率は無視できない値になりそう
@@おれっち-s9o
10万個ランダムに引いた時の候補者は高々10万種類なので、その10万種類の候補者の票数を普通にメモリで持って愚直に数えて過半数を超えるやつがいるか見れば良いです
（10万の中に一位が含まれてる確率が非常に高いため）
これなら計算量は変わらずO(N)ですが、配列サイズがNに依らずに10万固定で計算ができます
@@おれっち-s9o
過半数がいない時が辛そうですね
1億票がAさん5000万票・Bさん5000万票で割れていたとき、n票を開けて「過半数はいない」と正しく評価できる確率は comb(n, n/2) / 2^n で、10万票だと0.2%しか正解できません
魔理沙の「じゃじゃん」ちょっと珍しくてかわいい(ゆっくり解説を見過ぎている)
『cは「最多得票の人がいままでの半数からどれくらい多いか」を示している』という見方もできますかね？
もう少し複雑で、cは「新参に甘い」です。
例えば 1 1 1 1 1 2 2 2 2 2 3 と投票されると m=3, c=1 となりますが、3 は半数に全く届いていません。
@@evimalab 確かにそうですね！ありがとうございます！
投票方式がハンターハンターで草
1:50
たまに間違っても良いなら、「先頭から1000票読み込んで全得票者をメモ、その人たちについてのみ得票数を数える」とすればほぼ解けるはずだ。
過半得票者が先頭1000票に現れない2^-1000程度の確率で誤答することになる。
(競技プログラミングなら絶対に過半得票者が後ろ半分に固めてある意地悪テストケースが存在するはずなので例えばfloor(V＊i/1000)票目(iは1→1000)を取り出すみたいな非本質的な操作が必要になるよ
thanks so much
I dont think I would come up with a prove by induction, ty for the video
これって過半数がいなかった場合、cを減算する量を少し減らせば過半数より小さなある特定の割合を獲得した人がいるかどうか判別できるんでしょうか
だとすれば二分探索すれば最多得票者を求められそうに見えます（嘘？）
減算量が大きくなると最初の票の比重が大きくなりすぎて狂いますが、偶然正しい m が返ることもあるはずで、二分探索に必要な単調性がなさそうです。
@@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)を返す。結果は同じと言えるか？
結果は同じではなさそう（c が表すものがかなり異なります）ですが過半数要素がある場合はそれが m になりそうです。
ただし、定数メモリで実装するのは困難だと思います。
（入力を書き換えてしまえば追加の領域はほとんど不要そうですが、定数メモリといえるかは怪しそうです。）
@@evimalab
そうですね。Ο(logn)のメモリは必要でしょう
あと、奇数番地が過半数、偶数番地ザコで死にますね
mを投票先数のbool配列にしたΟ(mlogn)はないと厳しいかもですね
0:10山本...
Twitter見たら鶴崎さん（QuizKnock）やキム、すんさん（積分サークル）も良く見ていると聞いて。
僕は内容はほぼ分からないですが、惹かれる動画ですよねぇ。
2~3ヶ月くらい前に知ったという古参アピールをしておきます。
票をソートして尺取りもどきのO(VlogV)？しか思いつかなかった
過去一、一発で理解できんかったわ……
あれ、これって、「候補者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
なるほど、ありがとうございます！
1:29 そもそも入力読み込みする時点でメモリをvに依存させない事は不可能では…?
入力ストリームから少しずつ読み込めばメモリ量は定数で済みます（例えば C 言語の fread が使えます。なお番号がワード長に収まることは仮定してしまいます）。
@@evimalab なるほど、ご教示ありがとうございます。
まず、A100を用意します（）
落語で、味噌汁をちゃんと混ぜたら大体味は均等になるよね、
的な話があって面白かった。
過半数か確認するのに結局nの半数の数字を数えられるだけのメモリが必要なら、結局メモリ使用量がnに依存しちゃってない？
過半数得票者ではなく、最多得票者を見つける方法になってない？
> 過半数得票者ではなく、最多得票者を見つける方法になってない？
いいえ。1 2 1 2 3 をこの順に集計すると 3 が出力されます。
> 過半数か確認するのに結局nの半数の数字を数えられるだけのメモリが必要なら、結局メモリ使用量がnに依存しちゃってない？
nや候補者番号が計算機のワード長（64bitなど）に収まるという想定はしてしまっています（多くの場合で許されると思います）。
「定数個の変数」などといった方が正確だったかもしれません。
@@evimalab 素人質問に丁寧な回答をしていただきありがとうございます。
動画内では100億個の数字を保持するのに80GB必要とのことでしたが、半分の50億を『数えるだけ』なら64bitに収まるということでしょうか？
「n = 10^10000 などの巨大なケースを考えると、c の保持などに必要な領域は n に依存するのでは」というご指摘かと思っていました。
（これに対する答えは「それはどうしようもないので許してください」です。）
唯一の過半数の候補 m が実際に過半数であるかの判定（二周目）はどうするのかということでしたか？
一周目終了時の m の値を残したまま
c = 0
for v in votes:
if v == m:
c += 1
とすれば追加のメモリは不要です。
（100億個の数値を保持するのに80GB必要というのは、[0, 0, 0, ..., 0] という長さ100億の配列を作ったらということです。）
@@evimalab なるほど理解しました。
解説まで付けてくださりありがとうございます。
とても面白い動画でした。
テーマは面白かったけど説明があっさりしすぎてほんとんど理解出来なかった、数学は好きなんだけどな...
数学って便利だな(浅い意見)
このアルゴリズム偶数番目にのみ最多得票の候補者，奇数番目に常にそれ以外が来たら最多得票の人の番号mに入らなくない？（最初のデータは１番目とする）
最多得票の人を求めるアルゴリズムではありません。
1 9 2 9 3 9 4 9 5 9 と投票された場合、m=5, c=0 で終わり、過半数なしと判定されます。
@@evimalab 調べてみたら「過」半数が入力中に存在する場合のみ動作するアルゴリズムなのね
勉強になりました
過半数が存在しない場合も、動画で述べた通り入力を2周すればそのことを検出できます。
（その場合も線形時間です。なお 0:56 で 3/6 は過半数でないという例を出してはいます。）
기계 음성 쓰지 마라. 도저히 들어줄 수 없네
Please use the mute button.
過半数二つってありえないのでは..?
あと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が「今見ている票」を表しているのは自明なのでは