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))

Recommended Posts

yukicoder contest 256 entry record
yukicoder contest 267 entry record
yukicoder contest 264 entry record
yukicoder contest 245 entry record
yukicoder contest 250 entry record
yukicoder contest 262 entry record
yukicoder contest 265 Participation record
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 273 Participation record
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
yukicoder contest 249 Participation record
yukicoder contest 271 Participation record
yukicoder contest 251 Participation record
yukicoder contest 242 Participation record
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
yukicoder contest 257 Participation record
yukicoder contest 254 Participation record
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
yukicoder contest 247 Participation record
yukicoder contest 261 Participation record
yukicoder contest 278 Participation record
yukicoder contest 248 Participation record
yukicoder contest 270 (mathematics contest) Participation record
yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 175 Virtual entry