ABC131(A~D)
A - Security
https://atcoder.jp/contests/abc131/tasks/abc131_a
かかった時間 2分
実行時間 26ms
S=str(input()) for i in range(len(S)-1): if S[i]==S[i+1]: print("Bad") exit() print("Good")
B - Bite Eating
https://atcoder.jp/contests/abc131/tasks/abc131_b
かかった時間 10分
実行時間 119ms
import numpy as np N,L=map(int,input().split()) A=[] for i in range(1,N+1): num=L+i-1 A.append(num) B=[] for i in range(len(A)): s=sum(A)-A[i] B.append(s) index=np.abs(np.asarray(B)-sum(A)).argmin() print(B[index])
C - Anti-Division
https://atcoder.jp/contests/abc131/tasks/abc131_c
かかった時間 50分
実行時間 23ms
import math A,B,C,D=map(int,input().split()) num=B-A+1 def lcm(x, y): return (x * y) // math.gcd(x, y) k=lcm(C,D) y1=B//D y2=(A-1)//D sum1=y1-y2 x1=B//C x2=(A-1)//C sum2=x1-x2 z1=B//k z2=(A-1)//k sum3=z1-z2 sums=(sum1+sum2)-sum3 print(num-sums)
公倍数の所を(C+D)としていて、気づくまでに時間がかかってしましました。
考え方としては、まずBの範囲にあるCとD、CとDの最小公倍数の約数の個数を求めます。(y1,x1,z1)
同じく、A未満にある約数の個数も求める。(y2,x2,z2)
それらの、(y1-y2)とするとA~Bの範囲内にあるC,Dの約数の個数が求められる。
それから、CとDの最小公倍数の約数の個数を引けば重複している値を除いたA~Bの範囲内にあるC,Dの約数の個数がわかる。
あとは、A~Bの範囲内にある整数の個数と上記で求めたC,Dの約数の個数を引けば答えになる。
D - Megalomania
https://atcoder.jp/contests/abc131/tasks/abc131_d
かかった時間 10分
実行時間 930ms
from heapq import heappop,heapify N=int(input()) g=[] time=0 for i in range(N): A,B=map(int,input().split()) g.append([B,A]) heapify(g) while g: b,a=heappop(g) time+=a if time>b: print("No") exit() print("Yes")
heapqを使って締め切りが近い順に処理していけばいい
JavaScriptのみでアプリを作ってみた
フレームワークをつかわずにhtml,css,javascriptのみでアプリを作ってみました。
一つ目のアプリ:Todoアプリ
https://matsudasan.github.io/Todo-js-/
リポジトリ：https://github.com/matsudasan/Todo-js-
とりあえず、基本となるTodoアプリを作りました。
Reactと違って勝手にレンダリングされることがないので、ボタンを押したタイミングで一旦tasklistの中身を全部消してループでtasksの要素を描写しています。
2つ目のアプリ：カレンダー表示アプリ
https://matsudasan.github.io/Calender-js-/
レポジトリ：https://github.com/matsudasan/Calender-js-
難しかった所は末日の空白をどうするかということでした。最終的にはcountが末日の日数を超えていることを前提に、jが0つまり月曜日ならその週は描写する必要がないのでbreakし、月曜日以外なら7-jで残りの曜日の数だけ空白を用意することにしました。
クラスカル法
今回はクラスカル法をやっていきます。
使用する問題は以下になります。
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 _ in range(V)]#隣接リスト visit=[False]*(V)#頂点を訪れたか visit[0]=True#頂点0から始めるのでそこは訪れていることにする for i in range(E): s,t,w=map(int,input().split()) Graph[s].append([w,t])#sからtに行くコスト Graph[t].append([w,s])#今回は無向グラフなのでtからsに行くことも可能 que=[i for i in Graph[0]]#キュー heapify(que)#リストを優先度付きキューに変換 ans=0#答え
今回はheapqを使っています。
最小全域木を求めるのでコストが小さい辺を通っていくことが最善のため。
個人的にheapqでわからないことがあるのですが、
[[1, 3], [3, 2], [7, 3], [3, 4], [6, 5]] 実際はこうなる [[1,3],[3,2],[3,4],[6,5],[7,3]] こうなると思ってた
上記のような並び替えになるんですが、調べて見たらちょっと理解できたので脱線しますが書いておきます。
簡単な例として以下の配列を優先度付きキューに変換したとします
[-1, 0, 1, 2, 3, 4, -10]
そうしたら以下の配列になります
[-10, 0, -1, 2, 3, 4, 1]
私は以下のような配列になるのかなと思ってたんですが違いました
[-10, -1, 0, 1, 2, 3, 4]
公式サイトを見てみとheapq以下の木構造になっていることがわかりました。
https://docs.python.org/ja/3/library/heapq.html
さっきの配列で木構造を作ってみると以下のようになります。
結局上にある数値より下の数値が大きくなればいいので以下の配列になっても問題ないということだと思います。
自信はありませんが。
[-10, 0, -1, 2, 3, 4, 1]
一通り調べたのですが2次元配列の場合は乗っていませんでした。おそらく各配列の1番目の値で並び替えているとおもいます。(多分)
なので、1番目の値に各辺のコストを入れることによって、最小全域木を求めることができる。
続いて処理をかいていきます。
while que: c,v= heappop(que)#次に訪れる頂点とそこにいくためのコスト if visit[v]:#すでに訪れていたら処理を飛ばす continue visit[v]=True#訪れたらTrue ans+=c#答えにコストを足していく for e,t in Graph[v]:#頂点vに隣接する頂点にいく if visit[t]:#すでに訪れていたら処理を飛ばす continue heappush(que,[e,t])#訪れる場合キューに追加 print(ans)
最小全域木を求める場合各頂点は1回しか訪れないのでvisitで訪れたか判断します。
heapqを使っているので辺のコストが低い順に訪れるようになっている。
コード全体
from heapq import heappush,heappop,heapify V,E=map(int,input().split()) Graph=[[] for _ in range(V)]#隣接リスト visit=[False]*(V)#頂点を訪れたか visit[0]=True#頂点0から始めるのでそこは訪れていることにする for i in range(E): s,t,w=map(int,input().split()) Graph[s].append([w,t])#sからtに行くコスト Graph[t].append([w,s])#今回は無向グラフなのでtからsに行くことも可能 que=[i for i in Graph[0]]#キュー heapify(que)#リストを優先度付きキューに変換 ans=0#答え while que: c,v= heappop(que)#次に訪れる頂点とそこにいくためのコスト if visit[v]:#すでに訪れていたら処理を飛ばす continue visit[v]=True#訪れたらTrue ans+=c#答えにコストを足していく for e,t in Graph[v]:#頂点vに隣接する頂点にいく if visit[t]:#すでに訪れていたら処理を飛ばす continue heappush(que,[e,t])#訪れる場合キューに追加 print(ans)
参考記事
https://tjkendev.github.io/procon-library/python/graph/min_st_prim.html
ワーシャルフロイド法
今回はワーシャルフロイド法をやっていきます。
使用する問題は以下になります。
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)]#隣接行列 for i in range(E): s,t,d=map(int,input().split()) dp[s][t]=d#sからtにいく辺のコスト dp[s][s]=0#始点のコストは0
ここでは動的計画法を使っています。
今回のように各辺の情報をまとめたリストを隣接行列をいうらしいです。
続いて処理部分を書いていきます。
for k in range(V):#経由する頂点 for i in range(V):#始点 for j in range(V):#終点 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) print(dp,k,i,j) for i in range(V):#負の閉路を検出 if dp[i][i]<0: print("NEGATIVE CYCLE") exit()
例えば頂点0から頂点2にいく通り方は2種類ある。
パターン1:0-2
パターン2:0-1-2
パターン3:0-3-2
パターン1は入力で重みが与えられているので5と入力されている。
パターン2では頂点1を経由しているので式は、dp[0][2]=min(dp[0][2],dp[0][1]+dp[1][2])となる。
頂点を経由する場合は0-1と1-2のように分けてコストを出す。
パターン3は0-3に辺はないのでコストはINFとなる。
このように各頂点を経由する場合を考え、それらの中でコストが１番低い所を通ることになる。
この処理を各頂点に行う。
負の閉路を検出はdp[i][i]が負の値かによってあるかないかがわかる。
そもそも、始点から始点の距離は0になるはずなので、負の値になるはずがない。
コード全体
V,E=map(int,input().split()) INF=10**10 dp=[[INF]*V for _ in range(V)]#隣接行列 for i in range(E): s,t,d=map(int,input().split()) dp[s][t]=d#sからtにいく辺のコスト dp[s][s]=0#始点のコストは0 for k in range(V):#経由する頂点 for i in range(V):#始点 for j in range(V):#終点 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) for i in range(V):#負の閉路を検出 if dp[i][i]<0: print("NEGATIVE CYCLE") exit() for i in dp: s=" ".join(["INF" if n==INF else str(n) for n in i]) print(s)
参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75
ベルマン・フォード法
今回はベルマン・フォード法をやっていきます。
使用する問題は下記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().split())) for _ in range(E)] dist=[INF]*(V) dist[r]=0#始点は0
ダイクストラ法とあまり変わらないです。
処理部分を書いていきます
for i in range(V): for s,t,d in Graph: if dist[s]+d<dist[t]:#最短距離を更新するかどうか dist[t]=dist[s]+d#最短距離を更新 if i==V-1:#負の閉路を検出 print("NEGATIVE CYCLE") exit()
ベルマン・フォード法を使うメリットは負の閉路を検出できることにあるので、そこの処理の解説をしていきます。
今回の問題の入力例2で負の閉路があるのでそれを使います。
まず図に表わすと以下のようになります。
入力例2では1-2-3と通ることでどんどん最短距離を更新をしてしましい、ここに負の閉路があることがわかる。
なので、負の閉路を検出する方法としてv-1以上ループするならそれは負の閉路と判断されます。
なぜなら、始点から各頂点を訪れるためのに通る辺の数はv-1となるため。
始点を除いた頂点の数はv-1となります。そこをすべて訪れる辺の数もv-1となります。
それ以上ループすると負の閉路が存在することになり、永遠に処理がおわりません。
説明が下手でごめんなさい。
コード全体
INF=10**9 V,E,r=map(int,input().split()) Graph=[list(map(int,input().split())) for _ in range(E)] dist=[INF]*(V) dist[r]=0 for i in range(V): for s,t,d in Graph: if dist[s]+d<dist[t]:#最短距離を更新するかどうか dist[t]=dist[s]+d#最短距離を更新 if i==V-1:#負の閉路を検出 print("NEGATIVE CYCLE") exit() for i in dist: if i==INF: print("INF") else: print(i)
参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%99%E3%83%AB%E3%83%9E%E3%83%B3%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E6%B3%95
https://wakabame.hatenablog.com/entry/2017/09/06/221400
http://nishiharayuugo.blog.fc2.com/blog-entry-14.html
ダイクストラ法
今回はダイクストラ法をやっていきます。
まず、ダイクストラ法の説明については下記動画がとてもわかりやすいです。
https://youtu.be/X1AsMlJdiok
ちなみにダイクストラ法では負の辺があるとき使えません。
負の辺があるときはベルマン・フォード法を使いましょう。
負の辺があるときにダイクストラ法を使うと負の閉路がある場合があるので、ループし続けてしまうため、処理が終わりません。
入力は以下が与えられるとします
4 5 頂点の数、辺の数 0 1 2 頂点、隣接する頂点、辺の重み 0 2 4 1 2 1 1 3 3 2 3 1
図で表わすと以下のようになります
ではコードを書いていきます
from heapq import heappush, heappop,heapify INF=10**9 V,E=map(int,input().split()) Graph=[[] for _ in range(V)] dist=[INF]*(V)#とりあえず大きな数値を入れておく dist[0]=0#頂点0から始めるので頂点0にいくコストは0 priority_queue=[[0,0]] #現在のdist,今いる頂点 heapify(priority_queue)#優先度付きキューに変換 for i in range(E): s,t,d=map(int,input().split()) Graph[s].append([t,d])
今回はheapqというライブラリを使っています。
使い方は下記記事を参考にしました。
https://qiita.com/ell/items/fe52a9eb9499b7060ed6
処理の部分を書いていきます
while priority_queue: print(priority_queue) v=heappop(priority_queue)[1]#先頭の要素を取り出し、削除 for j,k in Graph[v]:#頂点vと隣接する頂点を訪れる if dist[v]+k<dist[j]:#隣接する頂点jの最もコストが低い所に行く dist[j]=dist[v]+k#頂点jに行くコスト heappush(priority_queue,[dist[j],j])#最短距離を更新したら、その頂点へのコスト、頂点をキューに追加
BFSと似たようなコードになっています。
キューがなくなるまで繰り返します。
if文は例えば頂点2に行くルートが今回の場合頂点0-1-2と頂点0-2の2パターンがあります。
頂点0-2のパターンは頂点2に行くコストは4となります。
頂点0-1-2のパターンは3となり、上記のパターンよりコストが小さくなるので3に上書きします。
優先度付きキューなのでキューに要素を挿入したら、ヒープ内の他の要素はそれにあわせて調整されるようになっているそうです。
コード全体
from heapq import heappush, heappop,heapify INF=10**9 V,E=map(int,input().split()) Graph=[[] for _ in range(V)] dist=[INF]*(V)#とりあえず大きな数値を入れておく dist[0]=0#頂点0から始めるので頂点0にいくコストは0 priority_queue=[[0,0]] #現在のdist,今いる頂点 heapify(priority_queue)#優先度付きキューに変換 for i in range(E): s,t,d=map(int,input().split()) Graph[s].append([t,d]) while priority_queue: v=heappop(priority_queue)[1]#先頭の要素を取り出し、削除 for j,k in Graph[v]:#頂点vと隣接する頂点を訪れる if dist[v]+k<dist[j]:#隣接する頂点jに最もコストが低い所を通って行く dist[j]=dist[v]+k#頂点jに行くコスト heappush(priority_queue,[dist[j],j])#最短距離を更新したら、その頂点へのコスト、頂点をキューに追加 print(dist)
参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95
https://mirucacule.hatenablog.com/entry/2020/05/21/124026
幅優先探索(BFS)
今回は幅優先探索(BFS)をやっていきます。
幅優先探索は各頂点への最短経路を求めることのできるアルゴリズムですが、辺に移動距離や時間などを考慮しないため、使う際は注意が必要。
今回は以下のグラフを使います。
頂点が8個、辺が8個のグラフです。
なので入力は以下のようになります
8 8 頂点の数、辺の数 0 1 頂点、隣接する頂点 0 2 1 3 1 4 2 4 2 5 4 6 4 7
まず、基本の処理から書いていきます。
from collections import deque N,M=map(int,input().split()) Graph=[[] for _ in range(N)] for i in range(M): #隣接リストを作成 a,b=map(int,input().split()) Graph[a].append(b) Graph[b].append(a) dist=[-1]*(N) #頂点を訪問したか 初期値は全部未訪問 dist[0]=0 #頂点0から頂点0の距離は0 queue=deque() #キューを作成 queue.append(0) #頂点0から始める
dequeの使い方は下記サイトを参考にしました
https://note.nkmk.me/python-collections-deque/
今回は先頭の要素の削除、リストへの追加しか行わないのでdequeを使った方が効率が良いらしい。
普通にリストを書くことも可能。
distの役割は距離の格納と、訪問済みかの判断
値が-1なら未訪問で、それ以外なら頂点0からの距離が入っているので訪問済みと判断できる。
次に処理の部分を書いていきます
while queue: #キューが空になるまで v=queue.popleft() #キューから先頭要素を削除し、取り出す for i in Graph[v]:#頂点vの隣接する頂点をすべて調べる if dist[i] !=-1:#探索済みならスルー continue dist[i]=dist[v]+1 #隣接する頂点の距離は、現在の距離+1となる queue.append(i) #キューに次に調べる頂点を追加
dist[i]=dist[v]+1は、現在の頂点から隣接する頂点に行くための距離は辺がつながっているので必ず+1の距離で行くことができる。
例えば、頂点0から隣接する頂点1,2は頂点0から+1の距離で行くことができる。
なので、distの値はdist=[0,1,1]となる。
さらに、頂点1から隣接する頂点0,3,4は頂点1から+1の距離で行くことができるので現在の1に+1を足した2の距離で行くことができる。ただし、頂点0は探索済みなのでスルーする。
なので、distの値はdist=[0,1,1,2,2]となる。
このように距離が変化していく。
コード全体
from collections import deque N,M=map(int,input().split()) Graph=[[] for _ in range(N)] for i in range(M): #隣接リストを作成 a,b=map(int,input().split()) Graph[a].append(b) Graph[b].append(a) dist=[-1]*(N) #頂点を訪問したか 初期値は全部未訪問 dist[0]=0 #頂点0から頂点0の距離は0 queue=deque() #キューを作成 queue.append(0) #頂点0から始める while queue: #キューが空になるまで v=queue.popleft() #キューから先頭要素を削除し、取り出す for i in Graph[v]:#頂点vの隣接する頂点をすべて調べる if dist[i] !=-1:#探索済みならスルー continue dist[i]=dist[v]+1 #隣接する頂点の距離は、現在の距離+1となる queue.append(i) #キューに次に調べる頂点を追加 for j in range(N): print(j,dist[j])
結果は以下の画像のようになる。
参考記事
https://qiita.com/drken/items/996d80bcae64649a6580
キューがどのように変化していくかについては参考記事にわかりやすく書いてあるためそちらを見るのがおすすめ。
