深さ優先探索

atcoder.jp・参考 Editorial - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)・説明 引数に頂点vとvまでの長さlengthを持つ、DFSをしていく。最大の長さをansとして、length>ansのときansを更新していく。注意点として帰りがけに頂点vを未探索にすることを忘れずに。 n,m=map(int, input().split()) g=[[]for _ in range(n)] C=[[0 for _ in range(n)]for _ in range(n)] for _ in …

atcoder.jp・参考： よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録・やったこと：参考記事の内容をpythonで勉強した。長さがNのリストAをDFSで全探索する。その時の得点(score)が一番高いものがansになる。 #参考：https://drken1215.hatenablog.com/entry/2020/05/04/190252 n,m,q=map(int,input().split()) a=[0 for _ in range(q)] b=[0 for _ in range(q)] c=[0 for _ in range(q)…

atcoder.jp・参考： Editorial - AtCoder Beginner Contest 308・考え方：参考の通りDFSをして、H,W座標まで行けるのか(seen[h-1][w-1]を探索済みにできるか)をすればいい。snukeの文字の管理、例えば's'のあとに'n'とかはnx={}で辞書型で管理する。・ACコード： import sys sys.setrecursionlimit(10**6) #再帰関数の回数を10**6まで増やす h,w=map(int, input().split()) f=[input() for _ in range(h)] if f[0][0]!=…

競プロで、ロジックの勉強してるときに、分からなくて色々調べたら、 タイトルにある、DFS関数にたどり着いた。 深さ優先探索 というワードの意味が、いまいちピンとこなくて、他のないのかな〜って思うけど、そこが味噌ではないから、まあ、ええかと。。。 調べると、C系言語で書かれた例が見つかった。ただ、自分はPHPを勉強しているのと、C系言語が理解できないので、Chat GPTさんに、php に置換してもらった。それが以下のコード。あと、課金したGPTさんの返答なんで、アプデ前のだとどう返ってくるかは知らん。 あと、このコードに対して、分かりやすく解説して！って投げたら、解説してくれました笑 流石！ …

深さ優先探索（Depth-First Search） ある状態からはじめて、遷移できなくなるまで状態を進める。遷移できなくなったら1つ前の状態に戻る。上記はstackのpushとpopで実現できる。このため、深さ優先探索は再帰関数（呼び出し元に戻る）で実装できる場合が多い。 部分和問題（Partial Sum） {a1, a2, ..., an}からいくつか選んだ和がkになるかを判別する。今回は深さ優先探索で各組み合わせの和をすべて求める。a1から順に和に加えないor加えるを決める。このため、以下のような二分木に対して、深さ優先探索を行えば良い。 public class PartialSum…

2023/03/04（土）修整：Problem#solve_dfsとProblem#dfsを高速化 2023/03/06（月）修整：Questionクラスをリファクタリング 目次 目次 多重ループを避ける方法 覆面算とは 覆面算の解き方 10重ループと深さ優先探索の比較 覆面算を解くプログラムのソースコード全文 おわりに 参考 多重ループを避ける方法 Rubyで多重ループを避ける方法には、Array#productを使う方法があります。 しかし、この方法では不要な計算をスキップすることができません。 そこでおすすめするのが深さ優先探索(バックトラック法, DFS)です。 この方法では、ループを…

鉄道・道路・航空などの交通、通信・電気・ガス・水道などのインフラストラクチャなどなど、我々の生活にネットワークは欠かせません。ネットワークに対して行う処理は多岐にわたり、アルゴリズムの研究と応用の代表的分野になっています。前回に打ち上げた「アルゴリズムアニメーション」実例としてネットワークアルゴリズムを取り上げます。これからの説明は前回紹介した程度の教科書・参考書を一応見た方に、理解を確実にしていただくことを想定しています。まったく初めてという方はまず教科書を一読願います。 いろんなネットワークがありますが、その本質は(V, E, w)という3つ組みで表現できます。V は頂点の集合、EはV✖️…

世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム- 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」内容紹介 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」目次 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第2巻-高度な設計と解析の手法・高度なデータ構造・グラフアルゴリズム-」Amazonでの購入はこちら 「世界標準MIT教科…

トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）に参加しました。 結果 A,B,Cの３問正解でした。 D問題は、これで解けるだろうと思ったアルゴリズムを実装してもTLEが出て最後まで解決できなかった。 解説を斜め読みした感じだと、思っていたアルゴリズムだとダメだったみたい。 A - Penalty Kick 問題文のとおりに処理して答えるだけの問題。 １～Nまでの整数のうち３の倍数ではない数の個数を答える問題。 剰余演算で１個ずつ３の倍数かどうかを確認して数えれば良い。 ループ処理と剰余演算ができれば解ける問題。 B - Farthe…

自己紹介 2024 年春にモノグサで SWE としてインターンに参加しました、宮崎と申します。2024 年 3 月現在、慶應義塾大学理工学部の 1 年生です。 参加を決めた理由 もともと春休みに大きな予定がなく、何かしらの春季インターンに参加することは考えていました。そんなとき、AtCoderJobs でモノグサの募集を見て、実際のサービスの開発に携われることに魅力を感じたこと、また AtCoder Beginner Contest や ICPC のスポンサーなどを通して会社について認知していたことから、応募を決めました。 取り組んだこと 主に管理者用 Web クライアントでの Book 編集…

概要 Atcoderで最近Python -> Rustに移行している最中でライブラリを作成中． ライブラリーを作りつつ，Atcoderで使えるcrate一覧に記載があるcrateを眺めているのでそのメモ． 使えそうな問題があれば別途記事をまとめていく． https://img.atcoder.jp/file/language-update/language-list.html#:~:text=Rust ac-library-rs@=0.1.1 acl (AtCoder Library)のRust実装版． https://atcoder.github.io/ac-library/master/d…

↓↓クリックして頂けると励みになります。ランキング参加中プログラミング 【25 | リストとファイル入出力】 ホーム】 >> 【27 | ファイルへの書き込み】 キューとスタック C++におけるキュー（Queue）とスタック（Stack）は、データを保持するための抽象的なデータ構造です。 これらは、データの挿入と取り出しの方法によって異なります。キュー（Queue）: キューは、先入れ先出し（FIFO：First In, First Out）のデータ構造です。 つまり、最初に追加された要素が最初に取り出されます。 キューは、要素の挿入が末尾に行われ、要素の取り出しは先頭から行われます。スタック…

問題 atcoder.jp 茶色Diff 431 再帰問題（そんなカテゴリーは無い） 考察 あるマスに入ったら以下の処理を行う そのマスが範囲外だったら即終了 0 return そのマスがすでに通過したマスと同じ値だったら0 return そのマスがGoalマスだったら +1 を return 上３つに該当しなければそのマスの数字をどこぞに保存 右か下に移動してループ最初から開始 で全部の処理が終わったらその出力値がそのまま答え 深さ優先探索の典型って感じですね というわけで実装 制約は H, W <= 10 であり、計算量は全探索できた場合右に10回、下に10回移動した場合で らしいです ネ…

問題 atcoder.jp 茶色Diff 422 考察 そもそも順列を知らない 中学校で学ぶらしいので、つまり中学数学すら知らなかったという事実に震える まぁ場合の数、順列とか耳にしたことはありますけど全く記憶にない ... 一手目すらよく分からなかったので順列だけググることにする c++ には色んな要素を順列順に並ばせてくれる next_permutaion, prev_permutation という便利なメソッドを発見 これを使って解いてみる 順列を知ってる人なら一瞬で解ける問題なんだろう 順列の生成方法さえわかれば解法はとても簡単 順列で動かす前の配列を用意して 配列pi, qi と比較…

はじめに 基礎技術研究部リサーチ・エンジニアの加藤です。 2023 年 11 月 8, 9 日の 2 日間に亘って開催された CODE BLUE 2023 に参加しました。 本記事では、私が聴講した講演の中から特に興味を惹かれた「シンボリック実行とテイント解析による WDM ドライバーの脆弱性ハンティングの強化」を紹介します。この講演は発表者の Zeze Lin 氏によってスライドが公開されているため、そちらもご参照ください。 この発表で扱われたツールは "IOCTLance" と呼ばれ、検証に使われたドライバーのデータセットなどと共にソースコードが GitHub で公開されています。本記事で…

お近づきになりたい人向けシリーズです。 いろいろなトピックを詰め込みましたが、「これら全部を知らないといけない」のようなつもりではなく、いろいろなことを知るきっかけになったらいいなという気持ちなので、あまり身構えずにちょっとずつ読んでもらえたらうれしい気がします。 まえがき 予備知識 規格 用語 精度という語について 記法 表現について 有限値の表現について エンコードについて 丸めについて よくある誤差や勘違いの例 0.1 = 1 / 10? 0.1 + 0.2 = 0.3? 整数の誤差 Rump’s Example 基本的な誤差評価 用語に関して 実数の丸め 有理数の丸め 基本演算の丸め …

この記事について 差分更新型ビームサーチライブラリの実装例について説明します。 差分更新型のビームサーチについては 高速なビームサーチが欲しい!!! などで既に解説されているため、被る部分については詳しく説明しません。 この記事に書いたソースコードをプログラミングコンテストで自由に使っていただいて構いませんが、当ブログは損害などに対する責任を負いかねますのでご了承ください。 前提知識 木に関する用語 深さ優先探索 C++の基本文法 差分更新型のビームサーチとは 木上のビームサーチ、Euler Tour ビームサーチとも呼ばれています1。 ビームサーチは、幅優先探索に枝刈りを取り入れた手法です。…

AtCoderに挑戦しています。その関係でアルゴリズムを勉強しています。グラフについての勉強内容をメモ書きします。 グラフ グラフのアルゴリズム AtCoderから問題を抜粋 グラフ理論 グラフ 丸と棒で関係を表すのがグラフです。丸と棒は、頂点と辺やノードとエッジなどとも言います。関係を可視化できるのが利点です。 総当りのリーグ戦、電車の路線図、ネットワーク、相関図などがグラフの例です。グラフの応用範囲は広いです。グラフは、配列で扱います。 グラフのアルゴリズム 幅優先探索(BFS:Breadth First Search) キュー 深さ優先探索(DFS:Depth First Search)…