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

Les résultats de cette fois

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.

Examen du concours de programmation Keyence 2020