深さ優先探索

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さんの返答なんで、アプデ前のだとどう返ってくるかは知らん。 あと、このコードに対して、分かりやすく解説して！って投げたら、解説してくれました笑 流石！ …

深さ優先探索はグラフ探索アルゴリズムの一種であり、木構造やグラフ構造の探索に広く使われています。深さ優先探索では、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には、一つ前のノードに戻り、別の子ノードを探索していくという方法を繰り返していきます。以下では、Pythonで深さ優先探索を実装する手順を説明します。 深さ優先探索とは 深さ優先探索（Depth-First Search, DFS）とは、グラフ探索アルゴリズムの一つであり、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には…

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

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

いきなりですがタイトル詐欺です. 正しくは「私にとって深さ優先探索はなぜ難しいのか」です. この記事を書こうと思ったきっかけですが、DFSの問題を解くときにDFSで解けると分かっていても実装が出来ないということを何度か体験したからです. なので時間をかけてDFSを実装してみたところ、（私にとって）DFSが難しい要因は問題の多様性ではなく、実装の多様性が原因ではないかという結論に至りました. 以下ではDFSを実装するにあたりどのような選択肢があり、私はこれを使って実装するぞ、ということをまとめていきます. 以下ではAtCoder Typical Contest 001-A のように、迷路が与えら…

Goのトップレベルで定義したエラー変数の命名規則をチェックするリンターを作ってみた トップレベルで宣言されたエラーの名前を正規表現でチェックするtomato3713/go-varErrChecker というカスタムリンターを作成しました。 Go言語ではカスタムエラーを定義するときにトップレベルでErrorインターフェイスを満たす変数を定義し、その変数を返すということを行います。 コードで書くと次のようになります。ErrOccuredSomething のような変数の名前が命名規則に従っているかをチェックするリンターです。 var ErrOccuredSomething = fmt.Errorf…

note.com {Script: ## Efficient Prompt Construction: Navigating the PCT Strategy ## This prompt by @LucasChatGPT / CC BY-NC 4.0 As a Prompt Creator, your primary responsibility is to weave complex ideas into a clear, actionable AI prompt. For example, if your high-level objective is "Creating a guide…

アルゴリズムとデータ構造にもう少し強くなりたく「アルゴリズム実技検定」という資格の公式テキストを読んでみました。 book.mynavi.jp 競技プログラミングで有名なAtCoderの会社が運営してる資格試験らしいです。資格を取る気は現状ないですが教材としてはよかった。 アルゴリズム実技検定に始まってサンプルコードに使われているPythonの紹介が入りその後、サンプル問題を解きながら競技プログラミングのテクニックを学んでいく構成です。 サンプルコードは個人的には静的型付け言語の方が読みやすいと思うんでPythonだと複雑なデータ構造になった時たまに辛く感じることは正直あったりもしましたが解説…

深さ優先探索とは グラフにおいて、いけるところまで深くいき、いけなくなったら引き返してまた同じことをする探索を深さ優先探索という。 実装 実装方法として再帰関数を用いる方法とstackを用いる方法がある。 再帰関数を使う方法は逃げてなのでstackでやるようにしている。 let mut q = vec![]; q.push(s); let mut used = vec![vec![false; w]; h]; while let Some((x, y)) = q.pop() { for &(dx, dy) in [(1, 0), (0, 1), (!0, 0), (0, !0)].iter()…

はじめに G検定の試験対策として、「人工知能は人間を超えるか」を読んだ。 人工知能とは 人工知能の定義 人工知能の定義は明確に定まっていないが、本の筆者は「人工的に作られた人間のような知能」と定義している。 単純な制御を行うプログラムであっても「人工知能」と称してしまえばそれは人工知能である。 人工知能ブームはこれまでに3度到来しており、現在は第3次AIブームの真っ只中である。 それまでには技術的な問題によって冬の時代を越してきた。 第1次AIブーム 第1次AIブームは1950年代後半～1960年代である。 この時代は「推論・探索」の時代と呼ばれた。 推論とは人間の思考過程を記号によって表現し…

グラフ探索の問題として、人生で最初に解きたい問題！！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられる。 このグラフの連結成分の個数を求めよ。 制約 解法 まず、単純グラフや連結成分という概念についてはこちら！ algo-method.com グラフの入出力の扱い方についても、このページで解説しています。 algo-method.com グラフの連結成分の個数を求めるためには、次の 3 つの方法が代表的です。 DFS BFS Union-Find DFS と BFS については、次の記事群で解説しています。 DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの…

サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）に参加しました。 結果 A,B,C,Dの4問正解でした。 C問題でそこそこ時間を使ったのが痛かった。 E問題はちょっとしか時間が取れなかったから解ききれなかった。 A - 321-like Checker 与えられた数値の各桁が狭義単調減少になっているかどうかを判定する問題。 数値を文字列として受け取って上から1桁目から順番に次の桁の値と比較して判定していった。 charで'0'から'9'のどれかだから上からx桁目とx+1桁目を直接比較しても問題ないと思うし、数値にしたいならcharの値から'…

ブレインパッドは、LLM/Generative AIに関する研究プロジェクトを立ち上げ、この「Platinum Data Blog」を通じてLLM/Generative AIに関するさまざまな情報を発信をしています。現在は、週に1回程度の頻度で、社内で実施している生成AI・LLMに関する論文レビュー会の内容をピックアップのうえ配信しています。 今回は、ツール拡張をテーマに、4つの論文をご紹介します。目次 今回のテーマ Lost in the Middle: How Language Models Use Long Contexts 選定理由 論文概要 どうやって入力コンテキストをどのように使用…

｜最も基本的なデータ構造（配列（Array）、配列の添え字） １．配列（Array） ２．添え字（Indexing） ｜静的配列と動的配列 １．静的配列（Static Array） ２．動的配列（Dynamic Array） ｜スタックとキューの操作 １．スタック（Stack） ２．キュー（Queue） ３．適切な使用例 ｜線形リスト：データの連なりを効率的に管理する １．線形リストの基本構造 ２．線形リストの特徴 ｜単方向リスト：データの順序付けと効率的な操作 １．単方向リストの基本構造 ２．単方向リストの特徴 ３．単方向リストの使用例 ｜両方向リスト：双方向のデータ操作 １．両方向リストの…

トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)に参加しました。 結果 A,B,C,Eの4問正解でした。 D問題は問題文を斜め読みすると難しそうな気がしたので後に回して、Dより簡単そうに見えたE問題から解くことにした。 D問題自体も問題分をちゃんと読むと思ってたより難しくなさそうだった。 A - Leyland Number 指定されたとおりに数値計算する。 指数計算が必要なのでpowを使って楽に解いた。 powを知らなかったならループで頑張ってBをA回掛けたり、AをB回掛けたりすれば解ける。 ループと数値計算がわかっていれば解ける問…

はじめに ABC317のA,B,C,D問題をPython3で解きます。 はじめに A問題: Potions 問題の概要 問題の考察 コード B問題: MissingNo. 問題の概要 問題の考察 コード C問題: Remembering the Days 問題の概要 問題の考察 DFSで解く場合のコード bitDPで解く場合のコード D問題: President 問題の概要 問題の考察 コード A問題: Potions atcoder.jp 問題の概要 個の効き目順に並んだ傷薬があり、番目の傷薬を使うと体力がだけ増加する。現体力がで傷薬を1つ使って体力を以上するとき、その条件を満たす最も効き目…

はじめに はじめまして．ふかだ（@towardbluesky）と申します． 2023年7月8日と9日に実施された編入試験で大阪大学基礎工学部 情報科学科 ソフトウェア科学コースに合格したので，体験記を書きます！ はじめに 自己紹介 勉強内容 英語（TOEIC） 数学 物理 過去問 面接・口頭試問 出願情報 試験の内容 英語（TOIEC） 数学（120分） 物理（90分） 面接・口頭試問 どうして合格できたのか 伝えたいこと 余談 自己紹介 名前：ふかだ 出身：N高専情報科 席次：1年生1位，2年生2位，3年生1位，4年生1位 受験年度：2024年度（令和6年度） 併願校：広島大学情報科学部，京…