C - Distance Indicators
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
2重ループするとTLEになってしまうということで工夫が必要な問題でした
元の式j−i=Ai+Ajを変形するとj−Aj=i+Aiになります
i+Aiの数を記録・カウントしておくと、記録していた数の中からj−Ajに当てはまる数を数えることでj−Aj=i+Ai
j（i+Ai）を先に記録してしまうとi<jの制約に引っ掛かるため先にi（i-Ai）をansに追加しています
def i_map():
return map(int, input().split())
def i_list():
return list(map(int, input().split()))
n = int(input())
a = i_list()
d = dict()
ans = 0
for i in range(0, n):
if i - a[i] in d:
ans += d[i - a[i]]
if i + a[i] not in d:
d[i + a[i]] = 1
else:
d[i + a[i]] += 1
print(ans)全く解法が思いつかなかったし、解説理解するのも時間かかった、、
ちなみに後で見たらPythonでもっと短くかける方法がありました
コメント