はてなブックマーク

私たちは、グラフアルゴリズムとして 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」というのが出てくる！！！！！！！！！！！ (ヴァネロピさんが教えてくれました。ありがとうございます。) これでこれからは、フォルダ機能と、コーディング画面と、ターミナルとを一元管理した環境で競プロができる！！！！！

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,

面白かった！ 問題へのリンク editorials 問題概要 3 つの文字 B, Y, K からなる長さ の文字列 が与えられる。 この文字列をいくつかの区間に分割する。各区間について、 ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得 ランレングス圧縮すると、K -> Y -> B の順になるもの：区間の長さだけスコアを獲得 それ以外：スコア獲得なし 区間分割の仕方を最適化したときに、得られるスコアの総和の最大値を求めよ。 制約 考えたこと 仮に の計算量を費やしてもよいならば、いつもの「区間の分割の仕方を走査していく DP」で解ける。それがうまくいかない場合には、耳DPで解けることがよくある。今回は、次のような DP で上手くいった。 dp[i][0]： の先頭から 文字目までを考えて、その終端で一旦区間を区切る場合の、スコアの最大値 dp[i

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

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