Ceci est un article de synthèse pour les débutants des professionnels de la compétition. Cliquez ici pour les concours auxquels vous avez participé. https://atcoder.jp/contests/panasonic2020
Le code que j'écris ici est écrit en regardant les réponses et les explications des autres. Il n'a pas été réellement soumis.
A - Kth Term C'est un problème de sortir le nième terme de l'entrée donnée à partir d'une séquence de nombres prédéterminée.
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
i = int(input())
print(li[i-1])
Notez que les numéros d'articles sont comptés à partir de 1.
B - Bishop $ H \ times W $ C'est une question pour répondre à la plage où le coin peut se déplacer sur le plateau du carré.
Veuillez noter que le coin ne peut pas bouger même d'un pas lorsqu'il n'y a qu'une seule taille horizontale ou verticale (une perte).
Le code que j'ai soumis ressemble à ceci.
import math
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
w_odd = math.ceil(H/2)
w_even = H // 2
N_odd = math.ceil(W/2)
N_even = W // 2
print(w_odd * N_odd + w_even * N_even)
En comptant les carrés horizontaux à partir de la gauche, le nombre de carrés mobiles diffère entre le temps pair et le temps impair. Le nombre de cellules dans ces deux cas et le nombre de colonnes correspondant à chacune ont été calculés séparément.
Vous pouvez en fait l'écrire de manière plus concise.
La moitié seulement de tous les carrés sont mobiles. S'il y a un reste divisé par 2, la cellule inférieure droite qui est le reste est toujours en position (impair, impair). Puisqu'il s'agit d'une position mobile, elle augmentera d'un carré de plus.
H, W = map(int, input().split())
if H == 1 or W == 1:
print(1)
else:
print((H * W + 1) // 2)
De plus, il n'est pas nécessaire d'importer des mathématiques dans le processus de rafle.
C - Sqrt Inequality Pour l'entrée A B C
Le problème de déterminer si.
J'ai soumis ce qui suit, pensant que ce serait inutile.
a, b, c = map(int, input().split())
if a**0.5 + b**0.5 < c**0.5:
print("Yes")
else:
print("No")
C'était mauvais. Vous ne pouvez même pas utiliser les mathématiques.
Mettons au carré les deux côtés de l'équation (1).
J'ai vu le commentaire. (2) est encore transformée.
Lorsque les deux côtés sont positifs, mettez les deux côtés au carré
Donc la réponse. Cela aurait dû être remarqué car cela ne devrait pas être difficile.
a, b, c = map(int, input().split())
if 0 < c - a - b and 4 * a * b < (c - a - b)**2:
print("Yes")
else:
print("No")
D - String Equivalence
Le problème est d'organiser tous les modèles de chaînes de caractères qui existent avec le nombre de caractères N (≤10).
Je ne savais pas comment faire, alors j'ai essayé de le résoudre en arrangeant tous les motifs une fois, puis en les effaçant. En fait, j'étais coincé au milieu de l'écriture et je ne pouvais pas le soumettre, mais j'ai écrit le code suivant.
import itertools
N = int(input())
alp = [chr(ord('a') + i) for i in range(N)]
allS = list(itertools.product(alp, repeat=N))
answers = []
PatternList = []
for s in allS:
pattern = []
letters = []
for l in s:
if not l in letters:
letters.append(l)
pattern.append(letters.index(l))
if not pattern in PatternList:
PatternList.append(pattern)
answers.append(s)
for answer in answers:
print(''.join(answer))
Je pensais qu'il serait possible d'atteindre N = 10, mais TLE est sorti en seconde période.
J'ai vu le commentaire. La condition de forme standard est remplacée par la formule suivante.
Il semble que vous deviez effectuer une recherche avec DFS pour satisfaire ces deux conditions. Les informations de valeur maximale sont stockées dans la variable mx qui contient les informations de valeur maximale et sont transmises par une fonction récursive.
Ce qui suit est fait selon l'échantillon.
n = int(input())
def dfs(s, mx):
if len(s) == n:
print(s)
else:
for i in range(0, mx + 1):
c = chr(ord('a') + i)
if i == mx: dfs(s+c, mx+1)
else: dfs(s+c, mx)
dfs('', 0)
E - Three Substrings Compte tenu des trois sous-chaînes a, b et c tirées de la chaîne s, c'est le problème de deviner la chaîne d'origine s.
J'ai préparé un tableau vide avec la longueur de a + b + c comme chaîne de caractères s, et j'ai commencé à écrire avec la politique d'appliquer les trois de a, b et c d'une extrémité, mais certains éléments restent bloqués. J'ai abandonné parce que j'ai vu TLE sortir.
J'ai vu le commentaire. Obtenez les "positions relatives" qui peuvent exister pour chacun de a et b, b et c, et a et c sous forme de tableau. Stockez-le sous ```ab [] `,` `ʻac []`, `bc []`. À partir de là, si la relation positionnelle entre a et b est représentée par i '' et la relation positionnelle entre a et c est représentée par j '', la relation positionnelle entre b et c est obtenue par `` ji ''. Je peux le faire.
Cela transforme i et `j```, et` `ʻab [i]` `ʻet` `ʻac [j]`, `` `bc [ji] ] ```Il peut être obtenu en calculant le nombre de caractères lorsque les trois conditions sont remplies. Notez que a, b et c peuvent être jusqu'à $ \ pm 4000 $ respectivement.
Je viens de réécrire la plupart des explications en Python, mais le code suivant est passé. Même avec Pypy3, cet algorithme claque et le temps n'est que de 1991 ms. Par exemple, mettez simplement `True``` et` Falsedansab [] `` `au lieu de 1 et 0 pour obtenir TLE. Il semble y avoir une méthode plus rapide (je ne l'ai pas encore vue), car certaines personnes obtiennent un temps de calcul plusieurs fois plus rapide et d'autres le font en Python.
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000
for i in range(A):
if a[i] == '?':
continue
for j in range(B):
if b[j] != '?' and a[i] != b[j]:
ab[i-j+8000]= 0
for i in range(B):
if b[i] == '?':
continue
for j in range(C):
if c[j] != '?' and b[i] != c[j]:
bc[i-j+8000]= 0
for i in range(A):
if a[i] == '?':
continue
for j in range(C):
if c[j] != '?' and a[i] != c[j]:
ac[i-j+8000]= 0
ans = 6000
for i in range(-4000, 4000):
for j in range(-4000, 4000):
if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
L = min(0, min(i, j))
R = max(A, max(B+i, C+j))
ans = min(ans, R-L)
print(ans)
C'est tout pour cet article. Si possible, j'aimerais ajouter la question F plus tard.
Recommended Posts