Résolu d'un problème à un problème O. Cependant, beaucoup d'entre eux se référaient aux codes d'autres personnes ou faisaient des recherches sur Google. Puisque le code qui est devenu AC est affiché presque tel quel, je pense qu'il y a une description inutile etc. .. ..
A S'il s'agit d'une chaîne de caractères, il génère une erreur. Facile à essayer.
#A
try:
print(int(input()) * 2)
except:
print('error')
B Qu'il ait augmenté ou diminué ou non est classé par cas. Écrivez-le honnêtement.
# 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 Triez et prenez le troisième.
# C
data = sorted(list(map(int, input().split())), reverse=True)
print(data[2])
D Comparez l'ensemble de $ 1 \ sim N $ avec le contenu obtenu à partir de l'entrée standard. Le seul élément de l'ensemble de différences a été réécrit et a disparu, et celui avec le plus grand nombre (deux cette fois) a été réécrit et augmenté.
# 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 Créez une matrice qui stocke les relations de suivi entre les utilisateurs et définissez les valeurs initiales de tous les éléments sur «N». Après cela, vous pouvez simplement mettre à jour la matrice en fonction de l'entrée.
# 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 Le mot est extrait en enregistrant l'index contenant des lettres majuscules et en le divisant en nombres pairs. Après cela, il peut être trié de manière appropriée.
# 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 Puisque le nombre de personnes et le nombre de groupes sont petits (3 $ ^ {10} $ modèle car 10 personnes sont 3 groupes), il est possible d'évaluer tous les modèles.
# 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 Le montant du calcul est réduit en conservant la valeur minimale du nombre restant de cartes dans le nombre impair et la valeur minimale du nombre restant de cartes dans toutes les cartes. Lorsque la requête 1 arrive, réduisez le nombre de cartes correspondantes et mettez à jour chacune si nécessaire par rapport au minimum enregistré. Lorsque la requête 2 arrive, soustrayez le nombre de ventes à la valeur minimale du nombre impair actuel. La requête 3 peut le faire pour le nombre minimum de toutes les cartes.
# 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 Créez un état en considérant l'état d'avoir ou non une partie comme un bit. On suppose que l'état initial n'a rien (toutes les chaînes de 0 bits), et chaque fois qu'un achat est effectué, une opération OU avec la chaîne de bits correspondant au produit est effectuée et les transitions d'état. Le fait d'effectuer ou non une transition est effectué lorsque le coût total d'un nouvel achat à partir de l'état actuel est comparé au coût enregistré à la destination de transition et que le nouvel achat est moins cher.
# 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 Calculez l'itinéraire le plus court à partir du coin inférieur gauche, du coin inférieur droit et du coin supérieur droit jusqu'à un certain carré et son coût, et soustrayez le coût de l'itinéraire doublé. Faites cela pour toutes les cellules et le minimum est la réponse. Nous avons utilisé scipy pour calculer l'itinéraire le plus court. A cette époque, il était nécessaire de préparer une matrice adjacente, donc elle était facilement créée sur place. (J'ai l'impression qu'il existe une bibliothèque qui crée des matrices adjacentes ...)
# 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 Effectuez une recherche de priorité de profondeur. À ce moment-là, comptez le nombre de nœuds descendants du sous-arbre enraciné à chaque nœud de boss. Dans le tableau dans lequel les nœuds sont enregistrés par la recherche de priorité de profondeur, ils sont enregistrés comme [..., racine, nœud descendant de sous-arbre, autre route, ...]. Il suffit donc de juger s'il existe un index de l'employé qui veut juger s'il est un subordonné ou non entre [index patron, index patron + nombre de nœuds descendants du sous-arbre].
# 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:
#Effectuer une recherche de priorité en profondeur
def __init__(self, connections):
"""
connection：
* [from, to]Tableau avec éléments
*from est la source de la connexion, à est la destination de la connexion
*racine vers est-1 (spécification)
"""
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:
#Si b est le parent, la recherche de priorité de profondeur est effectuée, de sorte que la structure qui stocke le nœud recherché
#position de b(lob_c)De loc entre b descendant_Il devrait y avoir un
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 Le nombre de petites tours étant petit (5), il suffit de créer un arbre de spannning minimum pour tous les motifs (120 voies) qui peuvent passer à travers les petites tours et obtenir le coût minimum.
# 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 Ceci est la vidéo de commentaire telle quelle. Monster $ N $ Ajouter 1 monstre d'aide à votre corps Trouvez le meilleur pour toutes les combinaisons avec la recherche binaire.
# 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 Lorsque la requête $ (l, r, p) $ arrive, la requête est divisée en deux événements $ (l, p), (r + c, -p) $, chacun des coordonnées $ 0 $ à $ W $. Exécutez tout en recevant l'événement. L'événement $ (a, b) $ signifie que le coût augmente de $ b $ aux positions supérieures à la coordonnée $ a $. Cela permet $ l \ leq w \ leq r + c $ lors du passage de la voiture par $ (w-c, w) $ Si c'est le cas, cela coûte la préparation du terrain. À partir de là, les événements sont triés par ordre croissant de coordonnées, et chaque événement s'exécute jusqu'aux coordonnées $ W $ pour trouver la plus petite.
# 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 C'était assez impressionnant. Les deux articles suivants sont pour référence.
https://atcoder.jp/contests/past201912-open/submissions/12871791 https://rsk0315.hatenablog.com/entry/2019/12/29/051900
Sur la base des yeux obtenus en lançant les dés, envisagez une stratégie pour sélectionner les dés avec la valeur maximale attendue du nombre de fois qui peuvent être lancés plus tard. Il est formulé comme suit. Si vous lancez un dé et obtenez un jet de $ X $, le nombre prévu de fois que vous pouvez lancer $ n_X $ est
n_X = \frac{1}{6}\left(1 + \max_d E_{Y_d}\left[n_{Y_d}\delta(Y_d \gt X)\right]\right).
Ici, $ d $ est une variable qui indique quels dés, et $ Y_d $ est une variable de probabilité qui correspond au résultat des dés $ d $. Quant au sentiment de cela
Mettez ce sentiment dans le code.
# 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)
# (Au moment de chaque boucle)Valeur de jet attendue de chaque dé
Exp_dices = [0] * N
# (Au moment de chaque boucle)Nombre maximum attendu de rouleaux
max_Exp = 0
for eye in sorted_eyes:
#N pour œil œil_Calculer X
#Puisque l'ordre correspond à la taille des yeux, la valeur maximale attendue à ce moment-là est max._Devenez 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))
J'ai eu l'impression d'avoir terminé la course (je voulais le dire), mais je n'ai pu la résoudre moi-même qu'à moitié environ, alors j'ai pensé que je devrais faire plus d'ici le 3ème test à la fin du mois. .. ..
Recommended Posts