マトロイド合併マトロイド交差と異なり、マトロイド合併はどんな場合でもマトロイドになり、したがって貪欲法が適用できることに注意。実装上の注意点とくになし。tot);}まとめ各行最大1個、各列最大1個のマトロイドは、交差が二部マッチングからなる独立性システムになるという事実がよく知られているが、それが交差ではなく合併になっても効率的に解けるという点で面白かった。これらの合併なのでマトロイドである、という証明をインライン展開した。*2:この証明は任意のマトロイドに適用できる。*3:独立性オラクルとしてこのような単純なアルゴリズムが使えるのはおそらくこの問題特有で、一般にはマトロイドの合併の独立性オラクルの実装は難しい気がする。CollectorTweet広告を非表示にするもっと読むコメントを書く2019-06-30AtCoderで赤になるまでにやったことAtCoderで赤タッチしたのももう1.5年も前ですが書きます。覚えていないこと・抜け・漏れなどのオンパレードですがご容赦ください。2017年11月に初めてAtCoderでredになりました。2017年11月11日なんで今更これ書いたの当時は面倒だったので書きませんでした。その後人々が変色時に記事を書いていくようになり、見かけた記事は大体全部読んでいました。微笑ましいと思ったもののAtCoderの赤でそれをやった人を見たことがなかったので、せっかくなので書こうと思いました。誰か書いていたらごめんなさい。筆者はAGCよりもARCの方が得意なため、AGCでの立ち回りは強い人に聞いてください。赤になるまでにやったこと問題を解いた2000問くらい解きました。必要になると思います。以下では蟻本上級編以上のレベルの内容を列挙していきます。列挙の漏れは100%確実にあります。(一発で正しい答えにたどり着ける確率を上げる)嘘解法についての嗅覚を鋭くする式変形を高速に、正確に行う知らないことでも実験して考えるとかが必要になる気がします。赤から落ちると思うのでそうなったらこれの通りにまた頑張ります。ここまで読んでくださりありがとうございました。2019/7/1)強い人と知り合いになれる確率がグッと高まる赤になることに限定せず、強くなることによるメリットとして、いわゆる「いつもの勢」と呼ばれる、国内オンサイトコンテスト常連の人たちについての話をしない訳にはいかないでしょう。赤になった年の翌年、入社した会社で強い人と知り合い、それがきっかけとなりいつもの勢の人々と知り合いになりました。いつもの勢の輪に入れているとは思いませんが、少なくとも観測できるようにはなったと言っていいです。彼らの競プロに対する考え方は、非常に参考になります。ストイックに精進したい人にはいい環境だと思います。OpenCupに出場できる確率が高まるこれもコネが増えたことによる帰結です。OpenCupについて、chokudaiさんなどが言及しているのをたまに目にする人がいるかもしれません。行われる、5時間チーム戦内輪コンテストです。これも社にいた強い人に教えてもらい、幸運にも組んでいただける人を見つけることができました。精進したい人にはオススメです。ARCがunratedになるARCみたいな面白いコンテストにunratedで出て新戦法を試すことができるのはメリットだと思います。ユーザによっては一度に限り変更できる場合があるようですが、なぜ私は出来ないのでしょうか?先日ユーザ名を一度だけ変更できる機能が実装されましたが、最大レートが2800以上のユーザはユーザ名の変更ができません。36日ratedに出ないともう何やっても悪くなりません。止まりで、春合宿出場者やIMO出場者に対して羨望に近い憧れを抱いていました。そんな私が、高校時代から知ってはいたものの手を出せずにいた競技プログラミングに手を出したのが大学1年の時です。盛んで、参加して緑落ちしては嘆き、黄色に昇格しては狂喜乱舞し、というのをやっていました。当時はUnionFindやbitDPすらまともに書けなかったと思います。レッドコーダーたちについては、尊敬の念をもって見ており、自分がなれるとは夢にも思っていませんでした。転機と呼べるものがいつあったか、正確には思い出せませんが、大学3年くらいの時だと思います。演習で競プロみたいな内容のものがあり、競プロの面白さに目覚めました。そのときはyukicoderあたりを埋めまくって典型を覚えていったと思います。本格的に取り組み始めたのは院生になってからだと思います。競プロに打ち込み、M1の11月にオレンジになりました。(は?)、ratedのたびに2800以上のパフォーマンスを取っては赤パフォだと喜び、2400以下のパフォーマンスを取っては落ち込み、という繰り返しをしました。途中からARCでパフォーマンス3200を取れるようになってきたので、このまま続けていればいずれは赤になれる、と徐々に確信できるようになりました。実際になれたときの喜びはひとしおでした。高校時代憧れの的でしかなかった国際科学オリンピック出場者に一歩だけ近づけたのだという思いが湧きました。_)m*1:誰も「赤になる方法」みたいな記事を書きたがらないように見えるのは、こういう情報量ゼロの内容しかないからでは、と思っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。