[PYTHON] yukicoder contest 250 entry record

yukicoder contest 250 entry record

A 1063 Route Calculation / Sqrt Calculation

If we find the largest i ^{2 </ sup> that can divide n, the answer is i and n ÷ i 2 </ sup>.}

n = int(input())

for i in range(10 ** 5, 0, -1):
    if n % (i * i) == 0:
        print(i, n // (i * i))
        break

B 1064 ∪∩∩ / Cup Cap Cap

Consider f (x) = C _{1 </ sub> --C 2 </ sub>. f (x) = 2x ^{2 </ sup> + (ac) x + (bd) Of course, when x = + ∞ and x = -∞, f (x) = + ∞. The smallest is f'(x) = 4x + (ac) = 0 → x = (c --a) When f ((c --a) / 4) is positive, there is no intersection, when it is 0, there is one intersection, and when it is negative, there are two intersections. Two intersections are -∞. Since it is located at (c --a) / 4 and (c --a) / 4 .. + ∞, it is sufficient to search for x such that f (x) = 0 by the dichotomy. After that, the equation of the straight line passing through the two points is calculated. I wrote Gugu.}}

a, b, c, d = map(int, input().split())


def f(x):
    return 2 * x * x + (a - c) * x + (b - d)


t = f((c - a) / 4)

if abs(t) < 1e-6:
    print('Yes')
    exit()

if t > 0:
    print('No')
    exit()

ok = 1e12
ng = (c - a) / 4
for _ in range(100):
    m = (ok + ng) / 2
    if f(m) > 0:
        ok = m
    else:
        ng = m
x1 = ok
y1 = x1 * x1 + a * x1 + b

ok = -1e12
ng = (c - a) / 4
for _ in range(100):
    m = (ok + ng) / 2
    if f(m) > 0:
        ok = m
    else:
        ng = m
x2 = ok
y2 = x2 * x2 + a * x2 + b

p = (y2 - y1) / (x2 - x1)
q = y1 - p * x1
print(p, q)

C 1065 Utility pole / Pole (Easy)

Except for the fact that the cost must be calculated from the coordinates, it is only the shortest path calculation of the weighted graph, so it can be solved by breadth-first search normally. However, the following code becomes TLE unless it is PyPy (laugh).

#AC only with PyPy
from math import sqrt
from sys import stdin
from collections import deque

readline = stdin.readline

N, M = map(int, readline().split())
X, Y = map(lambda x: int(x) - 1, readline().split())
pq = [list(map(int, readline().split())) for _ in range(N)]
PQ = [list(map(int, readline().split())) for _ in range(M)]

links = [[] for _ in range(N)]
for P, Q in PQ:
    links[P - 1].append(Q - 1)
    links[Q - 1].append(P - 1)

q = deque([X])
t = [float('inf')] * N
t[X] = 0
while q:
    i = q.popleft()
    for j in links[i]:
        a, b = pq[i]
        c, d = pq[j]
        k = t[i] + sqrt((a - c) * (a -c) + (b - d) * (b - d))
        if k < t[j]:
            t[j] = k
            q.append(j)
print(t[Y])

D 1066 # Red and Blue and more various colors (Easy)

Lost. I could write that it was naive, but of course TLE. Or even if there was only one B, I would TLE with N = 6000 and B1 = 3000 (laughs).

Addendum: I made the commentary DP one-dimensional, but it was still TLE in Python.

#AC only with PyPy
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

dp = [0] * (N + 1)
dp[1] = 1
dp[0] = A[0] - 1
for i in range(1, N):
    for j in range(i, -1, -1):
        dp[j + 1] += dp[j]
        dp[j + 1] %= 998244353
        dp[j] *= A[i] - 1
        dp[j] %= 998244353

print('\n'.join(str(dp[b]) for b in B))