競プロはPyPyとPythonのどっちが良いの？

PythonでTLEになった時PyPyでACを取れたり、逆にPyPyでTLEになった時PythonでACが取れたりします。

PythonでAC、PyPyでTLEになる例

AtCoder Typical Contest 001のA問題では、深さ優先探索の問題があります。

そこで、以下のようなコードを書きました。

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')

深さ優先探索としてはかなり安直な書き方をしていると思います。

これを提出した結果、次のようになりました。

Python3ではACを取れているのですが、PyPy3ではTLEになってしまっています。

これは、PyPyは再帰関数との相性が悪いらしく、それが原因となっているようです。

再帰関数を使わずに、大人しくスタックを使えばどちらでもACを取ることができます。

PyPyでAC、PythonでTLEになる例

AtCoder Beginner Contest 153のE問題は、動的計画法を用いて解ける問題でした。

そこで、以下のようなコードを書きました。

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] = i番目までの魔法で体力jのモンスターに
#勝つことができる、魔力の最小値
INF = 10**9
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]

#体力0のモンスターは初めからデスしている
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])

特にこれと言った工夫もせず、単純に個数制限なしナップサック問題と同じようなコードになりました。

こちらを提出すると以下のような結果が返ってきました。

今度はPyPyでAC、Python3でTLEになってしまいました。

もちろん、Pythonで解く方法もあります。

結局、どっち使えば良いの？

どっち使ってもACを取れるような、綺麗な回答を書けというのが正論なのだと思います。

ですが僕は競プロ初心者なので、とりあえずPyPyを使って、再帰関数を使うときはPythonにするというようにすることにします。

ちなみに、PyPyはC言語で書かれた一部のライブラリが使えないというデメリットもあるらしいです。

最後に

競プロ初心者なので、上記の内容に不備等ございましたらご指摘ください。