AtCoderで青色になるまでにしたこと
はじめましての方ははじめまして。新青コーダーのkawap23(twitter ID: kawap23)です。青色になった自慢がしたくて記事書いたので、いいねや拡散してもらえると喜びます（クズ）
2020/5/10に行われたABC167で"6完"し、"黄色"パフォを出して青色になりました。
現状＆自分語り～青色～
2019年8月10日に水色になってから9ヶ月かけて青色になりました。予定では4月中旬に青色になる予定でしたが、うまくいかないもんですね。普段はAtCoderでコンテストスポンサーもした某社で働いています。が、職場ではプログラムは書きませんん。触りません。見ることはあります。嘘です。人が書いてるのを後ろから覗くというのが正しい表現だと思います。最近だと同期がpythonでリストに対して"in"で存在判定をしていたので、setを使うべきと指摘し計算量改善に貢献しました。これが競プロerの素晴らしいところですね。Nは4でしたけど…。
バックグラウンドは物理・材料系で仕事もそんな感じの研究なのでプログラムはほぼ独学でしてる趣味です。twitter界の皆様にには大変お世話になっています。ありがとうございます。
さて、青色になったレートの伸び方はこんな感じです。緑後半から明らかに傾きが変わっています。
精進の進捗はこんな感じ。写真はいつもお世話になっているAtCoder Problemsさんから。色変したときくらいお布施したいです。新しく追加されたDifficulty Piesいいですね。色が綺麗。他の人と比べて進捗が早いとか問題数が多いとかはそこまでないですが、初ACからのstreak記録だけならほとんどの人に勝っているのではないでしょうか。もちろんあのtouristさんにも！
青コーダーになるまで
ようやく本題ですね。水色になった時から同成長したかなと思い、水色になるまでにしたことの記事を見てますが、ツッコミどころ満載ですね。今なら水色になるためにUnion-Findは必須だと思う…
その上で青色になるまでに必要だと思うことは
- BFS. DFS
- bit全探索
- 高校数学(順列、組み合わせ等)
- gcd, lcm
- キュー、スタック
- 優先度付きキュー
- 累積和
- いもす法
- MODの処理
- 簡単なDP
- メモ化再帰
- 二分探索
- Union-Find
- 最短経路問題
ここまでは水色のときにも書きましたが、やはり水色になるまでに必要だと改めて思いました。が、ある程度使いこなせるようになったと思えるのは水色中盤以降ですかね…。実装に悩まなくなってくるとようやく使いこなせてきた感が個人的にはありました。これらをある程度使いこなせるようになったことが青色になれた一因かなと。
これらに加えて、学んだこと、使ったことがあるやつは…
- 上位陣大好きsegment tree (ほぼ使えない)
- BIT
- bitDP
- 桁DP
- 木DP
- 2次元累積和
- 2次元いもす法
- 最大流・最小カット
このあたりが知識ベースで増えた部分です。コンテストではほとんど出番がなかったですが、その問題までたどり着いてなかっただけの気もします。一番レートに効いたと思うのはDP関連ですね。DP関連をいかにしっかり解けるかは、大事な気がしました。
これは自分が水色～青色にかけて必要になりそうだと思っていたことと一致しているので、水色になったときの自分はさすがだなと思います。が、セグ木なんかほぼ使ってないので、水色になったときの自分は先見の明がないなと思います。
他にはコロナ関係のおかげで精進時間を取れたのもでかいですね。あさかつ、よるかつの有志コンは集中して問題に取り組めるのに加えて過去に解いた問題を触ることが増えるためいい復習になりました。企画してくださっているかたありがとうございます。できる限り参加します。みんなで競いましょう。
青色～黄色に向けて
なんとなく黄色になるために必要だと思っていることです。黄色になって答え合わせしたいですね。
- 500点～700点問題埋め
- 水色問題の復習
- セグメント木
- DPの無意識に”書ける”ようにする
- コンテストに出続ける
書くことに脳のコストをかけずに、考えるところにコストをかけられるようになればもう少し上にいけるかなと思ってます。
あとはただの目標ですが、Longest streakを黄色までしっかりと続けていきたいです。Longest streakだけなら勝てる人が多いので笑
最後に
青になるまでも色々な方々のブログやコードを参考にさせていただいのに加えて、提出されているコードも参考にさせていただきました。ありがとうございます。そして何よりtwitterでアドバイスをくださった方、本当にありがとうございます。一人ではここまで来れなかったです。
次の目標としては、
- 黄色
- オンサイトコンテスト・イベントへの参加
- マラソンでの入賞
- streakをつなぐ
- 職場に競プロを広げる
- 仕事にプログラミング能力を活かす
このあたりですかね。また強くなって記事を下記に戻ってきます。
では、このへんで。
Pythonで強連結成分分解するのにscipyが高速に動く(らしい)話
お久しぶりです。kawap23です。
10月から就職したため精進できていません。痛勤電車内でいかに精進できるかがこれ以降のノビに効いてきそうです。
さて今回は強連結成分分解も、前記事の最短距離問題と同じくscipyで速くなるんじゃねって思って調べ検証してみました。
基本的には、正確性より問題で使えるようになること目指しました。正確性は保証しません（大事なことなので(略)）。
2019年10月06日 夜 追記
maspyさんに自前実装の最適化がされていないと教えて頂いたので、プログラムを変更し時間を測り直しました。maspyさん、ありがとうございます。
参考にしたもの
- 蟻本
-
SciPyでグラフの連結判定・連結成分の個数取得: connected_components | note.nkmk.me
- twitterでコメントを頂いたmaspyさん、furutaさん
強連結成分分解とは
まぁ蟻本やWikiでも読んでください。不正確に簡単に言うと、お互いに行き来することができる点を一つにまとめるって感じです。使う問題としては旧ARCにはなりますが、ARC030-C 有向グラフなどがあると思います。
そもそもScipyを使った実装って速いの？
測定に使ったコードは最後に貼っておきますが、頂点数Nに対して、辺の数が2倍、3倍の各パターンに対して自前実装とScipy実装とで計算時間を比べました。
はっきり言って、自前実装とか相手にもなりません。touristと僕以上の差があります。
| 頂点数N | 辺の数M | 自前実装 | scipy実装 |
| 10^1 | 2 * 10^1 | 0.00 | 0.00 |
| 10^2 | 2 * 10^2 | 0.00 | 0.00 |
| 10^3 | 2 * 10^3 | 0.01 | 0.00 |
| 10^4 | 2 * 10^4 | 0.06 | 0.00 |
| 10^5 | 2 * 10^5 | 0.73 | 0.01 |
| 10^6 | 2 * 10^6 | 7.86 | 0.33 |
| 10^7 | 2 * 10^7 | 83.60 | 4.16 |
| 頂点数N | 辺の数M | 自前実装 | scipy実装 |
| 10^1 | 3 * 10^1 | 0.00 | 0.00 |
| 10^2 | 3 * 10^2 | 0.00 | 0.00 |
| 10^3 | 3 * 10^3 | 0.01 | 0.00 |
| 10^4 | 3 * 10^4 | 0.07 | 0.00 |
| 10^5 | 3 * 10^5 | 0.81 | 0.01 |
| 10^6 | 3 * 10^6 | 9.15 | 0.51 |
| 10^7 | 3 * 10^7 | 100.35 | 6.38 |
※頂点数10^6, 辺の数3 * 10 ^ 6は計算が終わりません。数時間たってPCがスリープになっている事故をやらかしてます。近いうちに計算させます。プログラム(実装)が悪くて時間がかかっているだけでした。10^7のまで普通に計算できました。
見ての通り、Scipy実装が圧倒的に速いです。最大で数万倍速度差があります。意味がわかんないです。（自前実装が最適化されていない可能性も大いにあります）
さらに両対数グラフにしてみると…
となりO(N + M)で比例の関係にありそうなことがわかります。多分アルゴリズムあってそうです。ここまできれいに見えると嬉しいですね。
使い方
グラフの受け取り
最短距離問題のときと同じく、疎行列で受け取るのが楽でいいと思います。
csr_matrixには重みを与える必要がありますが、0以外ではなんでも同じように扱われるので、とりあえず1にしときます。多重辺があるときは重みが勝手に増えますが問題ありません。scipy内部で勝手に1になってます。
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import connected_components N = int(input()) M = int(input()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T tmp = np.ones(M, dtype = np.int64).T graph = csr_matrix((tmp, (edge[:] -1)), (N, N)) print (graph) # 入力例 # 10 # 20 # 1 6 # 3 8 # 3 4 # 3 9 # 3 2 # 4 7 # 4 5 # 5 1 # 5 10 # 5 9 # 7 8 # 7 9 # 8 1 # 8 10 # 8 9 # 9 10 # 10 8 # 10 1 # 10 6 # 10 6 # 出力 # (0, 5) 1 # (2, 1) 1 # (2, 3) 1 # (2, 7) 1 # (2, 8) 1 # (3, 4) 1 # (3, 6) 1 # (4, 0) 1 # (4, 8) 1 # (4, 9) 1 # (6, 7) 1 # (6, 8) 1 # (7, 0) 1 # (7, 8) 1 # (7, 9) 1 # (8, 9) 1 # (9, 0) 1 # (9, 5) 2 # (9, 7) 1
関数の使い方
関数の形は connected_componentsで、返り値は強連結成分を一つとみなしたときの、成分の個数(int) 及び numpy.ndarrayです。返り値が2つあるのに気をつけましょう（自戒）
- グラフ：上で作ったscr_matrixあるいは隣接行列
- 有向・無向：directed = Trueで有向、Falseで無向
- 連結条件：connection = 'strong'で両方向に繋がっているときのみ連結、'weak'で片方向で連結でもOK
- 有向グラフの強連結成分分解はdirected = True, connection = 'strong' でOK
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import connected_components N = int(input()) M = int(input()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T tmp = np.ones(M, dtype = np.int64).T graph = csr_matrix((tmp, (edge[:] -1)), (N, N)) print (connected_components(graph, directed = True, connection = 'strong')) # 入力 # 10 # 20 # 1 6 # 3 8 # 3 4 # 3 9 # 3 2 # 4 7 # 4 5 # 5 1 # 5 10 # 5 9 # 7 8 # 7 9 # 8 1 # 8 10 # 8 9 # 9 10 # 10 8 # 10 1 # 10 6 # 10 6 # 出力 # (8, array([1, 2, 7, 6, 5, 0, 4, 3, 3, 3]))
結果の見方としては、10頂点だが8, 9, 10の3頂点が強連結成分であり、8 ~ 10を一つとみなすと8個の成分であるということを示しています。基本的には必要な情報が返ってくるのでAtCoderでも使えると思います。
まとめ
Scipyが有能だということがわかりました。Scipyやnumpy等を実装?している人たちすごいですね。感謝しながら使っていこうと思います。
付録
計算時間の測定に使ったコードです。
def measure(n, times): #頂点の数10 ** n, 10 ** n * times = 辺の数 import time from random import randint N = 10 ** n M = N * times G = [[] for _ in range(N)] #0-indexでの隣接リスト RG = [[] for _ in range(N)] #0-indexでの隣接リスト #逆辺用 G2 = [] #scipy用 for _ in range(M): A = randint(0, N -1) while True: B = randint(0, N - 1) #自己辺を許さないが、多重辺は許す if A != B: break G[A].append(B) RG[B].append(A) G2.append([A, B]) # ---------------------------------------------------------- # 以下自前実装用 # ---------------------------------------------------------- s_mine = time.time() def scc(): #非再帰関数で実装 def dfs(v): stack = [v] used[v] = True while len(stack) != 0: tmp = stack[-1] flag = True for i in G[tmp]: if not used[i]: flag = False used[i] = True stack.append(i) break if flag: #どこにも行かなかった時 stack.pop() # stack = stack[:-1] #一行上に最適化 vs.append(tmp) def rdfs(v, k): stack = [v] used[v] = True cmp[v] = k while len(stack) != 0: tmp = stack[-1] stack.pop() # stack = stack[:-1] #一行上に最適化 used[tmp] = True for i in RG[tmp]: if not used[i]: cmp[i] = k stack.append(i) used = [False] * N #既に調べたかどうか vs = [] #帰りがけの並び cmp = [-1] * N for i in range(N): if not used[i]: dfs(i) k = 0 used = [False] * N #既に調べたかどうか for i in vs[::-1]: if not used[i]: rdfs(i, k) k += 1 return k, cmp #強連結成分分解をしたあとの要素数kとそれぞれの点がどこに位置するか l1, lst1 = scc() f_mine = time.time() # ---------------------------------------------------------- # 以下scipy用 # ---------------------------------------------------------- import numpy as np from scipy.sparse import csr_matrix G2 = np.array(G2, dtype = np.int64).T tmp = np.ones(M, dtype = np.int64).T graph = csr_matrix((tmp, (G2)), (N, N)) s_scipy = time.time() import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import connected_components l2, lst2 = connected_components(graph, directed = True, connection = 'strong') f_scipy = time.time() if l1 == l2: #答えが一致している時 flag = True print ('OK') print ('頂点数: 10 **', n) print ('頂点数 : 辺の数 = 1 :', times) else: #答えが一致していない時 flag = False print ('NO') print ('スタック l1 =', l1) print ('scipy l2 =', l2) # print ('再帰関数 l3 =', l3) print (G) # print (graph) print ('自前実装 :', format(f_mine - s_mine, '.10f')) print ('scipy 実装:', format(f_scipy - s_scipy, '.10f')) print () return for i in range(2, 4): for j in range(1, 8): measure(j, i)
Python + scipy を使って最短経路もついでに取得する方法
こんばんは。kawap23です。
前回の記事で、最短経路知りたいなぁって言っているとTwitterで教えてくださった方がいるので、記事にして残しておきたいと思います。(maspyさん、ありがとうございます。)
あくまで、使うためですので、正確性や厳密性は保証しません。
scipyを使って最短距離問題を解く方法にいついては、前回の記事を見てください。
最短経路を求める方法
いきなり結論ですが、dijsktra(グラフ、有向 or 無向、始点、経路が必要 or 不要)と引数に一つ足すだけで、最短距離と同時に返ってきます。(numpy.ndarrayが2つ返ってくる)
- 経路：return_predecessors = True で経路が返ってくる (デフォルトはFalse)
- 返ってきたarrayには直前の頂点情報が入っているため、始点までたどることで最短経路をたどることができる。
- 始点には -9999 が入っている
- 始点と連結していない点にも -9999が入る
とこんな感じです。ちなみに始点に2つ以上リスト等の形で指定しても問題なく返ってきます。
使用例は以下の感じです。入力例は蟻本のものに非連結成分を追加したものです。
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import dijkstra N, M = map(int, input().split()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N)) distance_mat, processors = dijkstra(graph, directed = False, indices = [0, 1], return_predecessors = True) print ('点0からの最短距離') print (distance_mat) print ('各点の直前の点') print (processors) # 入力例 # 9 11 # 1 2 2 # 1 3 5 # 2 3 4 # 2 4 6 # 2 5 10 # 3 4 2 # 4 6 1 # 5 6 3 # 5 7 5 # 6 7 9 # 8 9 4 # 出力例 # 点0からの最短距離 # [[ 0. 2. 5. 7. 11. 8. 16. inf inf] # [ 2. 0. 4. 6. 10. 7. 15. inf inf]] # 各点の直前の点 # [[-9999 0 0 2 5 3 4 -9999 -9999] # [ 1 -9999 1 1 1 3 4 -9999 -9999]]
実行時間について
詳しい実行コードは載せませんが、N = 10^6, M = 10^7 で、10点に関して最短経路ありと最短経路なしで計算したところ、30.32秒と30.77秒とほとんど差がない結果でした。計算コストは最短距離を出す計算をするところがメインであり、最短経路はついでなのでまぁそうですねって感じです。
結論
最短経路を求めたい時は、引数にreturn_predecessors = True を加える。
返り値は、numpy.ndarrayが最短距離のarrayとは別に増える
計算コストは(多分)無視しても構わないくらい少ない(一点の情報の復元はO(N))
参考文献
Pythonで最短距離問題解くのにscipyが高速に動く(らしい)話
お久しぶりです。kawap23です。
入社が近づいてきてドキドキしています
ARC025-C: ウサギとカメやARC035-C: アットコーダー王国の交通事情のように最短距離問題を使う問題でPython (pypy)じゃ遅すぎる！ってなっていろいろな方のブログ等を参考にして、なんとかscipyが使えたのでメモがてら残しておこうと思います。
自分が忘れていたときに、ここを見て思い出すことが目的ですので、正確性や厳密性は保証しません。
参考にしたブログ
いきなりですが、参考にさせていただいた方のブログを書いておきます。
・scipyのインストールについて
Masato's IT Library:
WindowsにPython3系とnumpy・scipyをインストールする方法（2/3 ライブラリ編） - Masato's IT Library
・scipyの使い方について
じゅっぴーダイアリー:
scipyのFloyd-WarshallとDijkstraのすすめ Python 競技プログラミング Atcoder - じゅっぴーダイアリー
これとは別に、maspyさんがAtCoderで提出されていたコードなども参考にさせていただきました。
ありがとうございます。
あと、良くわからなかったらこれ読んだらいいと思います。英語なのでいい感じに和訳されているサイトあったら教えて下さい。Numpy and Scipy Documentation — Numpy and Scipy documentation
下準備 -scipyのインストール-
上で紹介したブログですが、実は2017年4月の記事で2年以上前のものでした。が、2019年9月に行っても問題なく行えました。自分の使っているPythonのバージョンとあったnumpy・scipyをダウンロードすることだけ気をつけたら大丈夫だと思います。
（そろそろ自分がPCを買い換えるので自分のためのメモ）
AtCoderはPython3.4で自分は3.6使ってますが、今のところ問題は起きていません。
そもそもscipy使った実装って早いの？
前述のじゅっぴーさんはFloyd-Warshall法の速度がくっそ早いとアピールしていましたので、私はDijkstra法の速度を載せときます。
まずDijkstra法はO(辺の数M × log (頂点数N))で、ある頂点から他の頂点までの最短距離を求める手法です。調べるのに使ったコードや詳しい条件は一番最後に載せておきます。どこまで含めて時間とするかは個々考えがあると思いますので、そんなもんねぐらいの気持ちでお願いします。
|
頂点数 N |
辺の数 M |
自前 実装 |
scipy |
全体 |
scipy auto |
auto 全体 |
| 10^3 | 10^4 | 0.22秒 | 0.02秒 | 0.31秒 | 0.03秒 | 0.03秒 |
| 10^4 | 10^5 | 2.74秒 | 0.15秒 | 0.52秒 | 0.14秒 | 0.22秒 |
| 10^5 | 10^6 | 34.56秒 | 2.52秒 | 3.51秒 | 2.64秒 | 3.31秒 |
| 10^6 | 10^7 | 429.58秒 | 41.03秒 | 49.05秒 | 41.97秒 | 49.73秒 |
scipyの早いですね。自作の関数捨てて scipy 使います。
使い方
グラフの受け取り
AtCoderでよくある、頂点数N、辺の数M、Ai, Bi 間の重みがC_i のグラフの受け取り方
入力は1-indexが多いので途中で-1しています。
※入力例は蟻本から(以降全て同じ)
# 入力 # N M # A0 B0 C0 # A1 B1 C1 # .... # A(M-1) B(M-1) C(M-1) import numpy as np from scipy.sparse import csr_matrix N, M = map(int, input().split()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N)) print (graph) # 入力例 # 7 10 # 1 2 2 # 1 3 5 # 2 3 4 # 2 4 6 # 2 5 10 # 3 4 2 # 4 6 1 # 5 6 3 # 5 7 5 # 6 7 9 # 出力例 # (0, 1) 2 # (0, 2) 5 # (1, 2) 4 # (1, 3) 6 # (1, 4) 10 # (2, 3) 2 # (3, 5) 1 # (4, 5) 3 # (4, 6) 5 # (5, 6) 9
隣接行列用意してM回値を更新してもいいですが、めんどくさい & Nが大きくMが小さいとき殆どが不要な情報(疎行列)となるのでこっちのほうが効率的かなと思います。何より短く書ける。
使い方-1 dijkstra法
関数の形はdijkstra(グラフ, 有向 or 無向, 始点)で、返り値は numpy.ndarray です。
- グラフ：上で作ったもの、あるいは隣接行列
- 有向・無向：directed = Trueで有向、Falseで無向グラフ
- 始点：indicesで表す(0 - index)
下記の例では、無向グラフで頂点0からの最短距離、有向グラフで頂点3からの最短距離を計算しています。行くことが出来ない頂点に関してはinfとなるみたいですね。
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import dijkstra N, M = map(int, input().split()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N)) ans = dijkstra(graph, directed = False, indices = 0) print (type(ans)) print (ans) print (dijkstra(graph, directed = True, indices = 3)) # 入力例 # 7 10 # 1 2 2 # 1 3 5 # 2 3 4 # 2 4 6 # 2 5 10 # 3 4 2 # 4 6 1 # 5 6 3 # 5 7 5 # 6 7 9 # 出力例 # <class 'numpy.ndarray'> # [ 0. 2. 5. 7. 12. 8. 17.] # [inf inf inf 0. inf 1. 10.]
使い方-2 floyd-warshall
関数の形はfloyd_warshall(グラフ, 有向 or 無向)で、返り値は numpy.ndarray です。
- グラフ：上で作ったもの、あるいは隣接行列
- 有向・無向：directed = Trueで有向、Falseで無向グラフ
注意は重みが正の辺のみに対応していること*1。重み0の辺を作りたいなら、10 ** (-9)とかの重みにして、最後切り捨てでもするんか…？(試してません)
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import floyd_warshall N, M = map(int, input().split()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N)) ans = floyd_warshall(graph, directed = False) print (type(ans)) print (ans) ans = floyd_warshall(graph, directed = True) print (ans) # 入力 # 7 10 # 1 2 2 # 1 3 5 # 2 3 4 # 2 4 6 # 2 5 10 # 3 4 2 # 4 6 1 # 5 6 3 # 5 7 5 # 6 7 9 # 出力 # <class 'numpy.ndarray'> # [[ 0. 2. 5. 7. 11. 8. 16.] # [ 2. 0. 4. 6. 10. 7. 15.] # [ 5. 4. 0. 2. 6. 3. 11.] # [ 7. 6. 2. 0. 4. 1. 9.] # [11. 10. 6. 4. 0. 3. 5.] # [ 8. 7. 3. 1. 3. 0. 8.] # [16. 15. 11. 9. 5. 8. 0.]] # [[ 0. 2. 5. 7. 12. 8. 17.] # [inf 0. 4. 6. 10. 7. 15.] # [inf inf 0. 2. inf 3. 12.] # [inf inf inf 0. inf 1. 10.] # [inf inf inf inf 0. 3. 5.] # [inf inf inf inf inf 0. 9.] # [inf inf inf inf inf inf 0.]]
使い方-3 shortest_path
関数の形は shortest_path(グラフ, 方法, 有向 or 無向, (始点))で、返り値は numpy.ndarray です。これの良いところは方法に"自動 (auto)"が設定できる点。いい感じに処理してくれるらしい。自分で指定することもできるし、これ一択の気がする。理解度が深まるかは別の話として強そう。
- グラフ：上で作ったもの、あるいは隣接行列
- 有向・無向：directed = Trueで有向、Falseで無向グラフ
- 始点：indicesで表す(0 - index) -->dijkstra法のときは必要
ここまでは今までのと同じ。違うのは方法のところで、method = ****
- 'auto'：下記4種類から自動で選択 (明示的に選択も可能)
- 'FW': floyd_warshall法 (O (N ^ 3))
- 'D': dijsktra法 (O (N (N * k + N * log(N)) ))
- 'BF': bellman_ford法 (O (N (N ^ 2 * k))) 負の辺があっても使えるのが特徴
- 'J': Johnson's algorithm: 知りませんm(_ _)
kは各頂点から伸びている辺の平均なので N * k = Mが成り立つ。
import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import shortest_path N, M = map(int, input().split()) edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N)) ans = shortest_path(graph, method = 'auto', directed = False) print (type(ans)) print (ans) ans = shortest_path(graph, method = 'auto', directed = True) print (ans) # 入力 # 7 10 # 1 2 2 # 1 3 5 # 2 3 4 # 2 4 6 # 2 5 10 # 3 4 2 # 4 6 1 # 5 6 3 # 5 7 5 # 6 7 9 # 出力 # <class 'numpy.ndarray'> # [[ 0. 2. 5. 7. 11. 8. 16.] # [ 2. 0. 4. 6. 10. 7. 15.] # [ 5. 4. 0. 2. 6. 3. 11.] # [ 7. 6. 2. 0. 4. 1. 9.] # [11. 10. 6. 4. 0. 3. 5.] # [ 8. 7. 3. 1. 3. 0. 8.] # [16. 15. 11. 9. 5. 8. 0.]] # [[ 0. 2. 5. 7. 12. 8. 17.] # [inf 0. 4. 6. 10. 7. 15.] # [inf inf 0. 2. inf 3. 12.] # [inf inf inf 0. inf 1. 10.] # [inf inf inf inf 0. 3. 5.] # [inf inf inf inf inf 0. 9.] # [inf inf inf inf inf inf 0.]]
まとめ
特に改造が必要なければshortest_path(graph, method = 'auto')で使ったらいいんじゃないですかね…
課題
ついでに最短経路を返してくれる関数ないんすかんね…
2019年9月10日追記
maspyさんに、返り値に最短経路を追加させる方法を教えていただいたのでそれについてもまとめました。
付録
速度測定に使ったコード
N, Mを手動で変えながら測定。場合によっては、連結じゃないときもあると思います。
ランダムに選んだ10点からの最短距離を求めました。
import time from random import randint #グラフの作成 N = 10 ** 6 #頂点数 M = 10 ** 7 #辺の数 G_1 = [[] for _ in range(N)] #自前用 隣接リストで管理 G_2 = [] #scipy用 for _ in range(M): # a <--> b間のつなぐo重みcの無向グラフ a = randint(0, N - 1) b = randint(0, N - 1) c = randint(1, 10 ** 2) G_1[a].append([c, b]) G_1[b].append([c, a]) G_2.append([a, b, c]) #始点として調べる点 lst = [randint(0, N - 1) for _ in range(10)] #自前の実装 (参考: 蟻本) def dijksrea_manu(s): #始点s from heapq import heappop, heappush INF = 10 ** 9 d = [INF] * N d[s] = 0 #始点の距離を0にする pque = [] heappush(pque, [0, s]) #要素を[距離、頂点]として管理 最初の位置を入れる while len(pque) != 0: #queの中に要素が残っている時 p = heappop(pque) #最も距離が短いものを取り出す v = p[1] #距離が最も短い頂点 if d[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ continue for i in range(len(G_1[v])): #頂点vの隣接リストを走査 e = G_1[v][i] if d[e[1]] > d[v] + e[0]: #距離が更新できるかを検討 d[e[1]] = d[v] + e[0] heappush(pque, [d[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる return d s_mine = time.time() for i in lst: #始点10点調べる d_1 = dijksrea_manu(i) f_mine = time.time() #scipy dijkustra s_scipy = time.time() import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import dijkstra G_2_mat = np.array(G_2, dtype = np.int64).T graph = csr_matrix((G_2_mat[2], (G_2_mat[:2])), (N, N)) h_scipy = time.time() for i in lst: d_2 = dijkstra(graph, directed = False, indices = i) f_scipy = time.time() #scipy shortest_path auto s_scipy_auto = time.time() import numpy as np from scipy.sparse import csr_matrix from scipy.sparse.csgraph import shortest_path G_3_mat = np.array(G_2, dtype = np.int64).T graph = csr_matrix((G_3_mat[2], (G_3_mat[:2])), (N, N)) h_scipy_auto = time.time() for i in lst: d_3 = shortest_path(graph, method = 'auto', directed = False, indices = i) f_scipy_auto = time.time() # print (d_1) # print (d_2) # print (d_3) print ('N = ', N) print ('M = ', M) print ('自前の実装: ', f_mine - s_mine) print ('import含むscipy全体 (dijkstra): ', f_scipy - s_scipy) print ('scipyのdijkstraの計算 (dijkstra): ', f_scipy - h_scipy) print ('import含むscipy全体 (shortest_path(auto)): ', f_scipy_auto - s_scipy_auto) print ('scipyのdijkstraの計算 (shortest_path(auto)): ', f_scipy_auto - h_scipy_auto)
Japanese Traditional Big Companyへの就活に競プロ(≒ AtCoder ?)が役に立たないことはなかった話
はじめに
ある大学院生がJapanese Traditional Big Company(いわゆる日系大手企業数社)に入社するために面接をうけたときの個人的な感想をダラダラと述べる記事です。
結論だけ言うと、タイトルの通り「競プロが役に立たない(= マイナス評価)ことはない」って感じでした。
受けた業界・職種・企業の大きさ
志望した企業は電気メーカーで、プログラミング関係の仕事は主流ではなく、一部AI関係をしているというレベルで、プログラミング能力は要求されていません。さらに職種は材料系の研究・開発でありプログラミングとは？みたいな感じです。会社の大きさは東証一部上場であり、典型的な日系大手企業です。古き良き大企業ってやつです。
ここが大切なところですが、プログラムを書く仕事はおそらくありません。（そもそもプログラムを書く仕事をしたくて選んだわけではない）
面接時の自分の競プロのレベル
そもそも競プロはじめて3ヶ月程度で緑色でした。
AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ
によると、競技プログラミングに熱心に取り組んでいて、学生ならかなり優秀ってレベルらしいです。個人的には、ある程度プログラミング出来ます、くらいは言っても許されるのかなぁくらいに思ってます。
面接で聞かれたこと
そもそもプログラミング能力は要求されていません。もちろんコーディングテストなんてものはありません。
「最近個人的に勉強していること」を聞かれてそこから競プロの話を面接官としてました。面接官は競プロって？状況ですので、緑コーダーです！って言ったらコミュニケーション不良で落とされると思いました。面接官に聞かれたことは、
- そもそも競プロって？
- 始めた理由
- 学んだこと
- 業務に役立つと感じていることは？
の4点にまとめられると思いました。1つ目に関しては、文系の親や友達が理解できるレベルで説明できるかが大切だと感じました。始めた理由とかに関しては、本音でいいんじゃないんですかね…。評価されたと(勝手に)感じたのは下2つの質問に関してで、
- プログラムは有限時間で動く
- (たいていの製品は)プログラムによって動かされている
- 自分の作った製品がどのように制御されるかを意識して作られたモノとそうでないモノは質が異なる体験をした(大学での研究一般で)
みたいな答えしていました。別にアルゴリズムの話やデータ構造の話はしていませんが、なんとなく面接官が良い反応をしていると感じたのがこのあたりでした。あとは、大学とは関係ない勉強を個人的にしていること(個人的には勉強と思っていません。ゲームです。)も評価されていると思います。
まとめ
僕の感じた限り、日系大手メーカー(not IT)で競プロのレートが役立つことはありません。が、競プロに取り組んで感じたことは評価されると思います。
ということで、みなさん競プロしましょう。
※このブログはAGC037をno sub撤退したあとに書かれました。
AtCoderで水色になるまでにしたこと
はじめまして。kawap23(twitter ID: kawap23)と申します8月10日に行われたAtCder Begginer conntest 137で水色になれたので、(競技プログラミングを始めてから)今までにやってきたことを(忘備録も兼ねて)書いておこうと思います。
現状～水色～
初回参加が2019年4月20日で8月10日現在最高1220で水色になりました。
爆上がりや爆下がりしているのはAGC, ARC相当のコンテストで１問無理やり通したり、嘘通したり、0完激萎えをかました結果です。
ちなみに精進の具合はこんな感じです。ABCのC問題はあと2問でABCのD問題に手を出し始めてます。
競技プログラミングを始めるにあたって
自分のバックグラウンドは物理であり、プログラミングに触れた経験は大学の授業(Fortran 12時間)、実験・測定用の(Labview)グラフィック型言語のみであり、if文、for文の概念(?)は理解しているという程度でした。その中で大学院の授業でpythonを使って機械学習の基礎的なことを授業があり、その中でプログラミングの練習がしたいと思い、プログラムを書く練習として競技プログラミングを始めました。
が、思った以上にAtCoderで問題が解けないことにイライラし、気がついたら機械学習の授業と課題を放棄して競技プログラミングのめり込んでいる自分がいました。
水コーダーになるまで
ようやく本題ですね
黒色～灰色
そもそも始めた時点では標準入力とは？という状態だったため、先人たちのブログをググりまくりながら参加するという状態でした。なので100分フルに使ってA, Bをギリギリ終わらせるという状態でした。
この時期に重視したことは、
- 入力の受け取り方で悩まないようにすること-->過去のA, B問題をする
- (少なくともコンテスト時間中は)300点400点問題でも手を動かして試し続ける
- 毎日1問は新規ACする
です。特に僕のような初心者は、やったことを忘れないように毎日繰り返すことが重要だと感じました。
灰色～緑色
ABC問題のCに取り組むと同時に、「いかに早く正確にA, B問題を通すか」を重要視していました。今はどうかわかりませんが、少なくとも数ヶ月前はAB早解きで緑パフォは出ていました。
この時期にしたことは
- 蟻本を買った(あくまで、買った)
- DFS, BFS, 累積和をコンテストを通して学んだ
- AGCも含めて、(レーティング的に)出ることができるコンテストに参加した
AGCはA問題だけでも解けるとレートが爆上がりするので、出得だと思います。
緑色～水色
この時期は真面目に競技プログラミングの勉強をしないとレートが伸びないと感じました。勉強法としては、ABCのC問題埋めをメインに、蟻本の初級編＋コンテストで出てきた中級編の学習をしていました。結果的に学んだこととしては
- 競技プログラミングの楽しさ
- 深さ優先探索
- 幅優先探索
- bit全探索
- 順列
- 最小公倍数・最大公約数の性質の確認、書き方の確認
- キューと優先度付きキュー
- 累積和
- いもす法
- MODの四則演算
- 動的計画法
- メモ化再帰(この中では一番好き)
- 二分探索
- Union-Find木(たぶん必要ない)
- 最短経路問題(たぶん必要ない)
だとABC137の開始前までは思っていたんですが、あくまで学んだことがあるだけで理解はしていなかったみたいです…。ただ自分の引き出しが格段に増えていることは実感できました(悔しくなるポイントが以前と変わった)。
あとはこの時期は考察の大切さに気が付きました。そもそも制約条件からどれくらいの計算量に抑えないといけないのヒントがもらえる時"も"あります。
とりあえず過去問解きながら蟻本を斜め読みするぐらいがちょうどいいと思いました。
水色～青色に向けて
ここからは次のステップに向けて自分が必要だと感じていることを書きます。青色になって答え合わせしたいです。
最後に
水色になるまでに様々な方のブログやコードを参考にさせていただきました。
特にmaspyさんのコードは「ひぇーーー」って感じで、知らない知識が詰まっていてすごく勉強になりました。
あとはじゅっぴーさんのブログ「じゅっぴーダイアリー」は分類等がしっかりしているのに加えて、おもしろいので、良く読んでいました。
(勝手に名前だしてすいません)
偉大な先人についていくだけでなく、いつか参考になるようなコードを書けるようになるといいなぁ…
2019年8月25日追記
2019年8月24日に緑色に戻りました…
2019年9月27日追記の追記
2019年9月1日に水色に復帰しました
