AtCoder ABC 168 D - .. (Double Dots) (400 点) in Python
幅優先探索を使う典型的な問題でした...。python
ではcollections
モジュールのdeque
を用いることによって実装してあげるのが最も自然なのかなと思うので、そのように実装してあげます。「幅優先探索ってそもそも何?」という方は、けんちょんさんの記事を一度読まれることをお勧めします。C++
で書かれていますが、幅優先探索の考え方はプログラミング言語に依存しないので、大いに参考になると思います。
from collections import deque
n, m = map(int, input().split())
Graph = [[] for _ in range(n + 1)] # 隣接リスト(1-index)
for i in range(m):
a, b = map(int, input().split())
Graph[a].append(b)
Graph[b].append(a)
q = deque()
q.append(1) # 頂点 1 を enque
dist = [-1] * (n + 1)
res = [0] * (n + 1)
while len(q) > 0: # queue が空になるまで繰り返す
now = q.popleft() # queue から取り出す(deque)
for edge in Graph[now]: # 隣接している頂点について
if dist[edge] != -1: # すでに書き換えられている場合は何もしない
continue
dist[edge] = dist[now] + 1
q.append(edge)
res[edge] = now
print('Yes') # `No`となることはない
for i in range(2, n + 1):
print(res[i])
注意点として、制約に「どの2部屋間も、通路をいくつか通って行き来が可能」とあるので、No
となるような場合は存在しないということです。解説(editorial)にもある通りですが、深さ(ある部屋から部屋1
に移動するために廊下を通る最小の回数)d + 1
の部屋には、深さd
の部屋が少なくとも一つは隣接しています。
AtCoder ABC 167 D - Teleporter (400 点) in Python
問題の概要
N
個の町があり、それぞれの町には1
からN
までの番号が一意に割り当てられている(重複なし)。各町i
にはテレポーターがあり、町Ai
に移動することができる。このとき、町1
から出発してK
回の移動を繰り返したときの場所はどこでしょうか。
問題のURL
制約
2 <= N <= 2*10^5
1 <= Ai <= N
1 <= K <= 10^18
考え方
- 日本語が分かりにくいので、コードを見た方が早いかもしれません
制約を見て分かるように、K
の値が非常に大きいです。したがって、K
回の操作を純粋にシミュレーションすることはできません。
そこで「どこかで循環するんだろうな~」ということまでは比較的容易に思いつくと思います。実際、町の数はN
個しかないので、N
回の移動(最初は1
にいる)を行えば必ず循環します(鳩の巣原理)。したがって、循環する部分(循環が始まる地点)を特定してあげれば、求めるK
回の移動後における地点を求めることができます。循環が始まる地点は以下のように求めることができます:
- 辿った地点を覚えておいて、かつて辿ったことのある地点に到達するまで移動を繰り返す
N
回の移動を繰り返したときの位置の変遷を覚えておいて、N
回の移動時における地点に訪れたのは何回の移動を行ったときかを調べる
次に、得られた循環する部分を用いてK
回の移動後の地点を求める方法について考えます。まず、K
が循環が始まる地点よりも小さい場合はそのまま出力してあげて大丈夫です。一方、K
が循環が始まる地点に達している場合、循環が始まる地点まで移動して、そこから残りの移動回数を循環する地点の数で割った余りの分だけ移動してあげればよいことが分かります。
解答(Python)
- 入力は
0-index
になるようにしておきます
解法1:辿った地点を覚えていく方法
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
# order[i]: 町iに到達したときの総移動回数
order = [-1] * (N + 1)
seen = []
pos = 1
while order[pos] == -1:
order[pos] = len(seen)
seen.append(pos)
pos = A[pos]
period = len(seen) - order[pos] # 循環の周期
m = order[pos] # 循環する地点
if K < m:
print(seen[m])
else:
K = m + (K - m) % period
print(seen[K])
解法2:事前にN
回の移動履歴を覚えておく方法
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
seen = [1]
pos = 1
for i in range(N * 2): # 後の参照のために余分に回しておく
pos = A[pos]
seen.append(pos)
loop_end = N
loop_start = N - 1
# 周期を見つける
while seen[loop_start] != seen[loop_end]:
loop_start -= 1
period = loop_end - loop_start # 循環の周期
m = N - period # 循環が始まる地点
if K < m:
print(seen[K])
else:
K = m + (K - m) % period
print(seen[K])
余談
解法1において次のように実装してしまうとTLE
になるかもしれません。
seen = [1]
pos = 1
while True:
if A[pos] in seen:
seen.append(A[pos])
break
seen.append(A[pos])
pos = A[pos]
一般に、python
におけるelement in list
は非常に遅いことが知られています。注意しましょう。
AtCoder ABC 164 D - Multiple of 2019 (400 点) in Python
問題の概要
1
から9
までの数字からなる文字列S
が与えられる。このとき、S
のi
番目からj
番目までの部分文字列を10進数の整数とみなしたとき、その値が2019の倍数になるような(i,j)
の個数を求めてください。問題のURL
- 制約:
1 <= |S| <= 200000
解答
先にPython
による解答を載せます。
s = input()[::-1] # 入力文字列を逆順でsに格納
counts = [0] * 2019
counts[0] = 1
num, d = 0, 1
for char in s:
num += int(char) * d
num %= 2019
d *= 10
d %= 2019
counts[num] += 1
ans = 0
for cnt in counts:
ans += cnt * (cnt - 1) // 2
print(ans) # 答えの出力
ダメな解法
この問題を見たとき、自分を含めて恐らく多くの方は、「(i,j)
の組を総当たりすればよい」と考えたことと思います。これを素直に実装すると下記のようなコードになります。
s = input()
n = len(s)
cnt = 0
for i in range(n-2):
for j in range(i+3, n+1):
tmp = int(s[i:j])
if tmp % 2019 == 0:
cnt += 1
print(cnt)
このコードを提出するとTLE
、実行時間制限超過となります。それもそのはずで、計算量を確認すると、N=2*10^5
に対してO(N^2)
です。したがって、Python
だから通らないのではなく、アルゴリズムの設計(問題の解き方)が間違っています。
解法の説明
解説PDFを読むと「2019 は 2 でも 5 でも割り切れないので、mod2019 では 10 に逆元が存在します」と書かれていますが、あまりピンときませんでした。次のように考えてみましょう。入力文字列として、S = 31415926535
を考えます。このとき、例えば4
番目から8
番目までの部分文字列15926
が2019の倍数であるか判定したいというのが本問の主題です。特定の部分文字列が2019の倍数であるかどうかは、int(s[[i:j+1]) % 2019 == 0
とすればよいのですが、これを逐一やっていては上でも述べたようにO(N^2)
の計算量がかかってしまいます。そこで、この部分文字列を次のようにとらえてみます。
$$ 15926 = \frac{15926535 - 535}{10^3} $$
このように考えることの利点は、$10^3$ が $2019$ と互いに素(最大公約数が $1$)であるため、$15926$ が $2019$ の倍数であるかどうかは、上式右辺の分子に着目すればよいということです。したがって、アルゴリズムを設計する際は、与えられた文字列の右からk
番目($k=0,1,2,\dots,n$)から最右端までの部分文字列を保持しておけばよいことになります。これは$O(N)$で実行できます。分子が $2019$ の倍数かどうかは、分子を $A-B$ としたときに、$A \:\:\mathrm{mod}\:\: 2019$ と $B\:\: \mathrm{mod}\:\: 2019$ の値がそれぞれ等しければ、元の整数(上式左辺)は $2019$ の倍数であると言えます。以上を踏まえて、上に載せたコードを見ていただくと、なぜあのような記述で解が求まるのか分かると思います。
AtCoder ABC 150 C - Count Order (300 点) in Python
問題概要
大きさ $N$ の順列*1 $P,\,Q$ が与えられる.このとき
- $P$ が辞書順で何番目か
- $Q$ が辞書順で何番目か
をそれぞれ求め,それらの差の絶対値を求めよ.
※ 問題へのリンク
制約
- $2 \leqq N \leqq 8$
- $P,\,Q,\,N \in \mathbb{N}$
思考プロセス
- $N$ は高々 $8$ なので,愚直に $N!$ 通りの順列を計算しても大丈夫そう.
- でも,もっと賢い方法を考えたい.そういえば,ProjectEuler 24 と似ている.
- 例えば,$(3,4,1,2)$ を考えると,最上位が $3$ であるため,最上位が $1$ と $2$ のそれぞれ $3!=6$ 通り(計12通り)は排除できる.次に,最上位から2番目の桁を見ると $4$ なので,$31$xx および $32$xx のそれぞれ $2!=2$ 通り(計4通り)は排除できる.そして,最上位から $3$ 番目を見ると $1$ なので,$3412$ の可能性しかなくなり,順番が確定する.よって,$(3,4,1,2)$ は $12+4+0+1=17$ 番目の順列である*2.このようにして,与えられた順列が辞書式で何番目なのかを計算することができる.
- 注意すべき点としては,例えば $(2,4,3,1)$ の場合を考えたとき,最初に $(2-1)\times 3! = 6$ 通りの可能性が排除される.次に,$(4-1)\times 2! = 6$ 通りの可能性が排除されるかというとそうではなく,正しくは $2\times 2!=4$ 通りの可能性が排除される.これは,最上位の桁が $2$ であり,$21$xx または $23$xx の可能性しかないためである.
書いたコード(Python)
def fact(n):
if n==1 or n==0:
return 1
else:
return n*fact(n-1)
def index(n,lis):
for i in range(len(lis)):
if n==lis[i]:
return i
def count(lis):
l = list(range(1,len(lis)+1)) #[1,2,...,n]
ret = 1
for i in range(len(lis)-1):
ret += (index(int(lis[i]),l)) * fact(len(l)-1)
l.remove(lis[i])
return ret
動作例
>>> count([4,1,3,2])
20
基本情報技術者試験に対する試験勉強
はじめに
基本情報技術者試験に合格したので試験勉強として行ったことを書く.試験の概要などについては公式のページを参照されたい.
時系列
- 2019-8-14:受験申し込み(申し込みの期限日)
- 2019-9-10:試験勉強開始
- 2019-10-20:受験
- 2019-11-20:合格発表
試験勉強
基本的には,参考書を読むことと過去問を解いた.参考書は『キタミ式イラストIT塾基本情報技術者』(きたみりゅうじ)を使用した.参考書に関しては賛否両論あると思うが,書店で気に入ったものを購入すれば良いと思う.買わないという選択肢もあると思うが,体系的に纏まった書籍が一冊くらい手元にあると勉強が楽になると思う.過去問は IPA のページから入手可能.過去問の解説に関しては,基本情報技術者試験トットコムにほとんど載っている*1.午前の問題は 13 回分(平成24年春季〜平成31年春季),午後の問題は 7 回分 (平成28年春季〜平成31年春季)をそれぞれ解いた.プログラミング言語は C 言語を選択した.言語選択に関しては色々な意見があると思うが,使用したことのある言語がある場合はそれらを選択すれば良いと思う.なければ,表計算を選択するのが無難だと思う.
おわりに
試験後の記事でも書いたように,午前の試験問題の半数程度は過去に出題された問題と全く同じものが出題される.そのことをもっと早い段階で理解していれば,参考書を隅々読むような無駄な時間を過ごさずに済んだかもしれない.また,午後の試験においては,時間を計測して解かないまま本番を迎えてしまったため,本番で時間が足りなくなるという惨事に見舞われてしまった.日々の勉強にもう少し緊張感を持って取り組むべきだった.また,午後の問題は選択式となっているため,早い段階でどの問題を選択するのかを決めて試験に臨むべきだった.
*1:ただし一部の午後の試験については解説がないので注意.