AtCoder ABC155 Problème D Pairs Review Note 1

Aperçu

Une note sur AtCoder ABC155 Problem D Pairs.

Contexte

AtCoder ABC155 organisé le 16/02/2020 était trop occupé pour participer, mais en raison de la dévotion [Problème D](https: //) Atcoder.jp/contests/abc155/tasks/abc155_d) Je ne pouvais pas penser à une solution. En regardant l'article de commentaire, j'ai compris qu'il devait être compté par la méthode de la dichotomie. J'ai moi-même essayé de coder en Python, mais je ne pouvais pas sortir de TLE par moi-même.

De Comparaison précédente, j'ai deviné que je pourrais probablement utiliser C ++, mais

J'étais curieux de ce genre de choses, alors j'ai cherché.

Résultats du sondage

Est-il possible de le passer avec Python?

Conclusion: peut passer (mais est-ce un peu difficile?)

Quand j'ai cherché une personne qui a pris AC avec Python3, le résultat était comme ça. ABC155D-python-AC-01m.png Seules deux personnes sont passées pendant la durée du concours, maspy était jaune et nohtaray était bleu mais jaune (au 20 mars 2020). Le temps d'exécution est d'environ 1100 ms.

Considérant que seules deux personnes peuvent passer dans le temps et que les deux personnes qui passent sont jaunes et bleues, cela semble être un problème difficile à passer par ma capacité.

Je l'ai également essayé avec PyPy, qui a montré une amélioration significative dans Comparaison précédente ([Soumission # 10928876](https://atcoder.jp/contests/ abc155 / soumissions / 10928876)) n'a pas été très efficace cette fois et le TLE n'a pas pu être résolu.

Qu'est-ce qui est agréable dans votre code lorsque vous le transmettez?

Comparaison de la vitesse d'exécution

Tout d'abord, j'ai comparé les temps d'exécution. maspy Soumission # 10152895 [Soumission # 10155744] de nohtaray (https://atcoder.jp/contests/abc155/submissions/10155744) Je l'ai téléchargé sur mon serveur et l'ai écrit moi-même Programme Soumission # 11068460 De plus, le temps d'exécution de chaque programme pour quatre cas de test a été comparé. Les résultats suivants (mesure de la commande de temps du temps écoulé. L'unité est la seconde). Puisque les résultats d'exécution eux-mêmes correspondent, le programme lui-même semble fonctionner correctement.

programme test01 test02 test03 test04
Mon programme[Soumission#11068460] 0.045 0.039 9.576 9.576
Nohtaray's[Soumission#10155744] 0.303 0.288 1.140 1.119
maspy[Soumission#10152895] 0.275 0.312 1.097 1.045

La taille du scénario de test est la suivante. Ai a été généré par des nombres aléatoires.

programme test01 test02 test03 test04
N 20 20 200000 200000
Nombre de nombres positifs 10 10 100000 10000
Nombre de zéro 1 1 1 1
Nombre de nombres négatifs 9 9 99999 99999
K 150 50 1500000000 500000000

Les résultats montrent que mon programme est plus rapide lorsque N est petit, mais lorsque N est grand Les programmes de maspy et nohtaray sont environ 10 fois plus rapides. .. ..

Comparaison de code

Alors, quelle est la différence? .. .. Jetons un coup d'œil aux programmes de maspy et nohtaray pour le découvrir. Il s'avère que les deux codes utilisent une fonction appelée numpy searchsorted. Un tableau est également utilisé pour le deuxième argument. Il était prévu que ce serait probablement beaucoup plus rapide que ma fonction portative. Existe-t-il une telle fonction? .. .. .. Le code est court, en partie grâce à son utilisation.

finalement

La note 1 est terminée jusqu'à ce que l'utilisation de la recherche de numpy triée soit considérée comme "miso".

J'ai découvert que je n'avais pas assez de connaissances sur numpy pour concourir en Python. Si vous avez envie d'écrire numpy searchsorted ou si vous pouvez écrire du code qui ne TLE pas plus facilement avec C ++, je vais l'étudier et l'organiser.

Recommended Posts

AtCoder ABC155 Problème D Pairs Review Note 1
AtCoder ABC 182 Python (A ~ D)
AtCoder ABC151 Problème D Comparaison de la vitesse en C ++ / Python / PyPy
AtCoder ABC156 Problème D Calcul et séquence du module Bouquet, etc.
AtCoder ABC176
AtCoder ABC177
Atcoder ABC60 D - Solution séparée de sac à dos simple
Mémo Atcoder débutant Python @ Keyence 2020, problème ABC
[AtCoder] Résoudre ABC1 ~ 100 Un problème avec Python
Résoudre AtCoder ABC168 avec python (A ~ D)
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
AtCoder ABC 174 Python
Défiez AtCoder (ABC) 164 avec Python! Un problème ~ C
AtCoder ABC 175 Python
Examen de atcoder ABC158, jusqu'à la question E (Python)
Critique du concours AtCoder Beginner Contest 152
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Examen des questions passées d'AtCoder (12 / 6,7)
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Concours régulier AtCoder 106 Remarque
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
Concours régulier AtCoder 105 Remarque
AtCoder Grand Contest 045 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
Concours AtCoder Débutant 184 Remarque
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
Une personne qui veut résoudre le problème D avec ABC d'AtCoder a essayé de gratter
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Résolution avec Ruby et Python AtCoder ABC151 D Recherche de priorité de largeur
Résolution avec Ruby et Python AtCoder ABC133 D Somme cumulée
Résolution avec Ruby et Python AtCoder ABC138 D Liste adjacente