Examen du concours de programmation Keyence 2020

Je voudrais revoir le [Keyence2020] d'hier (https://atcoder.jp/contests/keyence2020).

Les résultats de cette fois

スクリーンショット 2020-01-19 7.54.59.png

Impressions

Je n'ai pas pu le résoudre du tout dans le dwango précédent (je ne l'ai pas revu, donc je dois le revoir bientôt), mais cette fois, j'avais peur. La raison pour laquelle je n'ai pas pu résoudre la quatrième question pendant plus d'une heure était ** Je n'avais pas assez de puissance logique et d'esprit **. J'étais ... Je n'ai pas vu de croissance mentale depuis que j'ai passé l'examen universitaire, alors j'aimerais aussi développer cette partie.

Problème A

Faites-le car il est possible de continuer à sélectionner les plus grands h et w (est-ce trop facile?). Pas h, w, n = map (int, input (). Split ()), hein? C'est devenu.

answerA.py


import math
h=int(input())
w=int(input())
n=int(input())
k=max(h,w)
print(math.ceil(n/k))

Problème B

Au moment où je l'ai vu, j'ai su que c'était la planification de la section. Utilisez la planification de sections pour prendre le nombre maximum de sections afin qu'il n'y ait pas de parties communes lors de la prise de sections avec des parties communes. Dans la planification des sections, l'algorithme trie par ordre croissant en fonction de l'heure de fin de la section, et les sections dont l'heure de début est après l'heure de fin sont prises dans l'ordre d'avant (triées). La régression mathématique peut prouver pourquoi le nombre maximum d'intervalles peut être pris par l'ordonnancement des intervalles. En supposant qu'il y ait une méthode de sélection de section optimale, cette méthode de sélection optimale le montre car l'heure de fin n'est pas en retard (✳︎) lorsque le même numéro est sélectionné par rapport à toute autre méthode de sélection (preuve simplifiée). Faire.). Lorsque n = 1, celui avec l'heure de fin la plus ancienne est sélectionné. Lorsque n = k est vrai, n = k + 1 sélectionne la section qui commence après l'heure de fin de la section sélectionnée par n = k et a l'heure de fin la plus ancienne, donc même n = k + 1 Cela tient de la même manière. Par conséquent, on peut dire que (✳︎) tient dans l'algorithme basé sur l'ordonnancement d'intervalle. Lorsque ce qui précède est mis en œuvre, cela devient comme suit. Il peut être facilement résolu en pensant que x-l est l'heure de début et x + l est l'heure de fin.

answerB.py


n=int(input())
sec=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    sec[i][0]+=l
    sec[i][1]-=l
sec.sort()

ans=0
#-inf
t=-10000000000
for i in range(n):
    #=N'oubliez pas de mettre
    if t<=sec[i][1]:#Le départ doit être supérieur ou égal à certaines coordonnées maximales du bras du robot
        ans+=1#Si ci-dessus+1
        t=sec[i][0]#Coordonnées maximales mises à jour avec le bras du robot
print(ans)

Problème C

C'était étonnamment facile quand je pensais que c'était une construction. Qu'est-ce que c'est. Je pensais qu'il y avait k> n et je me suis retrouvé coincé dans un cas d'angle de 10 ** 9 et j'ai émis 4WA. Je suis désolé. 1 <= l <= r <= n, mais quand on pense au cas de l = r, ça se termine immédiatement (au premier 1,1,1,1,…, r-1,…, r) Cela a pris du temps car je pensais à -1, r + 1, ..., r + 1. ** Il est important de simplifier le problème en construction ** ??). Considérant un motif avec k s et n-k s + 1, vous pouvez sélectionner k avec l = r. Cependant, lorsque $ s = 10 ^ 9 $, s + 1 sera hors de la contrainte, vous pouvez donc le définir sur 1 au lieu de s + 1 (car la somme de 1 ne devient pas s).

answerC.py


n,k,s=map(int,input().split())
if s<10**9:
    x=[s]*k
    y=[s+1]*(n-k)
else:
    x=[s]*k
    y=[1]*(n-k)
z=" ".join(map(str,x))+" "+" ".join(map(str,y))
print(z)

D problem

Je suis toujours frustré parce que je ne peux pas résoudre ce niveau de problème. Cependant, je pense avoir grandi parce que j'ai fait des trucs récemment avec un problème légèrement tordu comme le problème C. Quand j'ai vu le tweet le plus fort après le concours, j'ai remarqué que c'était 2 $ ^ {18} $, donc c'était environ 10 $ ^ 5 $, et j'ai pu voir que je pouvais faire une recherche complète. Tout d'abord, décidez du recto et du verso de chaque carte, et si vous le décidez, vous pouvez voir le nombre que vous pouvez voir dans l'état final de chaque carte, donc dans cet état, vous triez par ordre croissant avec le tri à bulles et pensez au nombre de fois que vous avez échangé à ce moment-là. , Trouvez le nombre minimum de swaps. Il est également important de noter que les cartes avant ne peuvent être placées qu'un nombre pair de distances, et les cartes arrière ne peuvent être placées qu'un nombre impair de distances.

J'ai pu établir une politique, mais je n'ai pas considéré le cas où il y a plusieurs mêmes numéros, donc je ne peux rien faire avec WA. Je voudrais le donner dès que ca est possible.

Recommended Posts

Examen du concours de programmation Keyence 2020
Revue du concours de programmation NOMURA 2020
Examen du concours de programmation HHKB 2020
Critique du concours de programmation Tokio Marine & Nichido 2020
Rapport de participation au concours de programmation AtCoder Keyence 2020
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours de programmation Acing 2020
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours de programmation HHKB 2020
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Bilan 2019 du concours de programmation Sumitomo Mitsui Trust Bank
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Grand Contest 048 Critique
Critique du concours AtCoder Débutant 181
Après le "Concours de programmation Diverta 2019"
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours de programmation Atcoder Acing Python
Notes pour le concours de programmation HHKB 2020
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
AtCoder Beginner Contest 066 Revoir les questions précédentes
Rapport de participation au concours de programmation AtCoder Panasonic 2020
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes