script 文は SpeakerDeck のページから取得が可能です。
<div style="max-width: 540px" class="center">
<script async="" class="speakerdeck-embed" data-id="63720e58066e4957af8f34499d7b16e4" data-ratio="1.33333333" src="//speakerdeck.com/assets/embed.js"></script>
</div>
以前の記事で ABC167-D について扱いました。ここで出題された問題は幅優先探索を用いることによって綺麗に解くことができました。今回はほぼ同様の実装で解くことのできる例題を見つけたので扱ってみたいと思います。
$N$ 個の町（町 $1,$ 町 $2,\dots ,$ 町 $N$）と $M$ 本の道路（道路 $1,$ 道路 $2,\dots ,$ 道路 $M$）があります。道路は二つの町を双方向につないでおり、すべての道路は同じ時間で移動が可能です。このとき、町 $a$ から町 $b$ への最短経路が何通りあるかについて、答えを $10^9 + 7$ で割った余りを求めてください。問題のURL
幅優先探索で探索をしながら経路を数えていきます。
from collections import deque
n = int(input())
a, b = map(int, input().split())
a, b = a - 1, b - 1 # 0-index
m = int(input())
adj = [[] for _ in range(n)] # 隣接リスト
for i in range(m):
x, y = map(int, input().split())
x, y = x - 1, y - 1 # 0-index
adj[x].append(y)
adj[y].append(x)
MOD = 10 ** 9 + 7
# 頂点 a からすべての頂点への最短距離を求める
q = deque()
q.append(a) # 頂点 a をenque
INF = 10 ** 9
dist = [INF] * n # INF で初期化
dist[a] = 0 # 始点から始点の距離 = 0
dp = [0] * n # 求める組み合わせ
dp[a] = 1 # 始点から始点は 1 通り
while q:
u = q.popleft() # queueから取り出す（deque）
for to in adj[u]: # 隣接している頂点について
if dist[to] == INF:
dist[to] = dist[u] + 1
dp[to] += dp[u]
dp[to] %= MOD
q.append(to)
elif dist[to] == dist[u] + 1:
dp[to] += dp[u]
dp[to] %= MOD
print(dp[b])
前回の記事において、単一始点最短経路（Single Source Shortest Path; SSSP）の重みを求めるプログラムである Dijkstra（ダイクストラ）法のpythonによる実装例を紹介しました。そこでは、隣接リストを用いて実装をしましたが、隣接行列を用いても同様に実装することができるので紹介しておきます。
from heapq import heappush, heappop
def dijkstra(s, n): # (始点, ノード数)
dist = [INF] * n
hq = [(0, s)] # (distance, node)
dist[s] = 0
seen = [False] * n
while hq:
v = heappop(hq)[1] # node
seen[v] = True
for to in range(n):
if W[v][to] == INF: continue # 隣接する辺がない場合は処理をスキップ
if seen[to] == False and dist[v] + W[v][to] < dist[to]:
dist[to] = dist[v] + W[v][to]
heappush(hq, (dist[to], to))
return dist
次のようなグラフを例に考えてみましょう。
4 6 1 # ノード数, エッジ数, 始点ノード
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5
Wの構築：
v, e, r = map(int, input().split()) # ノード数, エッジ数, 始点
INF = 10 ** 4 - 1 # 入力に応じて変更する
W = [[INF] * v for _ in range(v)] # 重み付き隣接行列
for i in range(e):
s, t, d = map(int, input().split())
W[s][t] = d
>>> print(*W, sep='\n') # 隣接行列
[999, 1, 4, 999]
[999, 999, 2, 999]
[1, 999, 999, 999]
[999, 1, 5, 999]
>>> d = dijkstra(r, v)
>>> print(d)
[3, 0, 2, 999]
こんにちは、みるか（@mirucaaura）です。
この記事では、わたくしみるかが 5 月に読んだ本について、徒然なるままに感想を語っていく内容となっております。
プログラミング言語 Java の入門書です。友人から譲り受けたので、ありがたく読ませていただいております。全体で 3 章構成になっており、それぞれの章は次のような内容になっています：
基本的な文法については、他の言語と大差がないので、言語間の差を意識してサラッと終わらせました。配列の宣言の仕方が少し慣れないので、いまだに調べながらやっています。オブジェクト指向については、名前こそ聞いたことあれど、実際に何たるかは全く分からない状態でした。一度読んだだけでは「分かった気になった」程度で、自分で本書の内容を再構成できるレベルには全然達しなかったので、何度か読みました。また、実際に Java の実行環境をローカルの PC に構築してプログラミングしながら勉強しました。
代数の入門書です。これまで代数を勉強したことがなかったのと、Twitter で本書を見かけたことをキッカケに購入してみました。内容としては、以下のようになっています：
入門書なだけあって、細かい事項には触れず主要な点に絞っている印象でした。まえがきでも述べられていますが、本書の目的は代数を勉強することではなく、代数的思考に慣れることにあります。そのため、本格的な代数の勉強をするためにはより専門的な書籍をあたる必要があるでしょう。しかしながら、いきなり専門書を読むと（これは多くの方に納得して貰えると思いますが...）挫折不可避です。ルベーグ積分を勉強しようとして、いきなり伊藤『ルベーグ積分入門』なんかに手を出すと厳しいのと同じです。そういう意味で本書のような基本的な本を挟んであげると良い導入になると思いました。実際、集合の濃度に関する証明なんかは、単射や全射を理解していないと厳密に示せなかったりして、学びは多かったと思います。
有名な本ですね。上の代数の本を読んでいて分からない箇所を参照するために使いました。位相については『多様体の基礎』に書かれている程度の内容しか理解できていないので、本書の内容はいつか理解したいです。
チャート式シリーズ 大学教養 線形代数 (チャート式・シリーズ)
5 月の上旬にヨビノリさんの線型代数の講義を一気見して、演習もしたいと思っていたところ、「チャート式 微分積分」に引き続き線形代数も出版されていたので購入しました。解説が非常に丁寧に記述されていて、学部一回の頃にあったらなぁ、なんて思ったりしました。少し昔話をすると、わたしがかつて受講した数学の講義では抽象的な概念に関する解説はそこそこで1、問題をどのように解くかに主眼が置かれていた印象が強いです。演習の時間は、逆行列を求める計算の仕方であったり、固有値・固有ベクトルをする手順を確認するくらいで、個人で取り組めるような内容ばかりでした。そのため、命題を示す訓練だったり反例を提示するような、いわゆる大学における数学の勉強をほとんどしてきませんでした。数学の勉強において何を以って理解したとするかは難しい問題ですが、本書のような演習書の存在は偉大であるとしみじみと思いました。
学部生の頃に購入してずっと手元に置いてある本です。チャート式で演習をしていて分からない部分が出てきたときに参照するために使ったり、ベクトル空間、正規直行規定、次元定理などの復習をしました。いまだにジョルダン標準形については理解していない（そもそも読もうとしていない...）ので、今後やっていきたいです。
競技プログラミングのためのアルゴリズムとデータ構造に関する本です。競技プログラミングをやらない人にも勉強になることが多い良書だと思います。本書で学んだアルゴリズムやデータ構造は、AOJ のサイトで実際に提出して自分の実装が正しいかどうかを確かめることができます。計算量を意識しないとTLEとなってしまう問題もあって、実践向きだと思いました。
まだ全然読み進められていないので、ここに載せるのも恐縮ですが、一応読み始めたということで掲載しておきます。もともと連続最適化をメインに研究してきたので、離散的な構造を持つような最適化問題について議論したことはありませんでした。学会などに参加したときに、「劣モジュラ性」や「M凸関数」のような用語を耳にしたり、講義で「マトロイド」と呼ばれる離散構造について学んだりしたくらいで、本格的に学んだことは皆無です。今後この本の知識が必要になることがあるということはないかもしれませんが、理論的に美しそうなので少し勉強してみたいと思います。
CAREER SKILLS ソフトウェア開発者の完全キャリアガイド
ソフトウェアエンジニアのためのキャリアの築き方に関する本です。書籍は 832 ページもあるらしいので、わたしは Kindle 版を購入しました。極めて多岐に渡る内容のため、気になった章をつまみ読みしています。就職活動をする前に目を通しておくべきだったなぁ、と思うような内容が豊富に書かれています。また、これからプログラミングを始めたいと考えている人や、エンジニアとして働きたいと考えている人など、プログラミングに携わる方であれば、本書から得るべきことは少なくないと思います。個人的に印象的だったのは、プログラミングに限らず何か学ぶ際に意識することとして、全体像を把握するために相応の時間を使うべきであるということです。全体像を把握できれば、その中で最もコアとなる部分を知ることができ、本当に重要な箇所に勉強の時間を割くことができます。闇雲に学びはじめてしまうと、どこが重要で本質的なのか分からなくなってしまうので、何かを新しく学ぶ際は意識しようと思いました。
何かを学ぶとき、学んだことを仕事なり日常生活なりに活かすためにはどのようなことを意識しながら学べばいいのかについて書かれた本です。本書の内容を一言でまとめてしまえば、学んだことを紙一枚 20 文字でまとめよ、ということに尽きます。もう少し具体的に言えば、学んだ内容を自分の言葉で咀嚼し、いつでもその内容について端的に説明できるようにせよ、ということになります。詳しい方法論については書籍に譲るが、本書もビジネス書なので「書かれている内容は納得できるけど、実際に実行するのは難しいよね」という感じの印象を受けました。
アニメを観ました。毎回にこにこしながら観ることができてとても楽しめました。漫画も一巻だけですが読みました。アニメを観た後なので、台詞が脳内で再生されて面白かったです。
ずっと読みたいと思っていた室伏広治さんの本です。本書は、自分の持っている力を極限まで引き出すためには何をどうすべきかについて、著者である室伏さんの経験・研究を基に追及した一冊です。室伏さんと言えばハンマー投げの金メダリストとして広く認知されていると思いますが、東京医科歯科大学教授という側面もあります。実際、本書の中にもご自身の論文の引用がなされていたりと、研究者らしくエビデンスのしっかりした内容が書かれています。さて、具体的な内容ですが、本書は漠然と「もっと集中力があればなぁ」と悩んでいる方におすすめできます。そもそも集中とは、集中そのものに目的があるのではなく、何らかの目的を達成するために集中するものです。したがって、まず考えるべきは、自分は何を達成したいのか、何を目標としているのか、何を成し遂げたいのか、などといったことを自問するところから始める必要があります。わたし自身、何となくすきな勉強や読書を漫然と長時間続けてしまうことがあるので、目標を明確にして物事に取り組むことの重要性を再認識しました。目標設定に時間をかけることは面倒に感じる方も多いと思いますが、そこをサボってしまうと毎日が漠然と過ぎ去ってしまいますし、モチベーションの維持も困難です。自分がなぜ今やっていることに時間を投下しているのかを意識して日々を過ごしていきたいと思いました。
東大卒プロゲーマー 論理は結局、情熱にかなわない (PHP新書)
本書を読むまで、著者である「ときど」さんを存じ上げませんでした。日本において二人目となるプロ格ゲーマーの方で、タイトルにもあるように東京大学のご出身の方です。まず言いたいのは、本書を読んでいる最中とても楽しかったです。すごくワクワクしながら一気に読んでしまいました。わたし自身、ゲームがすきということもあって、共感できる点も多かったし、物事への取り組み方・考え方についても参考になる記述が豊富にありました。よく「何かを極めた人間は他のことをやらせても他を圧倒する」みたいな言説がありますが、ときどさんは正にそれを体現している方だと思いました。詳しくは本書に譲りますが、プロゲーマーなのでゲームの腕前が世界レベルなのはもちろんのこと、東京大学の入学試験に合格したこともそうだし、研究の論文が国際学会で賞を受賞したりと、マルチな才能を発揮されています。なぜそのようなことが可能なのか。副題にある「情熱」がキーワードとなります。論理を重視する世の中になって久しいですが、成果を残せる人は物事に注ぐ情熱の量が凄まじい。これが本書の言わんとしていることであり、最も肝となる点であると思いました。わたしも一つのことに没頭しすぎる傾向はあると思っていましたが、そんなレベルでは足りないことが本書を通してよく分かりました。周りを見失ってしまう域に達するのは考えものですが、もっと没入感を大切にして物事に取り組んでいきたいです。
読み途中です。エンジニアとして生きていく以上、ネットワークの知識がないことは致命的であると思うので本書を通して基本的な知識を身に付けていきたいと思います。基本情報を受験したときに勉強した内容もありますが、ほとんどが記憶の彼方という状況なので丁寧に勉強します。
理学部の講義ではないので仕方がないと言えば仕方がないのですが…。↩
以前の記事で、pythonにおいてelement in listという書き方は非常に遅いので気を付けましょうと書きました。これについて、実例とともに見ていきたいと思います。
![線型代数[改訂版]](https://m.media-amazon.com/images/I/415X2XbxpZL._SL160_.jpg "線型代数[改訂版]")
element in listについてpythonでは、リストにある要素があるかどうかを次のように判定することが可能です。
>>> 1 in [1, 2, 3] # True >>> 4 in [1, 2, 3] # False
ただし、この処理は非常に遅いことが知られています（おわりに参照）。
ABC129-C を扱います。まだ問題を解いたことがない方はネタバレ注意です。
N段の階段があり、現在、0段目にいます。一度に移動できるのは、一段もしくは二段です。いま、a1, a2, ..., aM段目の床は壊れていて足を踏み入れることができません。壊れている床を踏まずにN段目までたどり着く方法は全部で何通りあるか求めてください。ただし、答えは10^9 + 7で割った余りを提出してください。問題へのURL
1 <= N <= 10^50 <= M <= N - 11 <= a1 < a2 < ... < aM <= N - 1基本的な方針としては、dpテーブルを用意してあげて、dp[i]にi段目の階段にたどり着くための移動方法（を10^9 + 7で割った値）となるように構成してあげればよいと思います。このとき、床が壊れているような階段kに対して、dp[k] = 0となることに注意をしながら、dpテーブルを埋めていってあげます。
はじめに、TLEになってしまう書き方を提示します。
n, m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 1
# 配列 a に 1 が含まれているかどうか
if 1 in a:
dp[1] = 0
else:
dp[1] = 1
# dp デーブル埋め
for i in range(2, n + 1):
if i in a:
continue
dp[i] = dp[i - 1] + dp[i - 2]
dp[i] %= MOD
print(dp[-1]) # dp[n] と同じ
このコードをPython3で提出するとTLEとなってしまいます。これは、dpテーブルを埋める際に、毎回の反復でiが配列aに含まれているかどうかの判定を行っていることが原因です。
そこで、次のように書き方を変更してあげましょう。すなわち、毎回の反復でiが配列aに含まれているかどうか判定するのではなく、事前に床iが壊れているかどうかのboolean配列を用意してあげて、それを利用しましょう。
n, m = map(int, input().split())
a = [0] + [int(input()) for _ in range(m)]
MOD = 10 ** 9 + 7
ok = [True] * (n + 1) # 床 i が壊れている ⇒ False
for v in a: # もちろん入力の段階で処理をしてもよい
ok[v] = False
dp = [0] * (n + 1)
dp[0] = 1
# 配列 a に 1 が含まれているかどうか（ここで一度 in を使うくらいはいいでしょう）
if 1 in a:
dp[1] = 0
else:
dp[1] = 1
# dp テーブル埋め
for i in range(2, n + 1):
if ok[i] == True: # 変更箇所
dp[i] = dp[i - 1] + dp[i - 2]
dp[i] %= MOD
print(dp[-1]) # dp[n] と同じ
これをPython3で提出してあげると、200msくらいでACとなります。
おわりに、element in listという書き方がどれくらい遅いのか、jupyter notebookで確認しておきましょう（思い付き）。
次のようなコードで実験してみましょう。lstという配列の要素に-1があるかどうかを判定する操作を1000回行うコードです。
なお、lstは事前に
lst = list(range(10 ** 5))
のように定義しておきます。
%%timeit
for i in range(1000):
if -1 in lst:
print('')
結果は次のようになりました。
1.67 s ± 211 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
平均で1.67 sかかっています。今回は反復回数を1000としましたが、上で扱った問題では最高で10 ** 5回程度の反復を要します（Nの制約条件より）。TLEになるのも納得できます。
