今回はダイクストラ法をやっていきます。 まず、ダイクストラ法の説明については下記動画がとてもわかりやすいです。 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…

まず、以下が完成品です https://matsudasan.github.io/Trello/使ったライブラリはreact-beautiful-dndです。 https://github.com/atlassian/react-beautiful-dnd最初はreact-dndを使っていたんですが、react-beautiful-dndのサンプルにTrelloに似ているもの…

A - Fifty-Fifty https://atcoder.jp/contests/abc132/tasks/abc132_a かかった時間 8分 実行時間 30ms import collections S=list(str(input())) num=collections.Counter(S) for i,j in num.items(): if j!=2: print("No") exit() print("Yes") B - Ordina…

A - T or T https://atcoder.jp/contests/abc133/tasks/abc133_a かかった時間 1分 実行時間 24ms N,A,B=map(int,input().split()) print(min(N*A,B)) B - Good Distance https://atcoder.jp/contests/abc133/tasks/abc133_b かかった時間 30分 実行時間 185…

エディタを作るにあたりreact-aceを使いました。 https://github.com/securingsincity/react-ace完成品 https://matsudasan.github.io/HTMLEditor/本当はリサイズ可能にしたかったんですが、やり方がわかりませんでした。 次は、paiza.ioのようなオンライン…

A - Dodecagon https://atcoder.jp/contests/abc134/tasks/abc134_a かかった時間 1分 実行時間 25ms r=int(input()) print(3*r**2) B - Golden Apple https://atcoder.jp/contests/abc134/tasks/abc134_b かかった時間 15分 実行時間 27ms N,D=map(int,inpu…

A - Harmony https://atcoder.jp/contests/abc135/tasks/abc135_a かかった時間 12分 実行時間 24ms A,B=map(int,input().split()) if (A+B)%2==0: print(int((A+B)/2)) else: print("IMPOSSIBLE") 入力例を見た感じAとBを足して2で割ったら答えになり、それ…