https://codeforces.com/contest/1520/problem/D
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 2 * 105)
• a1 , a2, …, an (0 ≤ ai ≤ n)

output :

• For each test case output the number of pairs of indices (i,j) such that i<j and aj − ai = j − i.
  각 테스트 케이스에서 (i, j)묶음의 수를 출력하시오.

조건 :

• Count the number of pairs of indices (i, j) such that i<j and aj − ai = j − i.
  (i, j) 묶음의 숫자를 세아리시오.

---

당연히 이 배열 전체를 다 확인하려면 시간이 터질 거다.
조건을 살짝 바꾸고 현재 i를 기준으로 i보다 뒤에 동일한 값을 가진 게 있는지 확인을 하자.

식

aj − ai = j − i 이 식을
-> aj − j = ai − i 으로 바꿔줄 수 있다.

그러면 이 값으로 배열을 다시 바꿔버리고 맵을 이용해서 개수를 저장할 수 있다.

반복문

배열의 뒤에서부터 확인 하면서 동일한 값이 몇 개나 있는지 확인하자.

다음

저런 식을 주는 게 잇다면 이를 어떻게 변형시킬 수 있는지 생각하자.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    temp = dict()

    ans = 0
    for i in range(len(data) - 1, -1, -1):
        if data[i] - i - 1 not in temp:
            temp[data[i] - i - 1] = 1
        else:
            temp[data[i] - i - 1] += 1
        ans += temp[data[i] - i - 1] - 1
    print(ans)