Quel est le meilleur, PyPy ou Python?

Quand il devient TLE avec Python, vous pouvez obtenir AC avec PyPy, et inversement, lorsque vous devenez TLE avec PyPy, vous pouvez obtenir AC avec Python.

Exemple d'AC en Python et TLE en PyPy

Dans Problème A du Concours Typique AtCoder 001, il y a un problème de recherche de priorité en profondeur.

J'ai donc écrit le code suivant.

test.py

import sys

sys.setrecursionlimit(500*500)
def dfs(px,py):
	if px < 0 or py < 0 or px > w-1 or py > h-1:
		return False

	if c[py][px] == '#':
		return False
	if c[py][px] == 'g':
		return True

	c[py][px] = '#'

	if dfs(px-1,py):
		return True
	if dfs(px,py-1):
		return True
	if dfs(px+1,py):
		return True
	if dfs(px,py+1):
		return True

	return False

h,w = map(int,input().split())

c = []
for i in range(h):
	s = input()
	x = s.find('s')
	if x != -1:
		start = [x,i]
	c.append(list(s))

sx = int(start[0])
sy = int(start[1])

if dfs(sx,sy):
	print('Yes')
else:
	print('No')

Je pense qu'il est écrit d'une manière assez simple comme une recherche prioritaire en profondeur.

À la suite de cette soumission, il est devenu le suivant.

J'ai AC dans Python3, mais il est devenu TLE dans PyPy3.

Cela semble être dû au fait que ** PyPy est incompatible avec les fonctions récursives **.

Vous pouvez utiliser AC de toute façon en utilisant la pile silencieusement sans utiliser de fonctions récursives.

Exemple d'AC avec PyPy et TLE avec Python

Problème AtCoder Beginner Contest 153 E était un problème qui pouvait être résolu en utilisant la planification dynamique.

J'ai donc écrit le code suivant.

test.py

H,N= map(int,input().split())

a = []
b = []

for i in range(N):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i+1][j] =Devenir un monstre avec une force physique j avec de la magie jusqu'à i
#Quantité minimale de puissance magique pouvant être gagnée
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]

#Les monstres avec 0 santé meurent depuis le début
for i in range(N+1):
  dp[i][0] = 0

for i in range(N):
  for j in range(H+1):
    if a[i] > j:
      dp[i+1][j] = min(dp[i][j],b[i])
    else:
      dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+ b[i])

print(dp[N][H])

Sans aucune ingéniosité particulière, le code est simplement similaire au problème du sac à dos à nombre illimité.

Lorsque j'ai soumis cela, les résultats suivants ont été renvoyés.

Cette fois, il est devenu AC avec PyPy et TLE avec Python3.

Bien sûr, il existe également un moyen de le résoudre en Python.

Lequel devrais-je utiliser après tout?

** Je pense que la bonne réponse est d'écrire une belle réponse qui vous permet d'obtenir AC indépendamment de celle que vous utilisez.

Cependant, comme je suis un débutant en compétition, j'utiliserai PyPy pour le moment, et utiliserai Python lors de l'utilisation de fonctions récursives **.

À propos, PyPy semble avoir l'inconvénient que certaines bibliothèques écrites en langage C ne peuvent pas être utilisées.

finalement

Puisque je suis un débutant en compétition, veuillez signaler toute insuffisance dans le contenu ci-dessus.