考え方 回答例 考え方止まるマスと訪れたマスを別に管理してBFSをする．回答例 from collections import deque N, M = map(int, input().split()) S = [input() for _ in range(N)] seen = [[False]*M for _ in range(N)] stop = [[False]*M for _ in range(…

考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…

解法1 考え方 回答例 解法2：BFS 考え方 回答例 解法1考え方頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる． 求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．回答例 N, M = map(int, input().…

考え方 回答例 考え方ある文字列$S$に関する良いパス$A$がわかっていたとすると，そのパスの最後の頂点から隣の頂点に遷移してできたパス$A^{\prime}$は対応する文字列$S^{\prime}$に関する良いパス（の候補）である．よって，BFSで見ていけば良さそう． 最…

考え方 回答例 考え方答え（$S$）で二分探索（$O(\log \cdots)$）する．$S$を決めれば辺を$O(N^{2})$で張れる．スタート地点（$N$通り）を決めれば，BFS（$O(N^{2})$）で全ての頂点に行けるかどうかを計算できる．回答例すでに訪れた頂点はリストではなくset…

考え方 回答例 考え方入力例として， 3 3 1 2 2 3 3 1を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．すでに頂点をつないだかどうかはsetで管理すれば良い．回答例スタックを使えばDFSになり，キューを使えばBFSになる．…

考え方 回答例 考え方制約から 距離0：1コ 距離1：1×3コ 距離2：1×3×3コ 距離3：1×3×3×3コ で，各クエリに対して40コ調べれば良いから，言われたとおり計算するだけでよい．回答例訪れた頂点の管理をするために全頂点の配列を用意するとTLEする（各頂点への…

単一始点 BFS ダイクストラ法 01BFS 単一始点ある頂点からの最短距離を求めたい場合．負の辺がないとする．未確定頂点のうち，最短距離のものは確定できる（他の頂点からの更新で小さくなりえない）．つまり，最短距離の未確定頂点の集合を取り出せるデータ…

ABC246E - Bishop 2 - 競プロはじめましたの類題． 考え方 回答例 考え方最短経路問題 - 競プロはじめました コストゼロで行けるものを優先してみればBFSで解ける． キューからpopしたものから更新される頂点はコスト＋1される．コストゼロで到達できる頂点…

【参考】最短経路問題 - 競プロはじめました 方法1 考え方 回答例 方法2 考え方 回答例 参考 方法1考え方ダイクストラ法と同じように，最短距離が未確定の頂点のうち，最小のものから確定させて更新すれば良さそう．1マスずつ動かす問題に帰着するにはどうす…

考え方 回答例 考え方 「重みなし」グラフの最短経路を求める問題になる→BFS 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる 回答例 from collections import deque a, N = map(int, input().split()) q = deque() q.append(1) dist = [-1]…