AtCoder Je ne connais pas le journal_1 ABC148D

introduction

J'ai participé au concours AtCoder pour la première fois. J'ai résolu un peu les questions du passé. Je suis vraiment un débutant, mais je pense que C est si facile et que D peut être utilisé. J'ai pensé, alors je l'ai résolu. Cela n'a pas fonctionné à temps. La réponse d'un homme fort en programmation (Tsuyobito) est trop intelligente pour les débutants. e? Existe-t-il un moyen de recevoir une telle contribution? !! Est-ce une fourmi comment le sortir? !! Ce sera comme. Je vais me consacrer. Pour le moment, j'aimerais réfléchir aux raisons pour lesquelles l'algorithme que je pensais n'était pas bon. Cela n'a pas de sens si vous ne pouvez pas écrire les opérations que vous considérez comme du code. Le problème vient du problème D de ABC148. Voici une citation (je vais suivre les règles, mais s'il vous plaît laissez-moi savoir si c'est faux).

(Ajout qui n'a pas d'importance) Je n'ai pas encore acheté de livre sur les fourmis. Parce que j'ai une petite somme d'argent. S'il est dans la bibliothèque de l'école, je pourrais peut-être le louer pour les vacances de fin d'année et de nouvel an. Je pensais que je voulais qu'il l'achète, mais j'ai fait une erreur de direction, donc j'étais chez moi. ・ Manuel d'algorithmes - Principes de base et applications des algorithmes présentés dans des programmes pratiques - ・ Puzzle d'algorithme-Introduction aux puzzles mathématiques pour les programmeurs- Je voulais d'abord me prêter ce livre et apprendre l'algorithme, alors j'ai pensé que c'était correct. L'ancien livre est plus vieux que moi ...

D - Brick Break

N briques sont alignées sur une rangée horizontale. L'entier a i </ sub> est écrit sur la i (1 ≤ i ≤ N) ème brique à partir de la gauche. Vous pouvez choisir et écraser n'importe quelle brique de N-1 ou moins. En conséquence, les briques K restent. A ce moment, pour tout entier i (1 ≤ i ≤ K), M. Sunuke est satisfait lorsque l'entier écrit dans le i-ème à partir de la gauche parmi les briques restantes est i. Veuillez indiquer le nombre minimum de briques que M. Sunuke doit écraser pour être satisfait. Si ce n'est pas possible, peu importe comment vous l'écrasez, imprimez -1 à la place.

Pensées

(1) Il semble que les nombres doivent rester dans l'ordre à partir de 1. ② Ensuite, dois-je le vérifier avec l'index de l'avant et effacer le différent [^ 1] Comment décidez-vous d'une nomenclature appropriée? Et quel était l'élément de la métaphore et pourquoi? Tel. [^ 1]: C'est une erreur. Il suffit de le compter. Ce qu'il faut en premier lieu, ce n'est pas la séquence finale de nombres. Lisez correctement le problème

Première fois

n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
    #index+Supprimer si 1 est différent de l'élément de liste
    if a[i] != i + 1:
        del a[i]
    #S'ils sont identiques, vérifiez l'élément suivant
    else:
        i += 1
#Impossible si vous effacez tout
if len(a) == 0:
  print(-1)
#Si vous soustrayez les éléments restants, ce sera le nombre que vous avez cassé
else:
    print(n - len(a))

To TLE dans certains cas de test. Hmmm j'y ai pensé pendant un moment, mais je ne sais pas ce qui ne va pas ... Je ne suis pas sûr que ce soit vraiment juste. N'est-ce pas TLE dans une boucle infinie, mais le temps est écoulé lorsque le cas de test est trop long? Je ne comprends pas vraiment comment cela fonctionne. Après cela, je craignais de le casser en chemin, mais cela n'avait pas d'importance du tout, alors je l'ai omis.

4e

③ Cela n'a peut-être pas été bon car je les ai effacés un par un. Vous pouvez tout effacer à la fois. Alors,

n = int(input())
a = list(map(int, input().split()))
ans = 0
i = 0
while i + 1 <= len(a):
    #index+Si 1 est différent de l'élément de liste
    if a[i] != i + 1:
        #Vérifiez s'il y a le bon élément
        if i + 1 in a:
            #Supprimer avant l'élément correct
            del a[i:a.index(i + 1)]
        #Supprimer tout s'il n'y a pas d'élément correct
        else:
            del a[i:]      
    #index+Si 1 est le même que l'élément de la liste, passez à l'élément suivant
    else:
        i += 1
#Impossible si vous effacez tout
if len(a) == 0:
  print(-1)
#Si vous soustrayez les éléments restants, ce sera le nombre que vous avez cassé
else:
    print(n - len(a))

Je suis passé par là. Tu l'as fait. Réponse de l'homme fort (Tsuyobito)

Cela n'a pas d'importance du tout, mais vous pouvez le lire séparément. ~~ On dirait un fou. ~~ [^ 2]

――Le code le plus court pour le moment, j'ai pleuré parce que je n'en comprenais pas du tout le sens [^ 3] [^ 4]

Pour une raison quelconque, j'essayais de trouver une ligne propre de briques, mais j'ai l'impression que je devais simplement compter le nombre de briques parfaitement alignées.

C'est ce qu'on appelle un opérateur ternaire

Il semble que vous puissiez écrire des instructions if et else sur une seule ligne.

(Si vrai, renvoyez ceci) si (sous cette condition) sinon (Si faux, c'est le cas)

Comme ça. Je n'ai même pas besoin d'un colon. C'est pratique. Donc les 4 dernières lignes

print(-1 if len(a) == 0 else n - len(a))

C'est bon. Je vois! Apprendre. [^ 2]: Compla [^ 3]: expression exagérée [^ 4]: Ce n'est pas le but d'écrire le code le plus fort pour le moment, il est important de résoudre le problème aussi loin que vous pouvez le comprendre, alors ne vous inquiétez pas.

Recommended Posts

AtCoder Je ne connais pas le journal_1 ABC148D
AtCoder Je ne sais pas journal_2 ABC148E
AtCoder Je ne connais pas le journal_3 ABC149C, D
AtCoder Je ne sais pas journal_4 ABC081B, 087B, 083B (de l'ABS)
Je ne connais pas l'erreur de valeur
Je ne comprends pas rejoindre
Journal de participation Atcoder Beginner Contest 146
J'ai participé à AtCoder (ABC158)
Je ne sais pas comment obtenir les paramètres de requête dans GAE / P
Je ne connaissais pas le théorème de Lucas qui est sorti naturellement dans Atcoder