Gelöst von A-Problem zu O-Problem. Viele von ihnen bezogen sich jedoch auf die Codes anderer Leute oder googelten. Da der Code, der zu AC wurde, fast so veröffentlicht wird, wie er ist, denke ich, dass es eine nutzlose Beschreibung usw. gibt. .. ..
A Wenn es sich um eine Zeichenfolge handelt, wird ein Fehler ausgegeben. Einfach mit versuchen.
#A
try:
print(int(input()) * 2)
except:
print('error')
B Ob es zugenommen oder abgenommen hat, wird von Fall zu Fall klassifiziert. Schreib es einfach ehrlich.
# B
N = int(input())
A_last = int(input())
for i in range(N-1):
A = int(input())
if A_last == A:
print('stay')
elif A_last > A:
print('down {}'.format(A_last - A))
elif A_last < A:
print('up {}'.format(A - A_last))
A_last = A
C Einfach sortieren und den dritten abholen.
# C
data = sorted(list(map(int, input().split())), reverse=True)
print(data[2])
D Vergleichen Sie die Menge von $ 1 \ sim N $ mit dem Inhalt der Standardeingabe. Das einzige Element des Differenzsatzes wurde umgeschrieben und ist verschwunden, und das mit der größten Anzahl (diesmal zwei) wurde umgeschrieben und vergrößert.
# D
N = int(input())
arr = {i+1 for i in range(N)}
As = [int(input()) for i in range(N)]
import collections
d = dict(collections.Counter(As))
try:
removed = list(arr - set(d.keys()))[0]
added = max(d.keys(), key=lambda k: d[k])
print(added, removed)
except:
print('Correct')
E Erstellen Sie eine Matrix, in der die folgenden Beziehungen zwischen Benutzern gespeichert sind, und setzen Sie die Anfangswerte aller Elemente auf 'N'. Danach können Sie die Matrix einfach entsprechend der Eingabe aktualisieren.
# E
N, Q = list(map(int, input().split()))
Ss = [input().split() for i in range(Q)]
mat = {str(i+1):{str(j+1): 'N' for j in range(N)} for i in range(N)}
for q in range(Q):
inp = Ss[q]
if inp[0] == '1':
mat[inp[1]][inp[2]] = 'Y'
elif inp[0] == '2':
users = [user for user in mat.keys() if mat[user][inp[1]] == 'Y']
for user in users:
mat[inp[1]][user] = 'Y'
else:
follows = [user for user in mat[inp[1]].keys() if mat[inp[1]][user] == 'Y']
follow_targets = set([])
for follow in follows:
follow_targets |= set([user for user in mat[follow].keys() if mat[follow][user] == 'Y'])
for target in follow_targets:
mat[inp[1]][target] = 'Y'
for i in range(N):
mat[str(i+1)][str(i+1)] = 'N'
print(''.join([mat[str(i+1)][str(j+1)] for j in range(N)]))
F Das Wort wird extrahiert, indem der Index mit Großbuchstaben aufgezeichnet und in gerade Zahlen unterteilt wird. Danach kann es entsprechend sortiert werden.
# F
S = input()
ids = [i for i in range(len(S)) if S[i].isupper()]
N = len(ids)
strs = [S[ids[n]:ids[n+1]+1] for n in range(0, N, 2)]
sorted_strs = sorted(strs, key=lambda s: s.lower())
print(''.join(sorted_strs))
G Da die Anzahl der Personen und die Anzahl der Gruppen gering sind ($ 3 ^ {10} $ Muster, da 10 Personen 3 Gruppen sind), können alle Muster ausgewertet werden.
# G
N = int(input())
As = [list(map(int, input().split())) for i in range(N-1)]
import itertools
d = {'{}:{}'.format(elem[0], elem[1]): As[elem[0]][elem[1] - elem[0] - 1] for elem in itertools.combinations(range(N), 2)}
g_size = 3
def div_to_groups(comb):
return [[i for i in range(N) if comb[i] == g+1] for g in range(g_size)]
combs = list(itertools.product(range(1, g_size+1), repeat=N))
combs = map(div_to_groups, combs)
def sumup_group_happiness(group):
def get_happiness(pair):
return d['{}:{}'.format(pair[0], pair[1])]
return sum(map(get_happiness, itertools.combinations(group, 2)))
def sumup_all_groups(comb):
return sum(map(sumup_group_happiness, comb))
print(max(map(sumup_all_groups, combs)))
H Der Rechenaufwand wird reduziert, indem der Mindestwert der verbleibenden Anzahl von Karten in der ungeraden Anzahl und der Mindestwert der verbleibenden Anzahl von Karten in allen Karten gehalten werden. Wenn Abfrage 1 eingeht, reduzieren Sie die Anzahl der entsprechenden Karten und aktualisieren Sie sie bei Bedarf im Vergleich zum aufgezeichneten Minimum. Wenn Abfrage 2 kommt, subtrahieren Sie die Anzahl der Verkäufe vom Mindestwert der aktuellen ungeraden Zahl. Abfrage 3 kann dies für die Mindestanzahl aller Karten tun.
# H
N = int(input())
Cs = {i+1:v for i, v in zip(range(N), map(int, input().split()))}
Q = int(input())
Ss = [list(map(int, input().split())) for i in range(Q)]
sold = 0
min_all, min_odd = min(Cs.values()), min(list(Cs.values())[::2])
sub_all, sub_odd = 0, 0
for s in Ss:
if s[0] == 1:
sell = s[2]
if s[1] % 2 == 0 and Cs[s[1]] - sub_all >= sell:
Cs[s[1]] -= sell
sold += sell
min_all = min(min_all, Cs[s[1]] - sub_all)
elif Cs[s[1]] - sub_odd >= sell:
Cs[s[1]] -= sell
sold += sell
min_odd = min(min_odd, Cs[s[1]] - sub_odd)
min_all = min(min_all, min_odd)
elif s[0] == 2:
sell = s[1]
if min_odd >= sell:
min_odd -= sell
sub_odd += sell
min_all = min(min_all, min_odd)
sold += sell * int((N+1)/2)
else:
sell = s[1]
if min_all >= sell:
min_all -= sell
sub_all += sell
min_odd -= sell
sub_odd += sell
sold += sell * N
print(sold)
I Erstellen Sie einen Status, indem Sie den Status, ein Teil zu haben oder nicht zu haben, als Bit betrachten. Es wird angenommen, dass der Anfangszustand nichts enthält (alle 0-Bit-Zeichenfolgen), und jedes Mal, wenn ein Kauf getätigt wird, wird eine ODER-Verknüpfung mit der dem Produkt entsprechenden Bitfolge ausgeführt und der Status wechselt. Es wird entschieden, ob ein Übergang vorgenommen werden soll oder nicht, wenn die Gesamtkosten eines Neukaufs aus dem aktuellen Status mit den am Übergangsziel erfassten Kosten verglichen werden und der Neukauf billiger ist.
# I
N, M = list(map(int, input().split()))
SCs = [input().split() for i in range(M)]
SCs = [{'mask': int(sc[0].replace('Y', '1').replace('N', '0'), 2), 'price': int(sc[1])} for sc in SCs]
size = 1 << N
max_price = sum([p['price'] for p in SCs]) + 1
price = {}
price[0] = 0
for i in range(size):
if i in price.keys():
for sc in SCs:
price[i | sc['mask']] = min(price.get(i | sc['mask'], max_price), price[i] + sc['price'])
print(price.get(size-1, -1))
J Berechnen Sie die kürzeste Route von der unteren linken Ecke, der unteren rechten Ecke und der oberen rechten Ecke bis zu einem bestimmten Quadrat und dessen Kosten und subtrahieren Sie die Kosten der doppelten Route. Tun Sie dies für alle Zellen und das Minimum ist die Antwort. Wir haben scipy verwendet, um die kürzeste Route zu berechnen. Zu dieser Zeit war es notwendig, eine benachbarte Matrix vorzubereiten, damit sie leicht vor Ort erstellt werden konnte. (Ich habe das Gefühl, dass es eine Bibliothek gibt, die benachbarte Matrizen erstellt ...)
# J
H, W = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np
def get_adj_matrix(A, H, W):
size = H * W
ret = [[10**9]* (size) for i in range(size)]
for i in range(size):
h_i = int(i / W)
w_i = i % W
for add in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
h_j = h_i + add[0]
w_j = w_i + add[1]
j = h_j * W + w_j
if h_j < 0 or h_j >= H or w_j < 0 or w_j >= W:
continue
else:
ret[i][j] = A[h_j][w_j]+1.0e-15 / size
return ret
csr = csgraph_from_dense(get_adj_matrix(A, H, W), null_value=10**9)
start = (H-1)*W
mid = H*W-1
end = W-1
from_start = dijkstra(csr, indices=[start])
from_mid = dijkstra(csr, indices=[mid])
from_end = dijkstra(csr, indices=[end])
double_counts = [-A[h][w]*2 for h in range(H) for w in range(W)]
arr = np.array([from_start, from_mid, from_end, double_counts])
print(int(arr.sum(axis=0).min()))
K Führen Sie eine Tiefenprioritätssuche durch. Zählen Sie zu diesem Zeitpunkt die Anzahl der Nachkommenknoten des Teilbaums, die an jedem Bossknoten verwurzelt sind. In dem Array, in dem die Knoten durch die Tiefenprioritätssuche aufgezeichnet werden, werden sie als [..., Wurzel, Teilbaum-Nachkommenknoten, eine andere Route, ...] aufgezeichnet. Daher ist es ausreichend zu beurteilen, ob es einen Index des Mitarbeiters gibt, der beurteilen möchte, ob es sich um einen Untergebenen zwischen [Chefindex, Chefindex + Anzahl der Nachkommenknoten des Teilbaums] handelt oder nicht.
# K
N = int(input())
connections = [[i+1, int(input())] for i in range(N)]
Q = int(input())
ABs = [list(map(int, input().split())) for i in range(Q)]
import sys
sys.setrecursionlimit(10**6)
class tree:
#Führen Sie eine Tiefenprioritätssuche durch
def __init__(self, connections):
"""
connection：
* [from, to]Array mit Elementen
*Von ist die Verbindungsquelle, bis ist das Verbindungsziel
*Wurzel zu ist-1 (Spezifikation)
"""
self.parent_to_child = {i+1: [] for i in range(len(connections))}
for connection in connections:
if connection[1] == -1:
self.root = connection[0]
else:
self.parent_to_child[connection[1]].append(connection[0])
self.structure = []
self.nodeid_to_strucure_loc = {}
self.nodeid_to_num_descendant = {}
def compute_depth_first_sub_tree_from(self, parent):
before_counting_descendant = len(self.structure)
self.nodeid_to_strucure_loc[parent] = before_counting_descendant
self.structure.append(parent)
children = self.parent_to_child.get(parent, [])
for child in children:
self.compute_depth_first_sub_tree_from(child)
after_counting_descendant = len(self.structure)
self.nodeid_to_num_descendant[parent] = after_counting_descendant - before_counting_descendant
def compute_depth_first_tree(self):
self.compute_depth_first_sub_tree_from(self.root)
t = tree(connections)
t.compute_depth_first_tree()
for ab in ABs:
#Wenn b das übergeordnete Element ist, wird die Suche mit Tiefenpriorität durchgeführt, also die Struktur, in der der gesuchte Knoten gespeichert ist
#Position von b(lob_c)Von loc zwischen b Nachkommen_Es sollte eine geben
loc_a = t.nodeid_to_strucure_loc[ab[0]]
loc_b = t.nodeid_to_strucure_loc[ab[1]]
shift = t.nodeid_to_num_descendant[ab[1]]
print('Yes' if loc_b < loc_a < loc_b + shift else 'No')
L Da die Anzahl der kleinen Türme gering ist (5), reicht es aus, einen minimalen Spannbaum für alle Muster (120 Wege) zu erstellen, die durch die kleinen Türme verlaufen und die minimalen Kosten erzielen können.
# L
N, M = list(map(int, input().split()))
xycs = list([list(map(int, input().split())) for i in range(N)])
XYCs = list([list(map(int, input().split())) for i in range(M)])
import itertools
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
def compute_cost(x1, x2):
r = ((x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2) ** .5
return r if x1[2] == x2[2] else 10 * r
cases = []
for i in range(M+1):
cases.extend(itertools.combinations(XYCs, r=i))
res = 10**30
for case in cases:
data = xycs[:]
data.extend(case)
size = len(data)
cost_matrix = [[compute_cost(data[frm], data[to]) for to in range(size)] for frm in range(size)]
csr = csr_matrix(cost_matrix)
res = min(res, minimum_spanning_tree(csr).sum())
print('{:.10f}'.format(res))
M Dies ist das Kommentarvideo wie es ist. Monster $ N $ Fügen Sie Ihrem Körper 1 Hilfsmonster hinzu. Finden Sie mit Binary Search das Beste für alle Kombinationen.
# M
N, M = list(map(int, input().split()))
monsters = [list(map(int, input().split())) for i in range(N)]
helpers = [list(map(int, input().split())) for i in range(M)]
import numpy as np
def find_BS(X_lower, X_higher, eval_function, max_iter=100):
iter_num = 0
while iter_num <= max_iter:
X = (X_higher + X_lower) / 2
res = eval_function(X)
if not res: X_higher = X
else: X_lower = X
iter_num += 1
return X
def get_score(monsters):
np_arr_monsters = np.array(monsters)
A = np_arr_monsters.T[0]
B = np_arr_monsters.T[1]
def eval_func(X):
sorted_val = sorted(B - X * A)
upper = sorted_val[-5:]
return sum(upper) > 0
X_lower = 0
X_higher = max(monsters, key=lambda m: m[1])[1]
max_iter = 25
X = find_BS(X_lower, X_higher, eval_func, max_iter)
Y = B - X * A
targets = np.array(sorted(np.array([A, B, Y]).T, key=lambda a: a[2])[-5:]).T
return sum(targets[1]) / sum(targets[0])
scores = [get_score(monsters + [helper]) for helper in helpers]
print('{:.10f}'.format(max(scores)))
N Wenn die Abfrage $ (l, r, p) $ eintrifft, wird die Abfrage in zwei Ereignisse $ (l, p), (r + c, -p) $ aufgeteilt, die jeweils von den Koordinaten $ 0 $ bis $ W $ reichen. Wird ausgeführt, während das Ereignis empfangen wird. Das Ereignis $ (a, b) $ bedeutet, dass sich die Kosten an Positionen, die größer als die Koordinate $ a $ sind, um $ b $ erhöhen. Dies ermöglicht $ l \ leq w \ leq r + c $, wenn das Auto durch $ (w-c, w) $ gefahren wird Wenn ja, kostet es die Landvorbereitung. Daraus werden die Ereignisse in aufsteigender Reihenfolge der Koordinaten sortiert, und jedes Ereignis läuft zu den Koordinaten $ W $, um das kleinste zu finden.
# N
n, w, c = list(map(int, input().split()))
events = [[c, 0]]
for i in range(n):
l, r, p = list(map(int, input().split()))
events.extend([[l, p], [r+c, -p]])
events.sort()
ans = 10**100
cost = 0
for loc, price in events:
if loc > w:
break
cost += price
if c <= loc:
ans = min(ans, cost)
print(ans)
O Das war ziemlich beeindruckend. Die folgenden zwei Artikel dienen als Referenz.
https://atcoder.jp/contests/past201912-open/submissions/12871791 https://rsk0315.hatenablog.com/entry/2019/12/29/051900
Überlegen Sie anhand der Augen, die durch das Würfeln erhalten wurden, eine Strategie, um die Würfel mit dem maximal erwarteten Wert für die Häufigkeit auszuwählen, mit der später gewürfelt werden kann. Es ist wie folgt formuliert. Wenn Sie würfeln und einen $ X $ -Wurf erhalten, können Sie voraussichtlich $ n_X $ würfeln
n_X = \frac{1}{6}\left(1 + \max_d E_{Y_d}\left[n_{Y_d}\delta(Y_d \gt X)\right]\right).
Hier ist $ d $ eine Variable, die angibt, welche Würfel verwendet werden, und $ Y_d $ ist eine Wahrscheinlichkeitsvariable, die dem Ergebnis der Würfel $ d $ entspricht. Was das Gefühl betrifft
Setzen Sie dieses Gefühl in den Code ein.
# O
N = int(input())
dice_eyes = []
for dice in range(N):
dice_eyes.extend([{'eye_value': dice_eye, 'dice_id': dice} for dice_eye in map(int, input().split())])
sorted_eyes = sorted(dice_eyes, key=lambda eye: eye['eye_value'], reverse=True)
# (Zum Zeitpunkt jeder Schleife)Erwarteter Wurfwert jedes Würfels
Exp_dices = [0] * N
# (Zum Zeitpunkt jeder Schleife)Maximal erwartete Anzahl von Rollen
max_Exp = 0
for eye in sorted_eyes:
#N für Auge Auge_Berechne X.
#Da die Reihenfolge der Größe der Augen entspricht, beträgt der maximal erwartete Wert zu diesem Zeitpunkt max._Werden Sie Exp
exp_length_of_eye = (1 + max_Exp) / 6.
Exp_dices[eye['dice_id']] += exp_length_of_eye
max_Exp = max(max_Exp, Exp_dices[eye['dice_id']])
print('{:.10f}'.format(max_Exp + 1))
Es war ein Eindruck, dass ich das Rennen beendet habe (ich wollte es sagen), aber ich konnte es nur etwa zur Hälfte selbst lösen, also dachte ich, dass ich bis zum 3. Test Ende des Monats mehr tun sollte. .. ..
Recommended Posts