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

• Est-il possible de le passer avec Python? ―― En quoi votre code est-il agréable lorsque vous le passez?

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. 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.

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

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.