![AtCoder Beginner Contest 360 A-F in 3 Minutes [English Subtitles]](/img/o.gif)
14 күн бұрын
21 күн бұрын
2 ай бұрын
Пікірлер
@nekodesumaru 3 сағат бұрын
鳩の巣原理
@kle284-vq10 10 сағат бұрын
チルノが爆破
@BENFRANK1911 10 сағат бұрын
ワイ、チルノより圧倒的に⑨で草
@kh_d23 11 сағат бұрын
投票方式がハンターハンターで草
@user-eb1su4xl5u 12 сағат бұрын
queue
@user-zb5cr7zk4j 12 сағат бұрын
ガウス積分だな。20年近く前に習ったのを思い出した。
@Normal_Person_17 17 сағат бұрын
終始頭の中が？でいっぱいだった
@user-yn1mu2eb8t 18 сағат бұрын
あれ、これって、「候補者1の票数だけを数える」→「候補者2の票数だけを数える」「暫定チャンピオン(1)と候補者2の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→「候補者3の票数だけを数える」「暫定チャンピオン(1か2)と候補者3の票数を比較して、新しい暫定チャンピオンの候補者番号と票数を記録する」→…でも定数メモリ解法にはなりますか？つまらなくて冗長なものではありますが
@evimalab 16 сағат бұрын
定数メモリですが、候補者数は定数でないので線形時間にはなりません。
@user-yn1mu2eb8t 14 сағат бұрын
@@evimalabああそうか！線形時間も出題の条件でしたね…ありがとうございます😊😊
@aoyama2019 22 сағат бұрын
数学と競技プログラミングのチャンネルなのにちゃんと時事ネタを入れてくるとは、さすがです。しかもメモリーの制約とか実態と合っていて最高です。
@YN-zx8qd Күн бұрын
このアルゴリズム偶数番目にのみ最多得票の候補者，奇数番目に常にそれ以外が来たら最多得票の人の番号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 は過半数でないという例を出してはいます。）
@user-op7ys8vp5s Күн бұрын
最後に結論言わないと分かりずらい…
@user-gz3oh6rw6v Күн бұрын
自分と違う種族と交配すると死ぬ生命体同士のお祭りか そういうとなんか実際にイかせそうな気が
@temporaurshi Күн бұрын
試しにやってみたけど目の前のライオン怖すぎて足すくんで動けず普通に食われたよ
@sxclij Күн бұрын
まず、A100を用意します（）
@nokemoyajuu Күн бұрын
0:10山本...
@A0ikun1818 Күн бұрын
票をソートして尺取りもどきのO(VlogV)？しか思いつかなかった
@birdshark36 Күн бұрын
m, cに格納されている票「以外」は全て相異なる候補者の票と相殺できる。故にm以外に過半数得票者の候補はいない。なるほど〜
@user-yn1mu2eb8t Күн бұрын
魔理沙の「じゃじゃん」ちょっと珍しくてかわいい(ゆっくり解説を見過ぎている)
@user-qg4xz9zf2v Күн бұрын
アルゴリズムとその動きだけ見ると全然上手く行ってるようには思えないのに証明を見ると確かに上手くいくと認めざるを得ないのが不思議な感覚 証明まで見た後にもう一度アルゴリズムの動きを見ると何がしたかったのか分かりやすい それにしてもこの動画に限らず前提知識を極限まで削った上で簡潔にかつわかりやすく解説できるの本当に尊敬します
@chuotokkaie233 Күн бұрын
３↑↑↑↑３円欲しい！
@user-ox5zd6ym9q Күн бұрын
投稿者こんなに頭良いなら絶対にもっと良い証明動画つくれたろ
@smuuukn Күн бұрын
乱択だなあ〜（一位が過半数取ってるなら適当にとって一位を引く確率が少なくとも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 17 сағат бұрын
@@user-qg4xz9zf2v 過半数がいない時が辛そうですね 1億票がAさん5000万票・Bさん5000万票で割れていたとき、n票を開けて「過半数はいない」と正しく評価できる確率は comb(n, n/2) / 2^n で、10万票だと0.2%しか正解できません
@The_moon_is_not_six_pence Күн бұрын
こんなシンプルな処理でチェックできるなんて…… 鳩の巣原理みたいな感じなんだろうか
@HN-bo6lq Күн бұрын
対数でも行けるかなこの問題？
@user-rn4kt1bl1w Күн бұрын
過半数二つってありえないのでは..? あと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が「今見ている票」を表しているのは自明なのでは
@user-qh1ns6et9w Күн бұрын
これ大学で習った時にクソほど感動したの覚えてる 中身はもう覚えてなかったけど
@user-jk4qp5lt6s Күн бұрын
電車の席の動画で知りました。難易度とテンポのバランスが心地よいです。 今後も応援してます🎉
@HelloingBoi-pk4io Күн бұрын
1:29 そもそも入力読み込みする時点でメモリをvに依存させない事は不可能では…?
@evimalab Күн бұрын
入力ストリームから少しずつ読み込めばメモリ量は定数で済みます（例えば C 言語の fread が使えます。なお番号がワード長に収まることは仮定してしまいます）。
@HelloingBoi-pk4io Күн бұрын
@@evimalab なるほど、ご教示ありがとうございます。
@user-wx9kv8ru9s Күн бұрын
都知事選馬鹿ばっかり立候補してるよな 都民が馬鹿ばっかりだから仕方ないけど
@aoroad Күн бұрын
過半数なら自分以外全て単一の敵勢力と見做すことができるからこういうアルゴリズムが成り立つのか。多分使い所はないけど面白い。
@user-go3ix1mp5c Күн бұрын
今回はきちんと自力でアルゴリズム思いついて嬉しい
@malc3497 Күн бұрын
すげえな
@USER-jb2er3xr1t Күн бұрын
1:14 89006（はくれいれいむ） 1341398（いざよいさくや）
@USER-jb2er3xr1t Күн бұрын
と、⑨
@USER-jb2er3xr1t Күн бұрын
Twitter見たら鶴崎さん（QuizKnock）やキム、すんさん（積分サークル）も良く見ていると聞いて。 僕は内容はほぼ分からないですが、惹かれる動画ですよねぇ。 2~3ヶ月くらい前に知ったという古参アピールをしておきます。
@JD-is8yg Күн бұрын
自分と違う票同士を対消滅させるアルゴリズムですね シンプルながら賢くて好きです
@activitydestory Күн бұрын
このコメントが一番助けになった
@bbbda179-ecac-cde9 Күн бұрын
分かりやすい
@user-eh3oi5rh7g Күн бұрын
これって過半数がいなかった場合、cを減算する量を少し減らせば過半数より小さなある特定の割合を獲得した人がいるかどうか判別できるんでしょうか だとすれば二分探索すれば最多得票者を求められそうに見えます（嘘？）
@evimalab Күн бұрын
減算量が大きくなると最初の票の比重が大きくなりすぎて狂いますが、偶然正しい m が返ることもあるはずで、二分探索に必要な単調性がなさそうです。
@user-eh3oi5rh7g Күн бұрын
@@evimalab ありがとうございます、そううまくはいきませんね……
@MINGYAOALEXANDERLIM Күн бұрын
thanks so much
@hamiltonianpathondodecahed5236 Күн бұрын
I just solved a problem on this technique 10min before you uploaded this video, would have saved me some time. Nice video.
@Chottoshitami Күн бұрын
『cは「最多得票の人がいままでの半数からどれくらい多いか」を示している』という見方もできますかね？
@evimalab Күн бұрын
もう少し複雑で、cは「新参に甘い」です。 例えば 1 1 1 1 1 2 2 2 2 2 3 と投票されると m=3, c=1 となりますが、3 は半数に全く届いていません。
@Chottoshitami Күн бұрын
@@evimalab 確かにそうですね！ありがとうございます！
@nasu_traitor Күн бұрын
知っててよかったオーダ記法
@temporaurshi 2 күн бұрын
(円周率)=3って教える教育はやっぱどう考えてもおかしかったんや
@MJS_QUIZ 2 күн бұрын
「途中まで見てヒントだけ貰おう」と思って開いたらめちゃくちゃ難しい解説で3分間ポカンだったw
@juto710 2 күн бұрын
開始10秒で分からなくなったw
@electro6290jp 2 күн бұрын
コンストラクタ解法ほんとすき
@kavascgcf 2 күн бұрын
well just dont go fast, and please suggest what stupid me could do to solve these , i pratise but still cant am i way to dumb
@guy_is_2_shy_to_talk_to_girl 2 күн бұрын
bro how u so good, i m dub and not improving, what should i do i practice but i still cant
@pctst5696 3 күн бұрын
要するに「有理数の和で無理数を作れると仮定したら矛盾した」って理解で良い？
@Zejgar 3 күн бұрын
"ueueueueueueue" kawaii
@mori_meme 3 күн бұрын
ピザの中心を特定するのが難しい
@bake3209 3 күн бұрын
無限降下法っぽいけどちょっと違うかな。 aとbの組が"最小"と仮定→それより小さい組がある→矛盾、がこの動画。 aとbの組が"存在する"と仮定→それより小さい組がある→それより小さい組がある→・・・と無限にいけるが自然数は有限なので矛盾、が無限降下法。
@user-bn9gu8xq6o 3 күн бұрын
グーグルコンプレックス👈yahoo