こんにちは。心機一転して今日は8時に起きたとーです。
解くに至った問題（9問）
ABC:016C/021C/029C/034C
ARC:001A/015A/059C
AGC:005A/011A
ARC001A
以前解いたことがあったらしいけどとりあえずワーシャルフロイド法の勉強ということで
ワーシャルフロイド法は、ある2頂点を最短コストで行くにはどうすればよいかというのを、頂点の数をnとしてO(n**3)で計算してくれるアルゴリズム だからpython3で競プロやるときはn <= 100くらいが実用的かしらん
リストdを用意する このリストdには、n個の要素を持ったリストがn個あり、d[i][j]は、頂点iから頂点jに行くのにかかる最短コストを表す
リストの更新方法だが、単純な3重ループであり、d[i][j]を求めるのであれば、現在入っている最短コストの候補d[i][j]と、頂点kを介していく経路のコストd[i][k]+d[k][j]を比較し、コストの小さい方を採用していくというのを繰り返していく
一般的なコードは以下の通りになる
def warshall_floyd(d): #d[i][j]は、iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j],d[i][k] + d[k][j]) return d n,w = map(int,input().split()) #nは頂点の数、wは辺の数 d = [[float("inf") for i in range(n)] for i in range(n)] #d[i][j]は辺ijのコスト(存在しないときはinf) for i in range(w): x,y,z = map(int,input().split()) #x,yは頂点、zは辺のコスト d[x][y] = z #双方向のコストを更新 d[y][x] = z for i in range(n): d[i][i] = 0 #自身のところに行くコストは0 print(warshall_floyd(d))
この問題では、dの各要素を温度に見立て、±1,±5,±10の温度に対しコスト1の辺を伸ばしていく
以下はpython3による解答
s,e = map(int,input().split()) def warshall_floyd(d): #d[i][j]はiからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j],d[i][k] + d[k][j]) return d n = 41 #頂点（温度）の数は0~40の41個 d = [[float("inf") for i in range(n)] for i in range(n)] #d[i][j]は辺ijのコスト(存在しないときはinf) CL = [1,5,10,-1,-5,-10] #リモコンで調節できる温度 for i in range(n): for j in range(6): if 0 <= i+CL[j] <= 40: #0度以上40度以下であれば d[i][i+CL[j]] = 1 #コストを更新 d[i+CL[j]][i] = 1 for i in range(n): d[i][i] = 0 #自身のところに行くコストは0 warshall_floyd(d) print(d[s][e])
ちなみにABC016Cもワーシャルフロイド法を使う問題です こっちもやっておくとよいかも
じゅっぴーダイアリーを参考にさせていただきました ありがとうございます
juppy.hatenablog.com
ABC021C
ワーシャルフロイド法だと計算が間に合うかな？と心配になったので、ダイクストラ法の勉強をする
ダイクストラ法は、ワーシャルフロイド法同様に「ある地点から別の地点への最短経路を求める」ことを可能にしてくれるが、ワーシャルフロイド法と比較して、
①計算が速い（辺の数をE、頂点の数をVとしてO(ElogV))
②距離（移動の重み）が負の数だと使えない
③結構複雑
という特徴を持っている
仕組みとしては、ワーシャルフロイド法のように全部の頂点同士をマッチングさせるのではなく、必要な部分だけを扱っていくようになっていて、
①始点を見る
②始点を訪問済みにする、以下、訪問済みにした頂点はもう訪れない（もう一度訪問済みの頂点に戻るのは、距離（重み）が非負である以上は無駄なので）
③始点と隣り合う頂点を、最短経路で訪れたとしてそこまでの経路を更新する。そのうえで、[距離（重み）、行き先]の要素を、配列に「距離でソートして」入れていく
（この更新は、リストのソートとともに行われるため、距離（重み）が小さい方から必ず使われるので、必ず最短のものを選ぶことになり、複数の候補の比較がいらない）
④②と③の操作を、始点を移しながら、訪問済みの頂点がなくなるまで続ける
という感じ
コードを見ながら確認する
heapの仕様だが、Lをリストとして、
①heappop(L)でリストから先頭の要素を削除
②heappush(L,n)でリストにnを（ソートしたうえで）追加
となっている
import heapq def dijkstra_heap(s): #始点sから各頂点への最短距離 d = [float("inf")] * n #ここに始点sから各点への最短距離を格納 used = [True] * n #Trueは「最短距離が未確定」を意味する d[s] = 0 #始点sは当然距離0 used[s] = False #d[s]=0と確定したのでFalseに edgelist = [] #全部調べつくしたとき、このリストは空になる for e in edge[s]: #edgelistに[重み,行き先]を入れる heapq.heappush(edgelist,e) while len(edgelist): minedge = heapq.heappop(edgelist) #まだ使われてない頂点の中から最小の距離（重み）のものを探す if not used[minedge[1]]: #取り出した[重み,行き先]の「行き先」が、最短距離確定済み頂点なら continue #引き返す（距離が無駄に増える）だけなので使わない v = minedge[1] #行き先 d[v] = minedge[0] #距離（重み） used[v] = False #「今」見た頂点はFalseにする for e in edge[v]: #行き先から出る道[重み,行き先]の要素eに対して if used[e[1]]: #行き先が「最短距離未確定」ならば heapq.heappush(edgelist,[e[0]+d[v],e[1]]) #edgelistにソートしてぶち込む return d #調べつくしたら、最短経路の入ったリストdを返す n,w = map(int,input().split()) #nは頂点の数、wは辺の数を表す edge = [[] for i in range(n)] #edge[i]は、iから出る道の[重み,行先]の配列 for i in range(w): x,y,z = map(int,input().split()) #x,yは頂点の番号、zは重み（距離） edge[x].append([z,y]) edge[y].append([z,x]) print(dijkstra_heap(0)) #番号0の頂点からの最短経路を求める
この問題では、単に始点aからの最短経路を求めただけでは答えにならず、始点aから終点bに至るまでの最短経路の「数」を求める必要がある
ということで、結局ダイクストラ法を使うとはいえ、全頂点に対し、始点から各頂点への距離を出さないといけない
最短経路の数を求める時は動的計画法を使う やり方は、まずリストdpを要素の数だけ0埋めし、始点a(ここでは0インデックスなのでdp[a-1]）を1にする
それから、dp[0]~dp[n-1]までリストの要素を更新していく 各kについてdp[k]の更新方法を述べる
どうするかというと、まず0~n-1のjに対し、とりあえずdp[a-1][j]が0以上n-1以下のiであるかどうかを判定する そして、dp[a-1][k] == i+1であれば、最短経路ならば当然dp[j][k] == 1となっているはずである（a-1→j→kと移ってくれば、a-1からjのコストはi、jからkのコストは1になるはず）
これを満たすようなjとkに限り、dp[k]がdp[j]+dp[k]として更新される
以上を繰り返すことで、終点bに至る経路数がdp[b-1]として出る（今回は10**9+7で割ったあまりを出すように言われているので、更新のたびに10**9+7で割っている）
以下はpython3による解答
import heapq def dijkstra_heap(s): d = [float("inf")]*n used = [True]*n d[s] = 0 used[s] = False edgelist = [] for e in edge[s]: heapq.heappush(edgelist,e) while len(edgelist): minedge = heapq.heappop(edgelist) if not used[minedge[1]]: continue v = minedge[1] d[v] = minedge[0] used[v] = False for e in edge[v]: if used[e[1]]: heapq.heappush(edgelist,[e[0]+d[v],e[1]]) return d n = int(input()) a,b = map(int,input().split()) M = int(input()) edge = [[] for i in range(n)] for i in range(M): x,y = map(int,input().split()) edge[x-1].append([1,y-1]) edge[y-1].append([1,x-1]) L = [] for i in range(n): D = dijkstra_heap(i) L.append(D) dp = [0]*n dp[a-1] = 1 for i in range(n): for j in range(n): if L[a-1][j] != i: continue for k in range(n): if L[a-1][k] == i+1 and L[j][k] == 1: dp[k] = (dp[k]+dp[j])%(10**9+7) print(dp[b-1])
こちらもじゅっぴーダイアリーにお世話になりました。ありがとうございます。
ちなみに、この問題をワーシャルフロイド法とダイクストラ法の二通りで解いたところ、ダイクストラ法の方が10倍近く速かった（いずれも間に合った）
ABC034C
なんだかんだ言って放置してたアレ
簡単に言うと(H+W-2)!を(H-1)!*(W-1)!で割って10**9+7で割るとどんなもんよって話
10**9+7で割る操作は、足し算掛け算なら項ごとにやってもよい（まあ引き算もそうだけどあんまり使わないし、pythonは正しく計算してくれるらしいけど言語によってはうまくいかないこともあるので）
ただ、割り算に関しては、a/bをkで割ったあまりがc = a(modk),d = b(modk)としてc/dをkで割ったあまりと等しくなるとは限らないのでちょっと厄介
a÷b == a*(1÷b) (modk)
となることを用いる
1÷b (modk) はb**(-1) (modk)とも書かれ、これは逆元という（つまりbをかけるとkで割ったあまりが1になるような数）
だから、b**(-1)さえわかれば、aをbで割ったものをkで割ったときの余りは、aに(b**(-1))をかけたうえでkで割ったときの余りと等しく、つまりは掛け算と同じ形で扱えるようになる
さて、M = 10**9+7と置く Mは素数なので、フェルマーの小定理から、Mの倍数でない数bに対して、
b**(M-1) ≡ 1 (modM)
が成り立つ
ここから、
b**(M-2) ≡ b**(-1) (modk)
となり、
(a÷b)%M == (a*(1÷b))%M == (a*(b**(M-2)))%M == (a%M) * (b**(M-2)%M))
と計算される
さて、そこまでわかれば、割り算を掛け算と同じように扱えるようになったので好き放題してよい
分子は1からH+W-2まで、掛け算→Mで割ったあまりにする、というのを繰り返し
分母は1~H-1,1~W-1をかけてMで割ってを繰り返して計算した後、
（分子）* (((分母）** (M-2))%M) を計算し、これをMで割ったあまりをだせば、TLEすることなく答えが出る（TLEするのは、階乗の愚直な割り算にめっちゃ時間がとられるためなので）
（ここで割と大事なのは、掛け算した結果を割っても、余りには何ら影響がないということだったりする）
