深さ優先探索(DFS)
今回は深さ優先探索(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)#頂点の発見時刻を格納 finish=[0]*(n)#頂点の完了時刻を格納 visit=[False]*(n)#その頂点を訪れたか num=0#現在の時刻
とりあえず、ここまでは入力の部分になります。
肝心の処理を書いていきます
def dfs(vertex): global num num+=1#時刻を進める start[vertex]=num#頂点vertexの発見時刻 visit[vertex]=True#頂点vertexを訪問済みにする for i in Graph[vertex][2:]:#繋がっている頂点を訪れる if(visit[i-1]):#すでに訪れていたらスルー continue dfs(i-1)#再帰的にその頂点に訪れる num+=1#時刻を進める #頂点vertexの完了時刻 finish[vertex]=num if __name__ == "__main__": dfs(0) for i in range(n): print(i+1,start[i],finish[i])
深さ優先探索(DFS)を簡単に説明すると、一本の道を行き止まりまで突き進んで、行き止まりまでいったら分かれ道まで戻ってまた行き止まりまで行くを繰り返すアルゴリズムです。
以下の画像を見ると入力例1はまっすぐなのでいって戻ってくればいいだけ
入力例2のグラフが問題のサイトに乗っているのでそれを見ると深さ優先探索がどのような順番で探索しているのかがわかりやすいと思う。
コード全体
n=int(input()) Graph=[list(map(int, input().split())) for _ in range(n)] start=[0]*(n)#頂点の発見時刻を格納 finish=[0]*(n)#頂点の完了時刻を格納 visit=[False]*(n)#その頂点を訪れたか num=0#現在の時刻 def dfs(vertex): global num num+=1#時刻を進める start[vertex]=num#頂点vertexの発見時刻 visit[vertex]=True#頂点vertexを訪問済みにする for i in Graph[vertex][2:]:#繋がっている頂点を訪れる if(visit[i-1]):#すでに訪れていたらスルー continue dfs(i-1)#再帰的にその頂点に訪れる num+=1#時刻を進める #頂点vertexの完了時刻 finish[vertex]=num if __name__ == "__main__": dfs(0) for i in range(n): print(i+1,start[i],finish[i])
特に難しくはなかったです
二分木探索
今回は二分木探索をやっていきます。
以下の記事で使ったことがあるので、その問題で今回はやっていきます。
コードもそこから流用します。
nasubifx.hatenablog.com
問題URL
https://atcoder.jp/contests/abc146/tasks/abc146_c
二分木探索を使う場合は全探索で間に合わない場面で使います。
今回は範囲は10**9ということで探索で間に合いません。
ここは二分木探索の探索範囲を決定しています。
A,B,X=map(int,input().split()) left=1 right=10**9 ans=0
ここが、二分木探索の処理になります。
while left<=right: mid=(left + right)// 2 #Xより小さい場合に探索範囲を右に変える if A*mid+B*len(str(mid))<=X: ans=mid left=mid+1 #Xより大きい場合に探索範囲を左に変える else: right=mid-1 print(ans)
簡単に二分木探索をしておきます。
まず、大前提として、配列の場合はソートしてある必要があります。
二分木探索は常に中央の値が求めている値と比較して小さいか、大きいかで次の探索範囲を決める。これによって、探索範囲が半分になっていき全探索ではできなかった広い範囲も探索できるようになります。
探索範囲の変え方については画像を見れば分かるとおり、探索範囲を右に変える場合は left=mid+1、探索範囲を左に変えるright=mid-1となっている。
今回の問題は特定の値ではなく、最も大きい整数を求めるのでmidがXより小さいとき、答えの変数に格納midを格納しておきそれをどんどん更新していく形にしている。
二分木探索の終了の条件は画像の通り１つの数値しか残らないのでleft<=rightとしている。
A,B,X=map(int,input().split()) left=1 right=10**9 ans=0 while left<=right: mid=(left + right)// 2 #Xより小さい場合に探索範囲を右に変える if A*mid+B*len(str(mid))<=X: ans=mid left=mid+1 #Xより大きい場合に探索範囲を左に変える else: right=mid-1 print(ans)
bitDP
今回で動的計画法(DP)の最後です
bitdpを使うと全探索がn<=10ぐらいの所をn<=20ぐらいまで探索できるようになるそうです。
今回は以下の問題を使用します。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja
有名な巡回セールスマン問題(TSP)ですね。
V,E=map(int, input().split()) #でかい値ならOK INF=10**10 cost = [[INF]*V for _ in range(V)] for e in range(E): s, t, d = map(int,input().split()) cost[s][t] = d dp = [[-1] * V for _ in range(1<<V)] #スタート位置 dp[0][0] = 0
とりあえず、ここまでは一緒ですね。
dpの作り方が今までと違うのでbitdpの考え方を説明します。
まず、bitdoでの集合の表し方は以下の画像のようになります。
画像では分かりやすいように頂点をa,b,c,dとしています。
これを前提に、入力例1を表で表わすと以下のようになります。
| 集合 | 2進数 | 10進数 |
|---|---|---|
| {} | 0b0000 | 0 |
| {0} | 0b0001 | 1 |
| {1} | 0b0010 | 2 |
| {0,1} | 0b0011 | 3 |
| {2} | 0b0100 | 4 |
| {0,2} | 0b0101 | 5 |
| {1,2} | 0b0110 | 6 |
| {0,1,2} | 0b0111 | 7 |
| {3} | 0b1000 | 8 |
| {0,3} | 0b1001 | 9 |
| {1,3} | 0b1010 | 10 |
| {0,1,3} | 0b1011 | 11 |
| {2,3} | 0b1100 | 12 |
| {0,2,3} | 0b1101 | 13 |
| {1,2,3} | 0b1110 | 14 |
| {0,1,2,3} | 0b1111 | 15 |
dp = [[-1] * V for _ in range(1<<V)]
pythonではrange(stop)ではstopの値は結果に含まれないので数値を1多くしている。
次の処理を書いていきます。
V,E=map(int, input().split()) INF=10**10 cost = [[INF]*V for _ in range(V)] for i in range(E): s, t, d = map(int,input().split()) cost[s][t] = d dp = [[-1] * V for _ in range(1<<V)] def dfs(S,v): if dp[S][v] != -1: # すでに訪れたかどうか return dp[S][v] if S==(1<<V)-1 and v==0: # 全ての頂点を訪れて頂点0に戻ってきた return 0 # もう動く必要はない #初期化 res = INF for u in range(V): if S>>u & 1 == 0: # 未訪問かどうか res = min(res, dfs(S|1<<u, u)+cost[v][u]) dp[S][v] = res return res ans = dfs(0, 0) # 頂点0からスタートする。ただし頂点0は未訪問とする if ans == INF: print(-1) else: print (ans)
上から解説していきます。
def dfs(S,v): if dp[S][v] != -1: return dp[S][v] if S==(1<<V)-1 and v==0: return 0
Sは今いるdpを表し、vは今いる頂点を表します。
1つ目のif文は、今回は-1なら訪問済み、0なら未訪問と扱うので、訪問済みならdpから持ってきます。
2つ目はのif文は全部の頂点を訪れた場合はdp[(1<
#初期化 res = INF for u in range(V): if S>>u & 1 == 0: # 未訪問かどうか res = min(res, dfs(S|1<<u, u)+cost[v][u]) dp[S][v] = res return res
初期化は今回は最短経路を求めるので大きい数値なら何でもよい。
今回使うビット演算子の使い方は画像と通りです。
&ビット演算子は両方1なら1をそれ以外は0を返します。
｜ビット演算子はどちらかが1なら1を返します。
if S>>u & 1 == 0:
このif分はその頂点をすでに訪れているかをチェックします。
訪れていない場合のみ、その頂点に移動します。
例をいくつか挙げると
S=0の場合対応する集合はdp[0]
dp[0]は2進数で0b0000なのですべての頂点は未訪問になる
S=7の場合対応する集合はdp[7]
dp[7]は2進数で0b0111なので頂点3以外訪れている
S=13の場合対応する集合はdp[13]
dp[7]は2進数で0b1101なので頂点1以外訪れている
S=15の場合対応する集合はdp[15]
dp[15]は2進数で0b1111なのですべての頂点を訪れている
さっきの表のとおりに対応しています。
res = min(res, dfs(S|1<<u, u)+cost[v][u])
ここは次に訪れる可能性がある頂点に行く場合のコストを計算して、一番低いコストを取ります。
例をいくつか挙げると
S=0の場合対応する集合はdp[0]。これを2進数で表すと0b0000なので、次に訪れる可能性がある頂点は0,1,2,3のすべてなので、次の遷移は0b0001(dp[1]),0b0010(dp[2]),0b0100(dp[4]),0b1000(dp[8])のどれかになる。結果は、この中で一番コストが低いところに遷移することになる。
S=13の場合対応する集合はdp[13]。これを2進数で表すと0b1101なので、次に訪れる可能性がある頂点は1のみなので、次の遷移は0b1111(dp[15])となる。
これをどんどん行っていき、最終的にすべての頂点を訪れた結果を返す。
ans = dfs(0, 3) if ans == INF: print(-1) else: print (ans) print(dp)
今回の場合適当にスタートする頂点を決めても大丈夫(理由はわかりません)なので
ans = dfs(0, 0)#dfs(初期状態、スタートする頂点) ans = dfs(0, 1) ans = dfs(0, 2) ans = dfs(0, 3)
どれでも大丈夫です。ただし、初期状態はdp[0]とすべて未訪問の状態でなければなりません。
頂点を変える場合は以下の所も変更してください
if S==(1<<V)-1 and v==0: # V==0の所をスタートした頂点にする return 0
入力例1の場合0-1-2-3-0と行くのが最短経路になるので、2進数で表すと、0b000(dp[0])-0b0010(dp[2])-0b1010(dp[10])-0b1110(dp[14])-0b111(dp[15])の遷移になる。
今回初めてbitを使ったので理解するまで大変でした。
参考サイト
https://kakedashi-engineer.appspot.com/2020/05/21/dpl2a/
https://cinnamo-coder.hatenablog.com/entry/2019/06/23/181751
https://algo-logic.info/bit-dp/#:~:text=%E3%83%93%E3%83%83%E3%83%88DP(bit%20DP)%20%E3%81%A8,(DP)%E3%81%AE%E3%81%93%E3%81%A8%E3%81%A7%E3%81%99%E3%80%82
区間DP
今回は区間DPをやっていきます。
理解するまでに時間がかかりましたが、理解できればなるほどと思いました。
例題は以下の問題でやっていきます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp
とりあえず、
4 1 2 3 4
与えられるデータはこれで行きます。
まず、基本となるコードを書いていきます。
N=int(input()) W=list(map(int,input().split())) #DPテーブル dp = [[0]*(N) for _ in range(N)] #探索する幅 for w in range(1,N+1): for i in range(N): j=w+i if j>=N: continue print(W[i:j+1])
この結果は以下のようになります
[1, 2] [2, 3] [3, 1] [1, 2, 3] [2, 3, 1] [1, 2, 3, 4]
このように探索する幅をどんどん広げて行きます。
そして、この探索範囲で取り出せるブロック数の最大値をdpテーブルに書き込んでいきます。
求め方は2パターンあって、まず1パターン目をかいていきます。
N=int(input()) W=list(map(int,input().split())) #DPテーブル dp = [[0]*(N) for _ in range(N)] for w in range(1,N+1): for i in range(N): j=w+i if j>=N: continue #パターン1 #区間を取り除けるか and 両端を取り除けるか if dp[i+1][j-1]==w-1 and abs(W[i]-W[j])<=1: dp[i][j]=w+1;
まず、dp[i+1][j-1]==w-1の処理から解説していきます。
探索範囲がdp[i][j]の時、両端を除いた区間はdp[i+1][j-1]になります。
画像で表わすとこうなります。
そして、dpテーブルにはその区間で取り除くことができるブロック数の最大値がはいっています。
dp[i+1][j-1]を調べて、w-1となればその区間はすべて取り除くことができることになります。
次のabs(W[i]-W[j])<=1を解説していきます。
仮に両端を取り除いた区間がすべて取り除けた場合、残りは両端のみになります。
今回の問題の条件は隣り合う数字がの差が1以内ならたたき出せるので、absで両端の差を絶対値にして、差が1以内かを判断しています。
それらの条件がすべてそろった場合、dp[i][j]の区間はすべて取り除けることになります。
なので、dp[i][j]=w+1となります。
2パターン目の処理を書いていきます
N=int(input()) W=list(map(int,input().split())) #DPテーブル dp = [[0]*(N) for _ in range(N)] for w in range(1,N+1): for i in range(N): j=w+i if j>=N: continue #パターン1 #区間を取り除けるか and 両端を取り除けるか if dp[i+1][j-1]==w-1 and abs(W[i]-W[j])<=1: dp[i][j]=w+1; #パターン2 #区間を分ける for mid in range(i,j): dp[i][j]=max(dp[i][j] , dp[i][mid]+dp[mid+1][j]); print(dp) print(dp) print(dp[0][-1])
この区間分けは探索区間における取り除くことができるブロック数の最大値を検索するものです。
探索方法はまず、探索区間を2ブロックにわける方法をfor文で全探索します。
そして、2ブロックに分けたそれぞれのブロックの取り除くことができるブロック数の最大値を足して、最終的にはその区間における取り除くことができるブロック数の最大値を求めることができます。
その結果をdpに書き込みます。
幅が小さい順で探索しているので、これらのパターンの結果はすでにdpに書き込んであります。
これで、パターン1とパターン2で全探索ができました。
そして、最終的には以下の表ができます
正解は全区間を探索した結果なので、dp[0][-1]になります。
わかりづらかったかもしれないですが、これが限界です。
参考記事
http://kutimoti.hatenablog.com/entry/2018/03/10/220819
おまけ
以下の問題を解いてみました
https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi
S=str(input()) dp = [[0]*(len(S)) for _ in range(len(S))] for w in range(2,len(S)+1): for i in range(len(S)): j=w+i if j>=len(S): continue if S[i:j+1]=="iwi": dp[i][j]=1 elif dp[i+1][j-2]!=0 and S[i]+S[j-1:]=="iwi": dp[i][j]=dp[i+1][j-2]+1 elif dp[i+2][j-1]!=0 and S[:i+2]+S[j-1]=="iwi": dp[i][j]=dp[i+2][j-1]+1 for mid in range(i,j): dp[i][j]=max(dp[i][j],dp[i][mid]+dp[mid+1][j]) print(dp[0][-1])
最初はこのコードを試して見たんですが、これだと入力例2のように以下のようになる場合に対応できないんですよね。
で、ちょと調べて改良してみたんですけど、WAで通らなかったです。
テストケースを調べてもでてこなくてこれ以上はわかりません
S=str(input()) dp = [[0]*(len(S)) for _ in range(len(S))] for w in range(2,len(S)): for i in range(len(S)): j=w+i if j>=len(S): continue if S[i:j+1]=="iwi": dp[i][j]=1 continue if S[i]=="i" and S[j]=="i": for k in range(i+1,j): if S[k]=="w": #おそらくここの処理が間違っている。全部消える時の処理ができていない dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1]+1) for mid in range(i+1,j): dp[i][j]=max(dp[i][j],dp[i][mid]+dp[mid+1][j]) print(dp[0][-1])
ナップザックDP
今回からAtCoderのD問題を解くためにアルゴリズムの勉強を始めます。
https://atcoder.jp/contests/abc032/tasks/abc032_d
上記の例でナップサックDPを使っていきます。
以下は上記の例の入力例1の場合で書いていきます。
N,W=map(int,input().split()) value=[] weight=[] for i in range(N): x,y=map(int,input().split()) value.append(x) weight.append(y) #DPテーブル dp=[[0]*(W+1) for i in range(N+1)] for i in range(N): for j in range(W+1): #処理を書いていく
ここまでは大丈夫だと思います。
最初自分はDQテーブルがよくわからなかったので図を載せておきます。
こんな感じで横は重量の最大値、縦はi番目の荷物を取ります。
では、ループの処理を書いていきます
N,W=map(int,input().split()) value=[] weight=[] for i in range(N): x,y=map(int,input().split()) value.append(x) weight.append(y) dp=[[0]*(W+1) for i in range(N+1)] for i in range(N): for j in range(W+1): if j>=weight[i]:#荷物を選ぶ場合 dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j]) else:#荷物を選ばないとき dp[i+1][j]=dp[i][j] print(dp[N][W])
if文の中の式は公式です。
私は以下の記事を参考にしました。
https://qiita.com/drken/items/a5e6fe22863b7992efdb#%E5%95%8F%E9%A1%8C-2%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C
これを実行すると結果的に以下の表ができます。
右下の数値が答えになります
自分なりにわかりっやすくまとめてみたのですが、わかりづらかったら申し訳ありません。
今回参考にした記事
https://nashidos.hatenablog.com/entry/2020/05/09/071907
https://qiita.com/drken/items/a5e6fe22863b7992efdb#%E5%95%8F%E9%A1%8C-2%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C
ReactでTrello風アプリを作って見た
まず、以下が完成品です
https://matsudasan.github.io/Trello/
使ったライブラリはreact-beautiful-dndです。
https://github.com/atlassian/react-beautiful-dnd
最初はreact-dndを使っていたんですが、react-beautiful-dndのサンプルにTrelloに似ているものがあったのでこちらにしました。
ABC132(A~C)
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 - Ordinary Number
https://atcoder.jp/contests/abc132/tasks/abc132_b
かかった時間 9分
実行時間 29ms
n=int(input()) p=list(map(int,input().split())) ans=0 for i in range(n-2): List=p[i:i+3] P=List[1] num=sorted(List)[1] if P==num: ans+=1 print(ans)
C - Divide the Problems
https://atcoder.jp/contests/abc132/tasks/abc132_c
かかった時間 9分
実行時間 66ms
N=int(input()) d=list(map(int,input().split())) d.sort() l=d[:N//2] r=d[N//2:] print(r[0]-l[-1])
配列をソートして、2分割する。
その後、r[0]-l[-1]をすれば答えがでる。
