AtCoder ABC164 Ceci est un résumé des problèmes de AtCoderBeginnerContest164 qui s'est tenu le 26/04/2020 (dim) dans l'ordre du problème A, en tenant compte de la considération. La seconde partie traite du problème du DEF (seul D est correctement résumé en raison des contraintes de temps). Cliquez ici pour le premier semestre. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Soit une chaîne $ S $ constituée uniquement de nombres de "1" à "9". Un ensemble d'entiers qui satisfont les conditions suivantes
(i,j) (1 \leq i \leq j \leq |S|) Trouvez le nombre total de fichiers. Condition: Si vous regardez les caractères $ i $ à $ j $ de $ S $ comme des entiers de base $ 10 $, cet entier est un multiple de $ 2019 $.
Au début, je pensais que la contrainte était $ (1 \ leq S \ leq 200000) $, donc j'étais honnêtement TLE. Le problème jusqu'à C a été résolu à un rythme plus rapide que d'habitude, donc je l'ai interprété convenablement. Je suis sorti de TLE, j'ai relu le problème et j'ai été déçu.
(1 \leq |S| \leq 200000)
Je ne peux pas venir à temps ... Après cela, je suis allé voir les problèmes E et F et j'ai décidé d'utiliser les 90 minutes restantes pour ce problème, mais je n'ai pas pu le résoudre. En regardant sur Twitter après avoir terminé, il semble que ce soit un sujet similaire du problème ABC158 E. Après tout, j'étais parfaitement conscient que la croissance ne peut être attendue sans résoudre des problèmes qui ne pourraient pas être résolus fermement (les gens ordinaires n'ont pas d'autre choix que de poser des questions passées et de pouvoir résoudre des problèmes similaires, n'est-ce pas?). J'ai essayé de lire les explications et de rédiger un article en examinant les problèmes du passé, mais le 28 avril, @ Seika139 a déclaré: "[problème ABC164 D qui peut être compris même avec quelques chiffres (calcul du surplus)](https: // J'ai posté un article intitulé "qiita.com/Seika139/items/8cacdb3cc8fa6655573c)" et j'ai doucement effacé ce que j'écrivais. S'il y a un article aussi cohérent, je ne peux plus l'écrire (sueur) J'ai également appris de cet article comme référence. Pour le moment, j'ai soumis le code en référence à celui publié dans "problème ABC164 D qui peut être compris même avec quelques chiffres (calcul du surplus)".
abc164d.py
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
current = (current + x * int(s)) % 2019
ans += mods[current % 2019]
mods[current % 2019] += 1
x = x * 10 % 2019
print(ans)
Personnellement, je ne savais pas que les combinaisons pouvaient être calculées avec ʻans + = mods [current% 2019] `, alors j'ai appris. Fondamentalement, il est nécessaire de compter le nombre de combinaisons où $ D [j] = D [i] $ décrit dans l'article référencé, mais je calculerai après que $ n $ soit décidé. Je savais seulement comment le faire.
Par exemple, $ i $ avec $ D [i] = 5 $ a été trouvé jusqu'à présent, et $ j (i \ not = j) $ avec $ D [j] = 5 $ a été nouvellement trouvé. Quand
{}_{m+1} C _2 = {}_m C _2 + m
Par conséquent, il peut être calculé en ajoutant $ m $ ... J'avais honte de dire que je ne savais pas. Vous n'avez plus à calculer $ {} _n C _2 $ après avoir terminé le calcul.
J'avais l'impression de ne pas l'avoir écrit dans l'article auquel je faisais référence, alors j'aimerais l'écrire un peu, mais c'est à propos de la raison pour laquelle mods [0] = 1.
C'est à peu près quand $ D [i] = 0 $.
Dans l'exemple donné dans l'article référencé, $ D [i] = 0 $ n'apparaît pas, donc je voudrais terminer le problème D avec deux exemples.
L'exemple d'entrée 1 est quand $ S = 18171 $. À ce stade, $ D [i] $ commence à partir de $ i = 0 $.
L'exemple d'entrée 2 est pour $ S = 1817118171 $. À ce stade, $ D [i] $ commence à partir de $ i = 0 $.
Seul $ D [i] = 0 $ est spécial, même si vous ne choisissez pas $ D [i] = 0 $ et $ D [j] = 0 $ à deux endroits, seulement $ D [i] = 0 $ Les nombres sont différents parce qu'ils sont divisibles. Dans l'article dont j'ai parlé,
En supposant que le tableau réel $ D $ est $ N + 1 $ au lieu de $ N $ de longueur, préparez une salle vide avec $ D [N + 1] = 0 $. Cela a à voir avec le fait qu'il existe $ {} _ {N + 1} C_2 $ façons de choisir les index $ i, j $ qui coupent la chaîne $ S $.
Depuis qu'il a été écrit, je pense que cela correspond à ici, mais en ajoutant la partie qui n'a pas $ D [N + 1] = 0 $, $ D [N + 1] = 0 $ et $ D [i Choisir une combinaison de] = 0 $ correspond à choisir seulement $ D [i] = 0 $.
Cela permet de calculer, donc nous mettons mods [0] = 1 pour supposer qu'il y a $ D [N + 1] = 0 $ au début.
Dans le concours, je n'ai pas l'impression d'être aussi fou de mise en œuvre ...
Énoncé du problème Il y a des villes $ N $ numérotées de 1 $ à $ N $. Ces villes sont reliées par des lignes de chemin de fer de $ M $. Vous êtes actuellement dans la ville $ 1 $ avec des pièces d'or de 10 $ ^ {100} $ et des pièces d'argent $ S $. La $ i $ th ligne ferroviaire relie la ville $ U_i $ et la ville $ V_i $ dans les deux sens, le tarif aller simple est de $ A_i $ pièces d'argent et le trajet dure $ B_i $ minutes. Le tarif ne peut pas être payé en pièces d'or. Chaque ville dispose d'un bureau de change où vous pouvez échanger des pièces d'or de 1 $ contre des pièces d'argent $ C_i $ au bureau de change $ i $. L'échange coûte $ D_i $ par pièce d'or de 1 $. Vous pouvez échanger autant de pièces d'or que vous le souhaitez à chaque échange. Pour $ t = 2, ..., N $, trouvez le temps minimum nécessaire pour passer de la ville $ 1 $ à la ville $ t $. Vous pouvez ignorer le temps qu'il faut pour attendre le train.
Cela semblait être un problème d'application de la méthode dijkstra, mais je ne suis même pas habitué à la simple mise en œuvre de la méthode dijkstra en premier lieu, donc je pense que je dois étudier ce domaine à partir de zéro. Parmi le code soumis, je me suis référé à Code de Kiri8128 qui a été le premier AC-passé avec python. @ kiri8128
abc164e.py
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
u, v, a, b = map(int, input().split())
u, v = u-1, v-1
for i in range(a, k):
X[u * k + i].append([v * k + i - a, b])
X[v * k + i].append([u * k + i - a, b])
for i in range(N):
c, d = map(int, input().split())
for j in range(k - 1):
X[i * k + j].append([i * k + min(j + c, k - 1), d])
def dijkstra(n, E, i0=0):
h = [[0, i0]]
D = [-1] * n
done = [0] * n
D[i0] = 0
while h:
d, i = hpop(h)
done[i] = 1
for j, w in E[i]:
nd = d + w
if D[j] < 0 or D[j] > nd:
if done[j] == 0:
hpush(h, [nd, j])
D[j] = nd
return D
D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")
Je manque encore d'études, alors j'aimerais étudier lentement ici.
Énoncé du problème Soit un tableau $ S, T, U, V $ d'entier $ N $ et de longueur $ N $. Construisez une matrice $ 1 $ de $ N × N $ qui remplit les conditions suivantes. ・ $ A_ {i, j} $ est un entier. ・ $ 0 \ leq a_ {i, j} \ leq 2 ^ {64} $ ・ Quand $ S_i = 0 $, le produit logique des éléments sur la ligne $ i $ est $ U_i $. ・ Lorsque $ S_i = 1 $, le produit logique des éléments sur la ligne $ i $ est $ U_i $. ・ Lorsque $ S_i = 0 $, le produit logique de chaque élément de la colonne $ i $ est $ V_i $. ・ Lorsque $ S_i = 1 $, le produit logique de chaque élément de la colonne $ i $ est $ V_i $. Cependant, dans certains cas, aucune matrice ne remplit les conditions.
Actuellement, ni D ni E n'ont été résolus, donc je vais réessayer un jour (sueur) Tout d'abord, je dois partir régulièrement de l'endroit où cela semble être résolu.
Il semble qu'il n'est pas possible d'organiser correctement E et F à chaque fois. J'espère pouvoir recommencer quand j'aurai le temps. Merci d'avoir lu la seconde moitié jusqu'à la fin.
Recommended Posts