J'ai finalement eu un peu de temps, alors j'ai essayé la participation virtuelle à PAST. Le résultat était de 64 points, donc c'était intermédiaire (60-79 points). Contrairement au jeu mathématique et inspirant habituel d'AtCoder, l'implémentation est quelque chose Il y avait beaucoup de problèmes qui semblaient subtilement gênants, et je sentais que la couleur des cheveux était un peu différente.
Rompre dans 3 minutes et demie. Vérifiez s'il ne s'agit que d'un nombre et, s'il est correct, convertissez-le en int et affichez-le au double.
S = input()
for i in range(3):
if S[i] not in '0123456789':
print('error')
exit()
print(int(S) * 2)
Percer en 7 minutes. Il suffit de comparer avec la valeur et la sortie précédentes.
N = int(input())
A = [int(input()) for _ in range(N)]
prev = A[0]
for i in range(1, N):
if A[i] == prev:
print('stay')
elif A[i] < prev:
print('down %d' % (prev - A[i]))
elif A[i] > prev:
print('up %d' % (A[i] - prev))
prev = A[i]
Passez en 2 minutes. Triez simplement par ordre décroissant et sortez la troisième valeur par l'avant.
ABCDEF = list(map(int, input().split()))
ABCDEF.sort(reverse=True)
print(ABCDEF[2])
Faites une percée en 11 minutes. Il vous suffit de compter le nombre d'apparitions dans le dictionnaire, d'identifier 0 et 2 choses, et de sortir.
N = int(input())
A = [int(input()) for _ in range(N)]
t = set(A)
if len(t) == N:
print('Correct')
exit()
d = {}
for i in range(N):
if A[i] in d:
d[A[i]] += 1
else:
d[A[i]] = 1
for i in range(1, N + 1):
if i not in d:
x = i
elif d[i] == 2:
y = i
print(y, x)
Percée en 24 minutes. La mise en œuvre du suivi de suivi a également ajouté les utilisateurs qui suivent le suivi qui ont augmenté au cours du traitement, et il a fallu du temps pour que l'exemple d'entrée 1 ne réussisse pas. L'exemple d'entrée 1 l'a détecté. Je pense que cela aurait pris plus de temps si vous ne l'aviez pas fait.
N, Q = map(int, input().split())
t = [['N'] * N for _ in range(N)]
for _ in range(Q):
S = input()
if S[0] == '1':
_, a, b = map(int, S.split())
t[a - 1][b - 1] = 'Y'
elif S[0] == '2':
_, a = map(int, S.split())
for i in range(N):
if t[i][a - 1] == 'Y':
t[a - 1][i] = 'Y'
elif S[0] == '3':
_, a = map(int, S.split())
for i in [i for i in range(N) if t[a - 1][i] == 'Y']:
for j in range(N):
if t[i][j] == 'Y' and j != a - 1:
t[a - 1][j] = 'Y'
for i in range(N):
print(''.join(t[i]))
past201912F - DoubleCamelCase Sort
Il n'y a rien de particulièrement difficile, il suffit de découper les mots, de les trier par casse et de les combiner.
S = input()
t = []
start = -1
for i in range(len(S)):
if S[i].isupper():
if start == -1:
start = i
else:
t.append(S[start:i+1])
start = -1
t.sort(key=str.lower)
print(''.join(t))
Il a éclaté en 20 minutes, je pensais que je ne savais pas au début, mais quand j'ai regardé de près, je pouvais faire un round robin parce que N≤10. Ce n'était pas particulièrement difficile.
N = int(input())
a = [list(map(int, input().split())) for _ in range(N - 1)]
result = -float('inf')
t = [0] * N
for _ in range(3 ** N):
s = 0
for i in range(N):
for j in range(i + 1, N):
if t[i] == t[j]:
s += a[i][j - i - 1]
result = max(result, s)
for i in range(N):
if t[i] < 2:
t[i] += 1
break
t[i] = 0
print(result)
Il se produit en 44 minutes et demie. Il est inévitable que TLE reflète à la fois les ventes d'ensemble et tous les types de ventes dans le tableau en raison des restrictions. J'ai donc créé une variable cumulative pour chacune d'elles et l'ai transmise avec une politique de correspondance avec Tsuji. Il m'a fallu beaucoup de temps pour remarquer que ʻodd_min- = a` avait été divulgué.
N = int(input())
C = list(map(int, input().split()))
Q = int(input())
all_min = min(C)
odd_min = min(C[::2])
all_sale = 0
odd_sale = 0
ind_sale = 0
for _ in range(Q):
S = input()
if S[0] == '1':
_, x, a = map(int, S.split())
t = C[x - 1] - all_sale - a
if x % 2 == 1:
t -= odd_sale
if t >= 0:
ind_sale += a
C[x - 1] -= a
all_min = min(all_min, t)
if x % 2 == 1:
odd_min = min(odd_min, t)
elif S[0] == '2':
_, a = map(int, S.split())
if odd_min >= a:
odd_sale += a
odd_min -= a
all_min = min(odd_min, all_min)
elif S[0] == '3':
_, a = map(int, S.split())
if all_min >= a:
all_sale += a
all_min -= a
odd_min -= a
print(all_sale * N + odd_sale * ((N + 1) // 2) + ind_sale)
Il passe en 14 minutes. C'est DP, donc ce n'est pas particulièrement difficile. Il suffit de convertir Y en 1 et N en 0, qui est considéré comme un peu de chaque chiffre, puis DP.
N, M = map(int, input().split())
def conv(S):
result = 0
for c in S:
result *= 2
if c == 'Y':
result += 1
return result
dp = [-1] * 2001
dp[0] = 0
for _ in range(M):
S, C = input().split()
S = conv(S)
C = int(C)
for i in range(2000, -1, -1):
if dp[i] == -1:
continue
if dp[i | S] == -1 or dp[i | S] > dp[i] + C:
dp[i | S] = dp[i] + C
print(dp[(1 << N) - 1])
Je n'ai pas pu percer. Trouvez l'itinéraire le moins cher du coin inférieur gauche vers le coin inférieur droit avec DP, réécrivez l'endroit où je suis retourné en arrière jusqu'à 0, trouvez l'itinéraire le moins cher du coin inférieur droit vers le coin supérieur droit avec DP, et le coût de chacun J'ai essayé de faire une implémentation qui résume, mais environ la moitié WA.
Post-scriptum: résolu selon l'explication.
from heapq import heappop, heappush
INF = float('inf')
def cost_from(H, W, A, y0, x0):
dp = [[INF] * W for _ in range(H)]
dp[y0][x0] = 0
q = [(0, y0, x0)]
while q:
c, y, x = heappop(q)
t = dp[y][x]
if t != c:
continue
if y - 1 >= 0:
u = t + A[y - 1][x]
if dp[y - 1][x] > u:
dp[y - 1][x] = u
heappush(q, (u, y - 1, x))
if y + 1 < H:
u = t + A[y + 1][x]
if dp[y + 1][x] > u:
dp[y + 1][x] = t + A[y + 1][x]
heappush(q, (u, y + 1, x))
if x - 1 >= 0:
u = t + A[y][x - 1]
if dp[y][x - 1] > u:
dp[y][x - 1] = u
heappush(q, (u, y, x - 1))
if x + 1 < W:
u = t + A[y][x + 1]
if dp[y][x + 1] > u:
dp[y][x + 1] = u
heappush(q, (u, y, x + 1))
return dp
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
result = INF
cost1 = cost_from(H, W, A, H - 1, 0)
cost2 = cost_from(H, W, A, H - 1, W - 1)
cost3 = cost_from(H, W, A, 0, W - 1)
for i in range(H):
for j in range(W):
t = cost1[i][j] + cost2[i][j] + cost3[i][j] - 2 * A[i][j]
if t < result:
result = t
print(result)
Je ne pouvais pas percer, bien sûr, je pourrais écrire une implémentation naïve, mais je ne pouvais penser à aucun moyen de réduire la quantité de calcul.
Post-scriptum: J'ai appris la tournée des pétroliers et la climatisation.
N = int(input())
root = -1
children = [[] for _ in range(N + 1)]
left = [0] * (N + 1)
right = [0] * (N + 1)
for i in range(1, N + 1):
p = int(input())
if p == -1:
root = i
else:
children[p].append(i)
i = 0
s = [root]
while s:
n = s.pop()
if n > 0:
left[n] = i
i += 1
s.append(-n)
for c in children[n]:
s.append(c)
else:
right[-n] = i
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, input().split())
if left[b] < left[a] < right[b]:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
J'ai aussi essayé de le résoudre en doublant.
from math import log
from collections import deque
from sys import stdin
readline = stdin.readline
N = int(readline())
root = -1
children = [[] for _ in range(N + 1)]
parent = [[-1] * (N + 1) for _ in range(18)]
for i in range(1, N + 1):
p = int(readline())
parent[0][i] = p
if p == -1:
root = i
else:
children[p].append(i)
for i in range(1, 18):
parenti1 = parent[i - 1]
parenti = parent[i]
for j in range(1, N + 1):
t = parenti1[j]
if t == -1:
parenti[j] = -1
else:
parenti[j] = parenti1[t]
depth = [-1] * (N + 1)
q = deque([(root, 0)])
while q:
n, d = q.pop()
depth[n] = d
for c in children[n]:
q.append((c, d + 1))
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, readline().split())
if depth[a] <= depth[b]:
result.append('No')
continue
while depth[a] != depth[b]:
t = int(log(depth[a] - depth[b], 2))
a = parent[t][a]
if a == b:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
Recommended Posts