ABC 131（PyPyは再帰してはいけない）

ABC 131

着実にPythonに慣れてきた結果ABCD完であった。Eは問題の意味が分からないのでやめた。
そもそもAから頭が働かなくてどうしようもなく、時間が無駄にか掛かった。
寝不足は大敵なのでやめよう。

ABC 131 F Must Be Rectangular!

3点在ったら4点目を埋めてその追加できる最大数を求める問題。
例によってできなかった問題をやる。
youtubeの問題解説の通りのやり方では出来なかった。
以降、解説前提のため先にyoutubeを見ることを勧める。
なお、Pythonの再帰限界はデフォルト1000なので変える場合は、以下のようにする。

atcoder.py

import sys
sys.setrecursionlimit(10**5)

こう変えることでREがTLEになるだけで問題は解決しなかった。
単純な深さ優先でC言語なら出来てもPythonの速度ではTLEする例である。
仕方がないのでUnionFindをどこかから持ってきた。
x,y成分を分けて考え、線で結んで連結して、同じ根につながっているx側とy側の数を別々にカウントする。
カウントが終わったらx側の数*y側の数が点数の最大値である。
異なる根についても同様に計算して総和を求め、最後に総和-Nが今回求めたい追加できる最大数となる。
ソースは載せない。参考にしたサイトをPython化しただけになったためである。

追記

結果から言うと解説通りのコードで、Python3ならACでPyPy3ではTLEであった。
まず、AtCoderのPyPy3の再帰最大数は100であり、ケース9だけREするため、再帰が一番深いのがケース9だと推定できる。
Python3やローカル環境で同じコードで何度やっても1秒かからず10万入力処理出来ていて謎だったが、PyPyについて調べると再帰が遅いというのがあった。
入力やほかの部分が遅い可能性については、ググって最適に近いといわれているものを選んだので否定的である。

結論「AtCoderで再帰を使うときはPyPyはやめた方がいい」

以下のコードはPython3でAC、PyPy3でTLEするものである。

atcoder.py

import sys
sys.setrecursionlimit(10**5)
m = 100005
visited = [False]*(m*2)
cnt = [0,0]
def dfs(i):
    visited[i] = True
    cnt[i//m] = cnt[i//m]+1
    for j in to[i]:
        if not visited[j]:
            dfs(j)

input = sys.stdin.readline
n = int(input())
to = [[] for _ in range(m*2)]
for _ in range(n):
    x,y = map(int,input().split())
    y = y+m
    to[x].append(y)
    to[y].append(x)

ans = 0
for i in range(m):
    if not visited[i]:
        cnt = [0,0]
        dfs(i)
        ans = ans + cnt[0]*cnt[1]

print(ans-n)