[PYTHON] Yukicoder-Wettbewerb 250 Eintragungsrekord

Yukicoder-Wettbewerb 250 Eintragungsrekord

A 1063 Routenberechnung / Sqrt-Berechnung

Wenn wir das größte i 2 finden, das n teilen kann, lautet die Antwort i und n i 2 2.

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

Man betrachte f (x) = C 1 </ sub> - C 2 </ sub>. F (x) = 2x 2 + (ac) x + (bd) Wenn x = + ∞ und x = -∞, ist natürlich f (x) = + ∞. Das kleinste ist f '(x) = 4x + (ac) = 0 → x = (c - a) Wenn f ((c - a) / 4) positiv ist, gibt es keinen Schnittpunkt, wenn es 0 ist, gibt es einen Schnittpunkt, und wenn es negativ ist, gibt es zwei Schnittpunkte. Zwei Schnittpunkte sind -∞. Da es sich bei (c - a) / 4 und (c - a) / 4 .. + ∞ befindet, ist es ausreichend, durch Dichotomie nach x zu suchen, so dass f (x) = 0 ist. Danach die Gleichung der Geraden, die durch die beiden Punkte verläuft Ich habe Gugu geschrieben.

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 Strommast / -mast (einfach)

Abgesehen von der Tatsache, dass die Kosten aus den Koordinaten berechnet werden müssen, ist dies nur die kürzeste Pfadberechnung des gewichteten Graphen, sodass sie normalerweise durch die Suche nach der Breitenpriorität gelöst werden kann. Der folgende Code wird jedoch zu TLE, es sei denn, es handelt sich um PyPy (lacht).

#AC nur mit 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 # Rot und Blau und weitere Farben (Easy)

Verloren. Ich könnte schreiben, dass es naiv war, aber natürlich TLE. Oder selbst wenn es nur ein B gäbe, würde ich TLE mit N = 6000 und B1 = 3000 (lacht).

Nachtrag: Ich habe den Kommentar DP eindimensional gemacht, aber in Python war er immer noch TLE.

#AC nur mit 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))