https://atcoder.jp/contests/abc215/tasks/abc215_e
ただのDPで、PyPy2だとあっさり通りました。
で、Python3で試したら、24ケース中13ケースでTLE。案の定Pythonでは遅いです。
手元でも試したら、実行時間は元の文字列の長さにだいたい比例するので、長さ少し変えて、
length | Python2 | PyPy2 |
---|---|---|
1000 | 1.92s | 0.25s |
2000 | 3.83s | 0.44s |
4000 | 7.80s | 0.84s |
だいたいPyPy2のほうが9倍くらい速いですね。長いリストを使うとだいたいこんな感じです。
たいていの場合PyPyのほうが速いので、素直にPyPyを使いましょう。