Résumé des problèmes d'AtCoder C qui peuvent être résolus en mathématiques au secondaire

Cet article est un article (16e jour) du Calendrier de l'Avent du Club Yugen 2019. ** Contient des spoilers sur la façon de résoudre le concours AtCoder Beginner. ** Veuillez faire attention lors de la lecture.

Vous ne pouvez devenir bleu clair qu'avec la puissance des mathématiques

C'est fujioka_math qui a participé 27 fois cet été. Je voulais ajouter du plaisir à ma vie, alors j'ai lancé AtCoder, ce que les gens autour de moi faisaient. graph.png Il est devenu bleu clair en environ 5 mois. (L'image date du 16/12. Le compte est fujioka_1115)

Il est devenu bleu clair, mais honnêtement, je ne connais pas du tout l'algorithme. J'ai l'impression d'avoir atteint la limite sans résoudre le problème ABC E en résolvant rapidement un problème qui peut être résolu simplement avec la puissance des mathématiques.

Pousser avec puissance mathématique

Les problèmes C et D d'ABC ont des problèmes qui peuvent être résolus même si vous n'êtes pas familier avec l'algorithme. Par exemple, quelque chose comme ça.

<détails>

Afficher le problème </ summary>
ABC144 D - Water Bottle ** [Résumé du problème] ** Un récipient rectangulaire avec un fond de $ a \ fois a $ et une hauteur de $ b $ contient $ x $ d'eau. Combien de fois le récipient peut-il être incliné (autour d'un côté du carré) sans débordement d'eau?

Afficher des exemples de réponses
C'est un problème complètement mathématique. Utilisez arctan, la fonction inverse de tan. Il est facile de diviser le cas par la taille de $ x $ et $ \ frac {a ^ 2b} 2 $. Arctan est-il un contenu universitaire? Cependant, étant donné que la propriété d'arctan n'est pas du tout utilisée ici et que la fonction inverse elle-même est le contenu de Math III, on suppose qu'il s'agit de mathématiques du secondaire. 
import math
a,b,x=[int(s) for s in input().split()]
if x>a*a*b/2:
  h=2*(a*a*b-x)/(a*a)
  print(math.degrees(math.atan(h/a)))
else:
  k=2*x/(a*b)
  print(math.degrees(math.atan(b/k)))

C'est un problème D mais n'utilise pas d'algorithme. Cette fois, nous présenterons des problèmes qui peuvent être facilement résolus si vous avez de telles compétences en mathématiques, de sorte que même les membres du club qui sont nouveaux dans la programmation devraient essayer de plus en plus.

Problème de cible

  • C problème après la 101ème du concours AtCoder pour débutants
  • La difficulté affichée dans AtCoder Problems est de 400 (marron) ou plus
  • Des choses qui ne peuvent être résolues que par les mathématiques du secondaire
  • Exclut les problèmes avec les opérations de chaîne, les sommes cumulées, etc.

Langue utilisée, notes

  • Utilisez Python.
  • Connaissance de la gestion des tableaux, instruction if, instruction for, etc. (C'est facile pour que vous puissiez l'apprendre tout de suite!)
  • Je n'ai pas trouvé toutes les réponses suivantes à première vue, et j'ai beaucoup appris des explications et des réponses des autres.
  • ** Je pense qu'il y a beaucoup de meilleures réponses que les exemples de réponses, veuillez donc les utiliser comme référence uniquement. ** **

Problème C

ABC101 C - Minimization

<détails>

Concept </ summary>
Si vous ne négligez pas l'énoncé du problème "$ A_1, A_2, \ dots, A_n $ est un réarrangement de $ 1, 2, \ dots, N $", le nombre entier de sections d'une longueur de $ K $ est suffisant. Pouvez-vous le couvrir? Je remarque que c'est un problème.

<détails>

Exemple de réponse </ summary> 

N,K=[int(s) for s in input().split()]
print((N+K-3)//(K-1))

Le nombre de sections requis est $ \ left \ lceil \ dfrac {N-1} {K-1} \ right \ rceil $. Ici, $ \ left \ lceil \ dfrac nm \ right \ rceil = \ left \ lfloor \ dfrac {n + m-1} n \ right \ rfloor $ est utilisé et la fonction de plafond n'est pas appelée. (J'ai également appris cette formule à partir de l'explication d'ABC.)

ABC105 C - Base -2 Number

<détails>

Concept </ summary>
C'est un développement du nombre de base $ n $ appris en Mathématiques I, donc il n'y a pas de quoi s'inquiéter. Le reste après la division peut être sorti dans l'ordre.

<détails>

Exemple de réponse </ summary> 

N=int(input())
ls=[]
while True:
  ls.append(N%2)
  N=-(N//2)
  if N==0:
    break
print(*reversed(ls),sep="")

La partie la plus difficile de ce problème était de sortir une liste de nombres comme [1,1,0,1] dans l'ordre inverse comme 1011 et de les connecter ensemble. Je vous ai déjà dit que vous pouvez facilement connecter et générer des listes avec print (* ls, sep = ""). Puis, en détail, j'ai perdu quand $ N = 0 $.

ABC108 C - Triangular Relationship

<détails>

Concept </ summary>
Utilisez l'idée du champ "entier" de Math A. Lorsque $ K $ est impair, $ a + b, b + c, c + a $ sont tous des multiples de $ K $, ce qui signifie que $ a, b, c $ sont tous des multiples de $ K $. Équivalent. Lorsque $ K $ est pair, "$ a, b, c $ sont tous des multiples de $ K $, ou $ a, b, c $ sont tous des multiples de $ \ frac K2 $ et non $ K $" Équivalent à. Par conséquent, dans chaque cas, le nombre de multiples doit être vérifié, mis au carré et ajouté.

<détails>

Exemple de réponse </ summary> 

N,K=[int(s) for s in input().split()]
if K%2==1:
  print((N//K)**3)
else:
  print((N//K)**3+((N//(K//2)-N//K)**3))

ABC109 C - Skip

<détails>

Concept </ summary>
Sortez les engagements maximum de $ x_1-X, x_2-X, \ dots, x_n-X $. Python a une fonction gcd qui trouve l'engagement maximum, mais AtCoder utilise gcd dans le module fractions au lieu du module math car la version Python est 3.4. Notez que cela peut renvoyer une valeur négative.

<détails>

Exemple de réponse </ summary> 

import fractions
N,X=[int(s) for s in input().split()]
ls=[int(s)-X for s in input().split()]
a=0
for e in ls:
  a=fractions.gcd(a,e)
print(abs(a))

ABC116 C - Grand Garden

<détails>

Concept </ summary>
Je ne savais pas comment le faire à première vue, mais ...

On voit que la somme des différences de hauteur (valeurs absolues) entre les fleurs adjacentes et le sol aux deux extrémités est le double du nombre de fois nécessaire pour l'arrosage. zu2.png

Plus simplement, ajoutez simplement la partie verte et vous aurez la réponse. Cela devrait être produit.

<détails>

Exemple de réponse </ summary> 

N=int(input())
ls=[int(s) for s in input().split()]
ls.append(0)
a=0
for i in range(N):
  a+=max([0,ls[i]-ls[i+1]])
print(a)

ABC117 C - Streamline

<détails>

Concept </ summary>
Si quoi que ce soit, la question de savoir si vous pouvez effectuer des opérations de base sur des tableaux. Si $ X_1 <X_2 <\ points <X_n $

  • Considérons la séquence de différence $ Y_n = X_ {n + 1} -X_n $
  • Supprimez les morceaux $ N-1 $ supérieurs de $ Y_1, \ dots, Y_n $
  • Vous pouvez afficher le total des autres.

Puisqu'il s'agit d'une séquence de nombres différentiels, est-ce math B?

<détails>

Exemple de réponse </ summary> 

N,M=[int(s) for s in input().split()]
if N>=M:
  print(0)
else:
  ls=[int(s) for s in input().split()]
  ls.sort()
  d=[ls[i+1]-ls[i] for i in range(M-1)]
  d.sort()
  print(sum(d[:M-N]))

La réponse est automatiquement 0 pour $ N \ ge M $. Le d [: M-N] dans la dernière ligne est la séquence d découpée au milieu (avant M-N).

ABC118 C - Monsters Battle Royale

<détails>

Concept </ summary>
Affiche uniquement les engagements maximum de $ A_1, A_2, \ dots, A_n $.

<détails>

Exemple de réponse </ summary> 

import fractions
N=int(input())
ls=[int(s) for s in input().split()]
a=0
for e in ls:
  a=fractions.gcd(a,e)
print(a)

ABC123 C - Five Transportations

<détails>

Concept </ summary>
Le plus lent des cinq modes de transport est la clé. L'étape déterminante en chimie.

Si vous demandez le temps qu'il faut pour transporter N personnes par le moyen de transport le plus lent, ce temps + 4 minutes est la réponse.

<détails>

Exemple de réponse </ summary> 

import math
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
X = min([A,B,C,D,E])
t=math.ceil(N/X)
print(t+4)

Ou utilisez $ \ left \ lceil \ dfrac NX \ right \ rceil = \ left \ lfloor \ dfrac {N + X-1} X \ right \ rfloor $

N = int(input())
ls = [int(input()) for i in range(5)]
X = min(ls)
print((N+X-1)//X+4)

ABC126 C - Dice and Coin

<détails>

Concept </ summary>
Mathématiques Un problème. Pas de notes spéciales. Vous pouvez utiliser log, mais vous pouvez tourner la boucle double for sans l'utiliser.

<détails>

Exemple de réponse </ summary> 

import math
N,K=[int(s) for s in input().split()]
a=0
for i in range(N):
  a+=2**(-max([0,math.ceil(math.log2(K/(i+1)))]))
print(a/N)

Alternativement, une combinaison d'instructions for et while (double boucle) peut être écrite comme suit. Dans mon cas, il y a moins d'erreurs simples lors de l'utilisation de cette méthode «intelligente».

N,K=[int(s) for s in input().split()]
a=0
for i in range(N):
  x=i+1
  n=0
  while x<K:
    n+=1
    x*=2
  a+=2**(-n)
print(a/N)

ABC129 C - Typical Stairs

<détails>

Concept </ summary>
Un problème célèbre en mathématiques au lycée. Ceux qui utilisent une formule graduelle. Lorsque le nombre de façons de passer à l'étape $ n $ est $ b_n $

b_{n}=  \begin{cases}
     b_{n-1}+b_{n-2} \quad (n\text{Les marches ne sont pas cassées})\\
     0\qquad (n\text{Les étapes sont cassées})
  \end{cases}

Tient pour $ n \ ge2 $. La méthode de mise en œuvre de cette récurrence est en fait difficile pour les débutants, alors je me demandais si je devais la traiter dans cet article, mais je l'ai traitée parce que ce sont des mathématiques trop lycées.

<détails>

Exemple de réponse </ summary>
J'ai utilisé ce qu'on appelle la "récurrence de mémorisation".

MOD=10**9+7
N,M=[int(s) for s in input().split()]
ls=[1 for _ in range(N+1)]
for i in range(M):
  ls[int(input())]=0
for n in range(2,N+1):
  if ls[n]!=0:
    ls[n]=(ls[n-1]+ls[n-2])%MOD
print(ls[N])

ABC130 C - Rectangle Cutting

<détails>

Concept </ summary>
Je n'ai rien à dire. Il peut toujours être divisé en deux parties égales, et si le point $ (x, y) $ est l'intersection des lignes diagonales du rectangle, il peut être coupé de plusieurs façons. Dans certains cas, il devrait être traité dans la classe «symétrie linéaire, symétrie ponctuelle» du collège.

<détails>

Exemple de réponse </ summary> 

W,H,x,y = [int(s) for s in input().split()]
if 2*x==W and 2*y==H :
  print(W*H/2,1)
else:
  print(W*H/2,0)

ABC131 C - Anti-Division

<détails>

Concept </ summary>
Mathématiques complètement lycée. Le champ «ensemble et logique» des mathématiques A. "Nombre total" - "Nombre de multiples de $ C $" - "Nombre de multiples de $ D $" + "Nombre de multiples communs de $ C et D $" peuvent être émis.

Le nombre de multiples de $ x $ supérieur ou égal à $ A $ et inférieur ou égal à $ B $ est "le nombre de multiples de $ x $ inférieur à $ B $" - "le multiple de $ x $ inférieur à $ A-1 $". Il est calculé par "nombre".

Au fait, le module des fractions n'a pas de fonction lcm pour trouver le multiple commun minimum. Par conséquent, j'ai essayé de trouver le multiple commun minimum avec $ C \ times D \ div gcd (C, D) $. C'est le contenu du champ "entier" de Math A.

<détails>

Exemple de réponse </ summary> 

import fractions
A,B,C,D = [int(s) for s in input().split()]
L=C*D//fractions.gcd(C,D)
print(B-(A-1)
      -(B//C)+((A-1)//C)
      -(B//D)+((A-1)//D)
      +(B//L)-((A-1)//L))

Il y a aussi un problème C plus simple

Les précédents sont la difficulté affichée dans At Coder Problems, c'est-à-dire que les problèmes avec le taux médian de bons répondants étant de 400 (marron) ou plus, et en fait plus. Il y a beaucoup de choses qui peuvent être facilement résolues (équivalent au gris).

Vous finirez par apprendre l'algorithme

Problème D et plus

Au-delà du problème D, le problème de "cette partie des mathématiques du secondaire!" Va diminuer.

De plus, même si elle est simplifiée par la puissance des mathématiques, la mise en œuvre nécessite souvent encore des connaissances en algorithmes (étant pris dans la limite du temps d'exécution), donc des problèmes "faciles" comme le 144D et le 139D introduits au début. La réalité est qu'il y en a peu.

C'est amusant d'étudier les algorithmes

Alors, étudions l'algorithme après tout.

C'est amusant de voir les explications de problèmes insolubles avec des solutions très vives et des algorithmes intéressants (même si je suis déprimé juste après la lecture). Si vous pouvez en profiter, vous pouvez profiter du pro de la concurrence.

Recommended Posts