今回は前回より大変簡単ですね（私にとっては）。
Aは6-a-bで、
Bは''.join([i + j for i, j in zip(S, T)])で、
Cは最小公倍数を求めるからPython標準libのgcd関数で簡単に計算：
from fractions import gcd
a, b = map(int, input().split())
print(a * b // gcd(a, b))
D - Brick Break
400点ですが簡単。
import sys
readline = sys.stdin.buffer.readline
n = int(readline())
num = 1
res = 0
for i in readline().split():
if num != int(i):
res += 1
else:
num += 1
if res == n: # 全部砕く=満足できない
print(-1)
else: # 少なくとも一個を残す
print(res)
E - Double Factorial
まずn<9とnが奇数の時0を貰えない。
自分の考え方は以下です。
- n//10個ゼロを貰えるはず。
- だがn=100の時、ゼロが12個。なぜ？50と100をかける時、おまけのゼロをもらった。だから
100/10+100/50=12です。 - n=1000の時、ゼロが124個。なぜ？50の倍数以外、250,500,750,1000をかける時、おまけのゼロをもらった。だから
1000/10+1000/50+1000/250=124です。 - つまりn=5のべき乗の10倍で(50,250,1250,6250など)おまけを貰えることだ。
import sys
readline = sys.stdin.buffer.readline
n = int(readline())
if n <= 9 or n % 2 == 1:
print(0)
quit()
res = n // 10
for j in range(1, 25): # int(math.log(10 ** 18, 5)) == 25
res += n // ((5 ** j) * 10)
print(res)
F - Playing Tag on Tree
DFSの知識を修得すれば簡単だ。（私はEを完成した後勉強を始めた）
まずAtCoderで流行っているDFSコードをコピーする。
def dfs(v):
dist = [None] * (n + 1)
dist[v] = 0
stack = [v]
while stack:
x = stack.pop()
for y in graph[x]:
if dist[y] is None:
dist[y] = dist[x] + 1
stack.append(y)
return dist
このコードを利用し、vと各頂点の距離リストを計算できる。
9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9
を例として、
dfs(6) == [None, 5, 4, 3, 2, 1, 0, 3, 4, 5]
dfs(1) == [None, 0, 1, 2, 3, 4, 5, 4, 5, 6]
がわかる。
次に、高橋君と青木君の戦略を考える。
高橋君の最適な戦略は、9へ逃げることです。
なぜなら、「高橋君より青木君との距離は遠い」を満足するすべての頂点(4, 5, 6, 7, 8, 9)の中に、
9と青木君の距離は一番遠いからです。
さて、ここに一つ問題が出た。
高橋君が自らゲームを終わらせる場合もあるよね。例の場合、高橋君は最後に「自殺」した。
(高橋君:6-5-4-7-8-9-8,6回; 青木君:1-2-3-4-7-8,5回)
幸いに、求めるのは青木君の移動回数なので、「自殺」を考える必要がない。
答えは「高橋君が行くべき頂点と青木君の距離-1」です。だから例の答えが5です。
高橋君の移動回数を求める場合、
二人の「目的地との距離」の差が奇数の場合「自殺」したので答えが「高橋君が行くべき頂点と青木君の距離」で、
偶数の場合「自殺」しないので答えが「高橋君が行くべき頂点と青木君の距離-1」
だと私が思います。（要検証）
ということで、コードは簡単です。
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n, u, v = map(int, readline().split())
m = map(int, read().split())
data = list(zip(m, m))
graph = [[] for _ in range(n + 1)]
for a, b in data:
graph[a].append(b)
graph[b].append(a)
res = 0
dfs_u = dfs(u)
dfs_v = dfs(v)
for i in range(1, n + 1):
dvi = dv[i]
if du[i] <= dvi:
if dvi > res: # 実行時間はmax(res, dvi)より早いからmax関数をやめる
res = dvi
print(res - 1)
(少々他人のコードを参考したが、皆さんは似たコードを使ってるから誰に感謝すべきかわからない
)