はてなブックマーク

私たちは、グラフアルゴリズムとして DFS や BFS を学ぶと 頂点 s から頂点 t へ辿り着けるかどうかを判定する 連結成分の個数を求める 二部グラフ判定する トポロジカルソートする などといった例題を次々とこなしていき、グラフ探索スキルを高めていく道を歩んでいくことになります。そんな長い道のりにおいて、脱初級者の登竜門とも言うべき難所として、本記事ではサイクル検出を解説します！ AtCoder でも、ABC-E や水色 diff などでよく出題されるテーマです。 目次 最終的なサイクル検出コードを「4. まとめのコード」で示すので、時間のない方はそこに飛んでもらえたらと思います。Yosupo Judge Library Checker の「Cycle Detection (Directed)」と「Cycle Detection (Undirected)」を通します。 また、ABC

こんばんは！！！ けんちょんです！ 新しく本を出させていただくことになりましたので、報告いたします。 この本は次の Qiita の記事を単行本化したものです。 qiita.com amazon リンク 今度はどんなコンセプトで、どんな内容で、どんなターゲット層を想定した本なのかについて、簡単に紹介します。 1. 本書のコンセプト 今回の本は、 AtCoder を何も知らない方が入門できる！ AtCoder を布教したい方が「とりあえずこれ読めばいいよ」と言える！ C++ と Python の両言語で入門できる！ ことを目指した AtCoder の入門本です。おそらく、史上最も易しい競プロ本です。 Python で競プロしている方が C++ に乗り換えるキッカケになったり、C++ で競プロしている方が Python に乗り換えるキッカケになったりすることも狙っています。 章 位置付け 内容

1. はじめに お久しぶりです！ けんちょん本のけんちょんです。 最近はアルゴリズムがとても盛り上がっていますね。今回新たなアルゴリズム本を上梓させていただくことになりました！ 発売予定日は 2022/4/20 です。一部大型書店では、もうすでに並んでいるはずです。今回の記事では、この本を通してお届けしたいメッセージや、想定読者、内容などについて簡単に紹介させていただきます。 amazon ページへのリンク 2. 本書の内容と対象読者 2-1. 本書の内容 百聞は一見に如かずということで、まずは目次構成をお見せします！ 第 1 章：アルゴリズム入門 第 1 話：「テンパズル」　〜 力まかせ探索 第 2 話：「小町算」　〜 再帰関数 第 3 話：「虫食算」　〜 枝刈り 第 II 章：グラフアルゴリズム 第 4 話：「数独」　〜 深さ優先探索 1 第 5 話：「覆面算」　〜 深さ優先探索 2

1. はじめに お久しぶりです！ けんちょんです。 これまで 3 年間にわたって、Qiita に、アルゴリズムに関するさまざまな話題を投稿し続けてきました: アルゴリズムとは何か！？ 計算量オーダーの求め方を総整理！ 動的計画法超入門！ 再帰関数を学ぶと、どんな世界が広がるか スタックとキューを極める！ ソートを極める！ DFS (深さ優先探索) 超入門！ 実世界で超頻出！二部マッチングの解法を総整理！‬ このたび、それらの記事を有機的にまとめ上げ、さらに多数のトピックを追加する形で、アルゴリズム入門書を上梓させていただくことになりました！ 大槻兼資著、秋葉拓哉監修：問題解決力を鍛える!アルゴリズムとデータ構造 - amazon 発売予定日は 2020/9/30 となっています。講談社サイエンティフィク様からの発売となります。今回の記事では、この本を通してお届けしたいメッセージや、想定読者

時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています！！！ AtCoder ABC 165 C - Many Requirements　(昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu AtCoder ABC 161 D - Lunlun Number パナソニックプログラミングコンテスト D - String Equivalence これらの多くは緑後半から水色前半の difficulty を叩き出す、とても恐れられている問題たちです。しかし実のところ、「ちょっと複雑だけど、単純に全探索するだけ」という側面もあります。 これらの出題が最近急増しているのは、おそらくは AtCoder 社側に 最近の AtCo

VSCode は神！！！！！ けんちょんは、emacs から VSCode への移行を決意しました。そのキッカケとなったのは、 どーーーーーん！！！！！！！！！ ターミナルを右側に表示させることができるのだ！！！ 実は以前にも、emacs から VSCode への移行を試みたことがあった。だがそのときは挫折した。その理由は「ターミナルを右側に表示させる方法がわからなかったから」だ。 でも、今回できたので、VSCode への移行を決めたのだ。その方法は実は簡単だった。 terminal と書かれているところを右クリックすると、「Move Panel Right」というのが出てくる！！！！！！！！！！！ (ヴァネロピさんが教えてくれました。ありがとうございます。) これでこれからは、フォルダ機能と、コーディング画面と、ターミナルとを一元管理した環境で競プロができる！！！！！

個数制限なしナップサック！！！！！！！ 問題へのリンク 問題概要 種類の魔法を駆使して、HP が のモンスターを倒したい。 番目の魔法は、魔力を だけ消費して、モンスターの HP を だけ減らすことができる モンスターの HP を 0 以下にするのに消費する魔力の最小値を求めよ。 制約 解法 (1) これは個数制限なしナップサック問題そのもの！！！！！ 普通のナップサックは、容量 以内で、価値を最大化する問題だけど、今回は魔法によってモンスターに与えるダメージが 以上になる範囲で、魔力を最小化する問題。 実質はほとんど一緒になります。個数制限なしナップサックは、以前これらの記事に書いてみました！！！ qiita.com 今回の DP をざっくり書くと、 dp[ i ][ h ] := 最初の i 種類の魔法でモンスターに h のダメージを与える場合の、消費魔力の最小値 とする。このとき d

0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見ても ABC-C の中でも高めの傾向です。 ABC 147 C - HonestOrUnkind2 (972) ABC 128 C - Switches (728) ABC 119 C - Synthetic Kadomatsu (1306) ABC 104 C - All Green (1396) bit 全探索の考え方や実装は、以下の記事にまとめてみました。 drken1215.hatenablog.com しかし、全探索アルゴリズムにおいて、より汎用的な方法として再帰関数を用いるというのがあります。むしろ、再帰関数を自在に書

0. はじめに ビット演算については、以下の記事で特集しました。 qiita.com しかし、この中で、bit 全探索に関する説明がだいぶ簡潔すぎたので、ちゃんと書きたいなと思って、この記事書きます！！！ただし、ビット演算に関する知識は前提としているので、そこに不安のある方は上の記事を読んでもらえたらと思います。 具体的には、以下の表を見てピンとこなかった場合には、先に上記の記事を読んでもらえたらと思います。 なお、この記事は、 Competitive Programming (1) Advent Calendar 2019 の 6 日目の記事として書きました。 1. bit 全探索で何ができるか bit 全探索とは、 個のものから、いくつか選ぶ方法を全列挙して調べ上げる手法 です！！！ 個のものからいくつか選ぶ方法は、 通りの選択肢があります。たとえば のとき、3 個のアイテム {2,

最初、頂点にアルファベット、辺に文字列を乗せたグラフを考えていたが、うまく解けなかった。 頂点に文字列を乗せて、しりとりが成立する箇所に辺を張ったグラフを考えるとうまくいった。 問題へのリンク 問題概要 英大文字 2 文字からなる 個の文字列 が与えられる。 次の条件を満たす文字列の集合のサイズの最小値を求めよ。 任意の に対して、集合に含まれる文字列が存在して、 はその文字列の部分文字列である 集合に含まれる文字列の長さ 2 の任意の部分文字列は、 のいずれかに一致する 制約 考えたこと 最初は、頂点がアルファベット文字を持たせたグラフを考えた。各 に対して、文字列 の 0 文字目から 1 文字目へと有向辺を張る。 こうしてできたグラフ上で、最小本数のウォークによって、すべての辺を被覆する問題と考えられた。まず、比較的明らかな考察として、強連結成分内ではすべての辺を通るウォークを構築でき

0. はじめに プログラミングコンテストにおいて、連立一次方程式を解くことに帰着できる問題は数多く出題されています。 連立一次方程式は Gauss Jordan の掃き出し法によって解くことができるのですが、「その解の個数を求めよ」などと言われたときに詰まりがちな印象があったので、簡単に解説してみます。 なお、掃き出し法を要求する問題は競プロでは「実数」「 」「mod. p」の 3 パターンがあるイメージです。特に「解の個数を求めよ」という問題に関しては、 を変数の個数として 係数 解の個数 実数 一般には無限個 mod. となります。ここで、 は の特殊な場合 () なのですが、出題も多く bitset を用いた高速化なども決まったりするので特別扱いしています。 1. 掃き出し法が目指すもの まずは、掃き出し法が何をするためのアルゴリズムなのかについて、概説します。 1-1. 標準形 掃

Qiita に移植しました 重みつき Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて

この記事は、Competitive Programming Advent Calendar Div2012の12日目の記事として書きました。 0. はじめに 今回はマトロイドについて書きたいと思います。 マトロイドはGreedyとの関連でよく耳にします。では、そもそもマトロイドがGreedy性を持つのは何故でしょうか？実は、マトロイドは単に「Greedyの一例」として出て来るばかりでなく、「現在効率的なアルゴリズムが知られている問題の殆どはマトロイドが何かしら関わっている」と言える程にイイ構造を持っています。以前、以下のようなツイートをしました。 dpやってていつも思うのが、なんか凸凹してるなーと。凸凹し過ぎてdpじゃなきゃ解けないよな、みたいな感じ。マトロイドは凹んでるところがない凸なイメージ。だから、局所最適狙う貪欲法だけで最適解に辿り着ける。焼き鈍しなんて必要ない。 本記事では、この