atcoderのabc176のE問題でエラーがでる

Question

実現したいこと

前提

atcoderのabc176のE問題でREが出ますが、SampleはACになるのでどの部分が原因なのかわかりません。分かる方がいれば教えていただきたいです。

該当のソースコード

H,W,m=list(map(int, input().split()))

maps=[]
for i in range(H):
    row=[0]*W
    maps.append(row)

hmax=0#行ごとにみた爆弾の最大値
hnum=[0]*H#各行の数
wmax=0#列ごとにみた爆弾の最大値
wnum=[0]*W#各列の数
hlist=[]#各行の最大値となる行のインデックスリスト
wlist=[]#各列の最大値となる列のインデックスリスト

for i in range(m):
    h,w=list(map(int, input().split()))
    h-=1
    w-=1
    maps[h][w]=1
    hnum[h]+=1
    wnum[w]+=1
    
    if hmax<hnum[h]:
        hmax=hnum[h]
        hlist=[]
        hlist.append(h)
    elif hmax==hnum[h]:
        hlist.append(h)
    
    if wmax<wnum[w]:
        wmax=wnum[w]
        wlist=[]
        wlist.append(w)
    elif wmax==wnum[w]:
        wlist.append(w)


flag=False
ans=hmax+wmax

for i in range(len(hlist)):
    if flag:
        break
    for j in range(len(wlist)):
        if maps[hlist[i]][wlist[j]]==0:
            flag=True
            break



if not flag:
    ans-=1
print(ans)

試したこと

pypy,Cpythonともに同じようなエラーが出ました。

Answer 1

mapsのサイズが大きくなりすぎるのが原因です。

H,W の最大値がそれぞれ 3x10^5 なので、mapsのサイズは最大 H x W = 9x10^10 となります。
たとえ各要素が1バイトだったとしても、9x10^10バイト=90GBなので、メモリ制限1024MBの環境ではとても動かせません。

mapsをリストのリストで持たせるのは無理があるので、別のデータ構造を使いましょう。

Comments

[bajapan]

回答ありがとうございます。メモリを考慮するのに、リストのサイズも注意しなくてはいけないのですね。
別の方法を考えます。