幅優先探索

atcoder.jp・参考： www.youtube.com・考え方：bfsで解く。1から行ける頂点の距離をdist1、N1+N2から行ける頂点の距離をdist2とする。あとはそれぞれのmaxを取って+1したのが最大の距離になる。 from collections import deque #入力 n1,n2,m=map(int, input().split()) n=n1+n2 g=[[]for _ in range(n)] for _ in range(m): a,b=map(int, input().split()) a-=1 b-=1 g[a].append(b) g[b].appen…

・問題： atcoder.jp・参考： Submission #16162979 - AtCoder Regular Contest 005 AtCoder ARC 005 C - 器物損壊！高橋君 (0-1 BFS) (水色) - けんちょんの競プロ精進記録・0-1BFS： 01-BFSのちょっと丁寧な解説 - ARMERIA・ダイクストラ法： グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube・0-1BFSを使う。壁の有無で0，1を重さとしてBFSするものをいう。ダイクストラ法の重さが0，1になったもので、0のときはdequeの左から入れて1のときは右から入れる。こうすると0の…

・問題 atcoder.jp ・参考 AtCoder AGC 033 A - Darker and Darker (緑色, 300 点) - けんちょんの競プロ精進記録 ・考えたこと：DFSかBFSを使うことは分かったが具体的なやり方は思いつかなかった。上の記事を参考にして、スタートを'#'としてbfsをする。'#'からの距離distが最大のものが答えとすれば良いということが分かった。・注意点：pypyで提出してください。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in ran…

・問題： atcoder.jp ・参考文献： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita ・説明：幅優先探索を使ってとく。詳しくは参考文献を参照。プログラムの説明は'#'の数(kabe)とスタートを含むゴールまでの最短距離(dist[gx][gy]+1)を全体(H*W)から引いた値になる。これを素直に実装すればよい。 ・実装例： from collections import deque H,W=map(int,input().split()) field=[] for _ in range(H): field.append(list(input())) sx=0…

・問題 atcoder.jp・参考： スタックとキューを極める！ 〜 考え方と使い所を特集 〜 - Qiita・注意点：参考文献を見れば基本大丈夫だが、スタートとゴールの座標をマイナス1する必要がある。(sx-=1,,,のように)・実装： from collections import deque H,W=map(int,input().split()) sx,sy=map(int,input().split()) gx,gy=map(int,input().split()) #1つ下げる sx-=1 sy-=1 gx-=1 gy-=1 field=[] for _ in range(H): …

・参考： BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita・内容：上の記事を参考にpythonでBFSを書いた。queueはcollectionsのdequeのほうが早いらしい。dequeはque=deque() #que.append(i)でappend,que.popleft()で左を取り出してキューから左の要素が消える。 queueはque=queue.Queue() #que.put(i),que.get()で同じことができる。・実装：頂点0からの距離distを求めるもの。 from collections import deque import q…

幅優先探索は、グラフや木構造などのデータ構造で、あるノードから開始して、そのノードから近いノードを順に探索するアルゴリズムです。これは、最短経路を求める問題などに使われます。以下に、Pythonで幅優先探索を実装する手順と具体例を示します。 幅優先探索のアルゴリズム 幅優先探索は、幅優先探索木を作成することによって実装されます。幅優先探索木は、始点ノードからの距離に基づいて、ノードをレベルごとに分類した木構造です。以下に、幅優先探索のアルゴリズムを示します。 始点ノードをキューに入れる。 キューからノードを取り出す。 取り出したノードが目的のノードかどうかを調べる。 取り出したノードから伸びる…

問題. Turning Red 個のライトと 個のボタンがある。ライトは赤、緑、青の三色のいずれかで点灯する。ライトの色を変えることができるボタンを1回押すと、赤は緑に、緑は青に、青は赤に色を変える。 各ボタンに対して、そのボタンを押すと同時に色が変わるライトのリストが与えられる。ただし、各ライトに対して、そのライトの色を変えることができるボタンの数は高々 2 個である。また、あるライトの色を変えるボタンが与えられない場合もある。初めに各ライトの色が与えられる。すべてのライトの色が赤色になるようなボタンの押し方で、押したボタンの回数の総和の最小値を答えよ。ただし、そのような押し方が無い場合は …

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

BFSとは? 到達可能かの判定 例題1(ゴールできる場合) 例題2(ゴールできない場合) C++での実装 BFSとは? 幅優先探索と呼ばれる経路探索のアルゴリズムです。 詳細は以下の記事などを参考にしてください。 BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 #AtCoder - Qiita 到達可能かの判定 スタートからゴールまで到達できるかを判定するだけで、最短などを考慮しない場合です。 今回は斜め移動は不可能とします。 例題1(ゴールできる場合) 以下のグリッドを例に挙げて説明します。 〇は進行可能で、×は進行不可を示します。 また、各グリッドの状態を次の4色で示…

本日は4/7(日)のAtCoder ABC348を振り返る。 結果 ABCまでの3完で、パフォーマンスは396。45分程度でCまでACできたが、D問題を解くための知識を持っておらず3完で終了した。 これを受けて思うのは、前回(ABC347)ではAB2完だったのだがパフォ385で、今回とは「C問題を解けなかった」という大きな差があるにも関わらずパフォーマンスに10程度しか差がない。 自分の直感では解いた問題数によってパフォーマンスが階段式に変わるのかと思っていたが、こちらの記事を読むに「参加者全員に対する順位」が参照されている模様？ なるほど、であれば前回と今回で順位に大きな差がないため、パフォ…

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

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

文書の一覧 JTC1/SC22/WG21 - Papers 2024 mailing2024-01 全部で22本あります。 もくじ P1255R11 A view of 0 or 1 elements: views::maybe P1255R12 A view of 0 or 1 elements: views::maybe P1709R5 Graph Library P2019R5 Thread attributes P2527R3 std::variant_alternative_index and std::tuple_element_index P2664R6 Proposal to …

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

2024/02/09 から 2024/02/19 までの期間に開催された THIRD プログラミングコンテスト (AHC 030) に参加した。 この記事では今回の参加について振り返る。 問題概要 https://atcoder.jp/contests/ahc030/tasks/ahc030_a N x N マスの盤面に M 個の油田がある。 このとき、油田のあるマスを全て特定せよという問題。 油田の大きさと形は事前に全てわかっている。 油田は重なって配置されることもあり、その場合油田が重なっているマスは重なっている数と同じだけの埋蔵量があるとみなす。 問題例 (seed=1) 緑枠で囲まれた…

BFSは幅優先探索と言って、まあだいたいグラフが連結かどうかだったり、ある頂点から初めてその頂点には何通りの行き方があるかとか、最小で何手である頂点からある頂点まで行けるかを確かめたりするのに使います（他にもたくさん使いみちあるけど）。 実装 vector<int> bfs(int n,int m,vector<vector<int>>rotti){ vector<int>amount(n,100000000); amount[0]=0; vector<int>stack={1}; int iti=0,hako; set<int>irane; irane.insert(1); while (s…

問題文 https://atcoder.jp/contests/abc339/tasks/abc339_d 問題概要 $n \times n$ のグリッド状の盤面があり，各セルは空きマスまたは障害物である．また，2 つの駒が盤面の（相異なる）セルに置かれている． 駒たちに対し，以下の操作を適用することができる： 上下左右の方向をひとつ選ぶ． 2 つの駒をその方向に 1 マス移動させる． ただし，盤外に出たり障害物にめり込むような移動を試みた場合は，その場に留まる． 2 つの駒が同じセルに存在するような状態にするために必要な操作回数の最小値はいくらか？ 制約 $2 \leq n \leq 60$