しゃくとり法に関しては下記URLのスライド55ページ～を参考にどうぞ https://www.slideshare.net/yuki2006_debel/21-35882983ポイントとしては条件に一致するまでrightを動かしていき、処理が終わったらleftを動かす。この時rightの値はそのままにする。問題…

今回はクラスカル法をやっていきます。使用する問題は以下になります。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jaまず、入力から from heapq import heappush,heappop,heapify V,E=map(int,input().split()) Graph=[[] for…

今回はワーシャルフロイド法をやっていきます。 使用する問題は以下になります。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jaまず、入力から V,E=map(int,input().split()) INF=10**10 dp=[[INF]*V for _ in range(V)]#隣接…

今回はベルマン・フォード法をやっていきます。使用する問題は下記URLのものを使います。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jaまず、入力から INF=10**9 V,E,r=map(int,input().split()) Graph=[list(map(int,input()…

今回はダイクストラ法をやっていきます。 まず、ダイクストラ法の説明については下記動画がとてもわかりやすいです。 https://youtu.be/X1AsMlJdiokちなみにダイクストラ法では負の辺があるとき使えません。 負の辺があるときはベルマン・フォード法を使いま…

今回は幅優先探索(BFS)をやっていきます。 幅優先探索は各頂点への最短経路を求めることのできるアルゴリズムですが、辺に移動距離や時間などを考慮しないため、使う際は注意が必要。 今回は以下のグラフを使います。 頂点が8個、辺が8個のグラフです。 なの…

今回は深さ優先探索(DFS)をやっていきます。 問題は下記URLのを使います http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja n=int(input()) Graph=[list(map(int, input().split())) for _ in range(n)] start=[0]*(n)#頂点の発…

今回は二分木探索をやっていきます。 以下の記事で使ったことがあるので、その問題で今回はやっていきます。 コードもそこから流用します。 nasubifx.hatenablog.com問題URL https://atcoder.jp/contests/abc146/tasks/abc146_c二分木探索を使う場合は全探索…

今回で動的計画法(DP)の最後です bitdpを使うと全探索がn 今回は以下の問題を使用します。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja 有名な巡回セールスマン問題(TSP)ですね。 V,E=map(int, input().split()) #でかい値な…

今回は区間DPをやっていきます。 理解するまでに時間がかかりましたが、理解できればなるほどと思いました。 例題は以下の問題でやっていきます。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp とりあえず、 4 1 2 3 4与えられる…

今回からAtCoderのD問題を解くためにアルゴリズムの勉強を始めます。https://atcoder.jp/contests/abc032/tasks/abc032_d 上記の例でナップサックDPを使っていきます。 以下は上記の例の入力例1の場合で書いていきます。 N,W=map(int,input().split()) value…