二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに、二部マッチングに関してこちらの記事を読んでいただければと思います。 実世界で超頻出！二部マッチング（輸送問題、ネットワークフロー問題）の解法を総整理！ 早見表 二部グラフの最大マッチング、最小点被覆、最大安定集合、最小辺被覆についての結論を最初にまとめます。$|V|$ はグラフの頂点数、$|M|$ は最大マッチングのサイズです。 なお、本記事の内容のあらすじは簡単に以下のスライドにまとめました。 https://www.slideshare.net/drken1215/ss-86894312 1. はじめに グラフ上の最適化問
AtCoder 版！蟻本 (中級編) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに 前回の初級編に続いて、今度は中級編です。 プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita
目次 DFS (深さ優先探索) 超入門！ 〜 グラフ理論の世界へ 〜 【前編】 からの続きです！！ 前編 0 章: はじめに 1 章: グラフとは 2 章: 計算機上でのグラフの表し方 3 章: 深さ優先探索 (DFS) と幅優先探索 (BFS) 後編 (いまここ) 4 章: グラフの様々な例題 5 章: 発展的話題 6 章: おわりに 7 章: 参考文献 4. グラフ上の様々な例題 いよいよ、深さ優先探索 (DFS) を用いて、グラフに関する様々な問題を解いてみましょう。グラフの連結性に関する問題の多くが、単純な探索によって解決できることがわかります。 そしてグラフ探索はとにかく「習うより慣れろ」の精神が重要なテーマでもあります。本記事では、グラフの連結性に関する諸概念に親しみながら、探索にも慣れるという一石二鳥を狙います。なお、ここで取り上げる問題のほとんどは DFS だけでなく BF
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita
1. なぜ 998244353 で割るのか？ 最初はこのような設問を見るとぎょっとしてしまいますが、実はとても自然な問題設定です。 $998244353$ で割らないと、答えの桁数がとてつもなく大きくなってしまうことがあります。このとき以下のような問題が生じます: 多倍長整数がサポートされている言語とされていない言語とで有利不利が生じる 10000 桁にも及ぶような巨大な整数を扱うとなると計算時間が膨大にかかってしまう 1 番目の事情はプログラミングコンテストに特有のものと思えなくもないですが、2 番目の事情は切実です。整数の足し算や掛け算などを実施するとき、桁数があまりにも大きくなると桁数に応じた計算時間がかかってしまいます。実用的にもそのような巨大な整数を扱うときは、いくつかの素数で割ったあまりを計算しておいて、最後に中国剰余定理を適用して復元することも多いです。 なぜ 9982443
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造 (通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
