[伯俊]74534つのゼロと整数

https://www.acmicpc.net/problem/7453

質問する

整数からなる大きさが等しい配列はA,B,C,Dである.
A[a]、B[b]、C[c]、D[d]の和が0の(a、b、c、d)対の個数を求めるプログラムを作成する.

入力

第1行は配列の大きさn(1≦n≦4000)を与える.以下のn行では、A、B、C、Dに含まれる整数がスペースで区切られ、与えられる.配列内の整数のピッチ値は最大2^28です.

しゅつりょく

出力とゼロのペアの数.

に答える

アルゴリズムを段階的に適用しましょう.

フルナビゲーション

上の質問を見ると思い出す解答は完全に探求です.
次は完全ナビゲーションコードです.そしてこのようにすると100%以上の時間がかかります.

import sys
input = sys.stdin.readline
n = int(input())
a, b, c, d = list(), list(), list(), list()

for i in range(n):
    t, e, m, p = map(int, input().split())
    a.append(t)
    b.append(e)
    c.append(m)
    d.append(p)

answer = list()

for i in range(n):
    for j in range(n):
        for k in range(n):
            for m in range(n):
                if a[i] + b[j] + c[k] + d[m] == 0:
                    answer.append([i, j, k, m])

print(len(answer))

4つのfor loopをすべて完了すると,時間的複雑度はO(n^4)となり,1~2%の間でタイムアウトする.
これは探索では全く解決できない問題だ.(最初はカテゴリに完全な検索はありませんでした)

forサイクルを減らす

https://jaeyoon-95.tistory.com/168
参考解答.
ほとんどの人は辞書で時間の複雑さをOと解釈している(n^2).
まずaとbを並べ、cとdを並べて問題を解く.
Python dictionaryでget関数をうまく使えばいいという機会に知りました.

getは、keyerrorが表示されず、default値が指定されていない場合はNoneが表示され、default値が指定されている場合は対応する値が表示されることを示します.
上の関数がわかりませんが、コードを書くときに以下のように書きました.

a = dict()
count = 0

if not 'key' in a.keys():
  a[key] = 0
count += a.get(key)

でも今は知っていますが、下と一緒に書けば、上のように...!

a = dict()
count = 0

count += a.get(key, 0)

回答は次のとおりです.

import sys
input = sys.stdin.readline
n = int(input())
a, b, c, d = list(), list(), list(), list()

for i in range(n):
    t, e, m, p = map(int, input().split())
    a.append(t)
    b.append(e)
    c.append(m)
    d.append(p)

answer = dict()
for _a in a:
    for _b in b:
        answer[_a + _b] = answer.get(_a+_b, 0) + 1
count = 0
for _c in c:
    for _d in d:
        count += answer.get(-(_c+_d), 0)
print(count)