話題になった^1問題なので取り上げてみます。
a, b, h, m = map(int, input().split())
from math import sqrt, cos, radians
angle = abs(30 * (h + m / 60) - 6 * m)
c = sqrt(a**2 + b**2 - 2*a*b*cos(radians(angle)))
print(c)
針の動きは次のように考えました：
H時のときに短針は30*H + 30 * (M / 60)°（12時間で360°なので）M分のときに長針は6*M°（60分間で360°なので）幅優先探索を使う典型的な問題でした...。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の部屋が少なくとも一つは隣接しています。
N個の町があり、それぞれの町には1からNまでの番号が一意に割り当てられている（重複なし）。各町iにはテレポーターがあり、町Aiに移動することができる。このとき、町1から出発してK回の移動を繰り返したときの場所はどこでしょうか。
問題のURL
2 <= N <= 2*10^51 <= Ai <= N1 <= K <= 10^18制約を見て分かるように、Kの値が非常に大きいです。したがって、K回の操作を純粋にシミュレーションすることはできません。
そこで「どこかで循環するんだろうな～」ということまでは比較的容易に思いつくと思います。実際、町の数はN個しかないので、N回の移動（最初は1にいる）を行えば必ず循環します（鳩の巣原理）。したがって、循環する部分（循環が始まる地点）を特定してあげれば、求めるK回の移動後における地点を求めることができます。循環が始まる地点は以下のように求めることができます：
N回の移動を繰り返したときの位置の変遷を覚えておいて、N回の移動時における地点に訪れたのは何回の移動を行ったときかを調べる次に、得られた循環する部分を用いてK回の移動後の地点を求める方法について考えます。まず、Kが循環が始まる地点よりも小さい場合はそのまま出力してあげて大丈夫です。一方、Kが循環が始まる地点に達している場合、循環が始まる地点まで移動して、そこから残りの移動回数を循環する地点の数で割った余りの分だけ移動してあげればよいことが分かります。
0-indexになるようにしておきます
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])
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は非常に遅いことが知られています。注意しましょう。
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$ の倍数であると言えます。以上を踏まえて、上に載せたコードを見ていただくと、なぜあのような記述で解が求まるのか分かると思います。
大きさ $N$ の順列*1 $P,\,Q$ が与えられる．このとき
をそれぞれ求め，それらの差の絶対値を求めよ．
※ 問題へのリンク
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
