Problem:


Score: 500 points

Problem Statement

You are the top spy of AtCoder Kingdom. To prevent the stolen secret from being handed to AlDebaran Kingdom, you have sneaked into the party where the transaction happens.

There are N attendees in the party, and they are given attendee numbers from 1 through N. The height of Attendee i is A_i.

According to an examination beforehand, you know that a pair of attendees satisfying the condition below will make the transaction.

The absolute difference of their attendee numbers is equal to the sum of their heights.

There are \frac{N(N-1)}{2} ways to choose two from the N attendees and make a pair. Among them, how many satisfy the condition above?

P.S.: We cannot let you know the secret.

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the number of pairs satisfying the condition.

Sample Input 1

6
2 3 3 1 3 1

Sample Output 1

3

A_1 + A_4 = 3, so the pair of Attendee 1 and 4 satisfy the condition.

A_2 + A_6 = 4, so the pair of Attendee 2 and 6 satisfy the condition.

A_4 + A_6 = 2, so the pair of Attendee 4 and 6 satisfy the condition.

No other pair satisfies the condition, so you should print 3.

Sample Input 2

6
5 2 4 2 8 8

Sample Output 2

0

No pair satisfies the condition, so you should print 0.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

22



Sample input:
6
2 3 3 1 3 1


Sample output:
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    increased = [elm + i for i, elm in enumerate(L)]
    decreased = [(elm - i, i) for i, elm in enumerate(L)]

    # decreased.sort(key=lambda x: x[0])
    decreased_stripped = [elm[0] for elm in decreased]

    # cnt = 0
    # for i, num in enumerate(increased):
    #     res = - num
    #     left = bisect_left(decreased_stripped, res)
    #     right = bisect_right(decreased_stripped, res)
    #     # print(f"{left} {right}")
    #     for x in range(left, right):
    #         j = decreased[x][1]
    #         # print(decreased[x][1])
    #         if i < j:
    #             cnt += 1
    # print(cnt)

    decreased_num_to_ind_list = defaultdict(list)
    for i, elm in enumerate(decreased_stripped):
        decreased_num_to_ind_list[elm].append(i)

    cnt = 0    
    for i, num in enumerate(increased):
        res = - num
        tmp = decreased_num_to_ind_list[res]
        if tmp:
            j = bisect_left(tmp, i)
            cnt += len(tmp) - j
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
self_front = [0]*(2*(10**5)+3)
for i in range(N):
    if(i-A[i] >= 0):
        self_front[i-A[i]] += 1
cnt = 0
for i in range(N):
    if(i+A[i] < 2*(10**5)+3):
        cnt += self_front[i+A[i]]
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))

num_dict = {}

for i,a in enumerate(a_list):
    idx = a+i
    if idx > 0:
        if idx not in num_dict:
            num_dict[idx] = 1
        else:
            num_dict[idx] += 1

count = 0

for i,a in enumerate(a_list):
    target_idx = i-a
    if target_idx in num_dict:
        if target_idx != a-i:
            count += num_dict[target_idx]
        else:
            count += num_dict[target_idx]-1


print(count)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
diff = [0]*N
summ = [0]*N
count = 0
for i in range(N):
    diff[i] = i - A[i]
    summ[i] = A[i] + i

c_diff = collections.Counter(diff)
c_summ = collections.Counter(summ)
for k in c_diff.keys():
    count = count + c_diff[k]*c_summ[k]
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
B1 = [A[i]+i for i in range(N)]
B2 = [-A[i]+i for i in range(N)]

C1 = Counter(B1)
C2 = Counter(B2)
ans = 0
for i in C1:
    if i in C2:
        ans += C1[i]*C2[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
a = [ A[i] - (i+1) for i in range(N)]
c = Counter(a)
count = 0
for i in range(N-1):
  count += c[-1*(A[i] + (i+1))]
  c[A[i]-(i+1)] -= 1
print(count)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))

d = collections.defaultdict(int)
for i in range(n):
    d[i + 1 + a[i]] += 1

ans = 0
for j in range(n):
    ans += d[j + 1 - a[j]]

print (ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = map(int, input().split())
    Aplus = [0] * N
    for i, a in enumerate(A):
        Aplus[i] = i + a + 1
    A_counter = Counter(Aplus)

    ans = 0
    for i in range(1, N + 1):
        key = i * 2 - Aplus[i-1]
        ans += A_counter[key]
        if key == Aplus[i - 1]:
            ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
pl = []
dic_mn = collections.defaultdict(int)

for i in range(n):
    pl.append(a[i] + i)
    dic_mn[i - a[i]] += 1
ans = 0
for i in range(n):
    ans += dic_mn[pl[i]]

print(ans)
#print(pl)
#print(dic_mn)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

Ap = [0] * N
Am = [0] * N

for i in range(N):
	Ap[i] = i + A[i]
	Am[i] = i - A[i]

import collections
h = collections.defaultdict(int)
ans = 0
for i in range(N):
	if Am[i] in h:
		ans += h[Am[i]]
	h[Ap[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
def main():
    N = int(input())
    A = [int(_) for _ in input().split()]
    B = [-a-i for i, a in enumerate(A)]
    C = sorted([a-i for i, a in enumerate(A)])
    D = [a+i for i, a in enumerate(A)]
    E = sorted([i-a for i, a in enumerate(A)])

    output = 0
    for b in B:
        x = bisect.bisect_left(C, b)
        y = bisect.bisect_right(C, b)
        output += y - x
    for d in D:
        x = bisect.bisect_left(E, d)
        y = bisect.bisect_right(E, d)
        output += y - x
    print(output//2)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]


    c = collections.Counter()

    ans = 0
    for i, a in enumerate(A):
        ans += c[a - i]
        c[-a - i] += 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[-1*A[i]+(i+1) for i in range(N)]
C=[A[i]+(i+1) for i in range(N)]
b={}
c={}
for i in range(N):
    if B[i] in b:
        b[B[i]]+=1
    else:
        b[B[i]]=1
for i in range(N):
    if C[i] in c:
        c[C[i]]+=1
    else:
        c[C[i]]=1
ans=0
for k in c.keys():
    if k in b:
        if k==0:
            a0+=1
        else:
            ans+=b[k]*c[k]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans, d = 0, dict()

for i in range(N):
    key = A[i] + i
    if d.get(key) == None:
        d[key] = 1
    else:
        d[key] += 1
    
    key = i - A[i]
    if d.get(key) != None:
        ans += d[key]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
List=list(map(int,input().split()))
ans = [[0,0] for i in range(N+1)]
for i in range(N):
  a = List[i]
  if i + a < N:
    ans[i+a][0] += 1
  if i-a >= 0:
    ans[i-a][1] += 1
    
cnt = 0
for i in range(N+1):
  a = ans[i][0]
  b = ans[i][1]
  
  cnt = cnt + a*b
     
print(int(cnt))

Submission status: Accepted

Solution code:
n = int(input())
from collections import Counter
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append(a[i]-i-1)
b = Counter(b)
k = -a[0]-1
a.append(10**10)
ans = 0
for i in range(n):
  ans += b[k]
  k -= 1
  k += a[i]-a[i+1]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


N = int(input())
A = list(map(int, input().split()))

# R = [None] * (N + 1)
# R[N] = Counter()

R = Counter()
cnt = 0
for n in range(N - 1, 0, -1):
    R[(n + 1) - A[n]] += 1
    c = A[n - 1] + ((n - 1) + 1)
    cnt += R[c]

# ans = 0
# for i, Ai in enumerate(A):
#     # n < a
#     # c0 = i - a
#     # l = L[i][c0]

#     # n >= a
#     c1 = Ai + (i + 1)
#     r = R[i + 1][c1]

#     ans += r

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
B = [A[i]-(i+1) for i in range(N)]
C = sorted(B)
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left

ans=0

for i in range(N):
    target = -2*(i+1)-B[i]
    l=bisect_left(C, target)
    r=bisect_right(C, target)
    ans+=r-l
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

t = list(map(int,input().split()))

ans = 0

sa = [0]*(n+1)

for i in range(n):
    if i+1-t[i] > 0:
        sa[i+1-t[i]] += 1

for i in range(n):
    if 0 < i+1+t[i] < n:
        ans += sa[i+1+t[i]]
    if i+1-t[i] > 0:
        sa[i+1-t[i]] -= 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int,input().split()))
bucket_l = [0] * (2*n)
bucket_r = [0] * (2*n)
for i,v in enumerate(a):
    if v > n:
        continue
    if i-v >= 0:
        bucket_l[i-v]+=1
    bucket_r[i+v]+=1

ret = 0
for i,j in zip(bucket_l,bucket_r):
    ret+=i*j
print(ret)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))

P = [i+A[i] for i in range(N)]
Q = [j-A[j] for j in range(N)]

Q_dict = collections.Counter(Q)

cnt = 0
for i in range(N-1):
    Q_dict[Q[i]] -= 1
    cnt += Q_dict[P[i]]

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
#from collections import Counter
import collections

def combinations_count(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    N = int(input())
    A  =  [int(i) for i in input().split()]

    A_plus = []
    A_minus = []
    for i, a in enumerate(A):
        A_plus.append(a+i)
        A_minus.append(-a+i)
    #print(A_plus,A_minus)
    plus = collections.Counter(A_plus)
    minus = collections.Counter(A_minus)
    ans = 0
    for k,v in plus.items():
        if k in minus.keys():
            ans += minus[k]*plus[k]
    print(ans)


if __name__ == "__main__":
    main()
"""
ans = 0
for i in range(2,N-1):
    k = 0
    while(k+i<N):
        #print(A[k], A[k+i],i)
        if(A[k]+A[k+i]) == i:
            ans += 1
        k+=1
print(ans)
"""

Submission status: Accepted

Solution code:

from collections import defaultdict


def submit():
    n = int(input())
    a = list(map(int, input().split()))

    j_aj = [(i + 1) - a[i] for i in range(n)]
    j_aj_cnt = defaultdict(int)    
    for j in j_aj:
        j_aj_cnt[j] += 1

    ans = 0
    for i in range(n):
        j_aj_cnt[j_aj[i]] -= 1
        t = (i + 1) + a[i]
        ans += j_aj_cnt[t]
    print(ans)


submit()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
B = A[:]
for n in range(N):
    B[n] -= (n + 1)

D = defaultdict(int)
ans = 0
for i, a, b in zip(reversed(range(N)), A[::-1], B[::-1]):
    ans += D[-(i + a + 1)]
    D[b] += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[0 for i in range(2*10**5+1)]
r=[0 for i in range(2*10**5+1)]
c=1
a=0
if n!=0:
  k=[int(i) for i in input().split()]
for i in range(n):
  if k[i]+c<=2*10**5:
    l[k[i]+c]+=1 
  if -k[i]+c>=0 and -k[i]+c<=2*10**5:
    r[-k[i]+c]+=1
  c+=1
for i in range(n):
  a+=l[i]*r[i]
print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

dp = defaultdict(int)
dm = defaultdict(int)
for i, ai in enumerate(a):
    if i + 1 + ai <= n:
        dp[i + ai + 1] += 1
    if 0 < i + 1 - ai <= n:
        dm[i + 1 - ai] += 1
ans = 0
keys = set(dp.keys()) & set(dm.keys())
for k in keys:
    ans += dp[k] * dm[k]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def RunLengthEncoding(list):
    dict = {}
    for i in list:
        if i in dict.keys():
            dict[i] += 1
        else:
            dict[i] = 1
    return dict


n = int(input())
a = list(map(int, input().split()))
minus = [i-a[i] for i in range(n)]
plus = [i+a[i] for i in range(n)]
minus_cnt = RunLengthEncoding(minus)
plus_cnt = RunLengthEncoding(plus)

cnt=0
for i in minus_cnt:
    if i in plus_cnt:
        cnt += minus_cnt[i] * plus_cnt[i]
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * N
    for i in range(N):
        B[i] = (i + 1) - A[i]
        A[i] += i + 1

    d = defaultdict(int)
    ans = 0
    for i in range(N-1,0,-1):
        d[B[i]] += 1
        ans += d[A[i-1]]

    print(ans)

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))

num_dict = dict()

ans = 0

num_dict[0 + A[0]] = 1
  
for i in range(1, N-1):
  if (A[i] + i in num_dict):
    num_dict[A[i]+i] += 1
  else:
    num_dict[A[i]+i] = 1
    
  if (i + 1 - A[i+1] in num_dict):
    ans += num_dict[i + 1 - A[i+1]]
    
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

num_dic = {}

ans = 0
for i, a in enumerate(A):
    if (i - a) in num_dic:
        ans += num_dic[i-a]
    if a + i in num_dic:
        num_dic[a+i] += 1
    else:
        num_dic[a+i] = 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7

#s=input().rstrip()
n=I()
h=LI()
plus=[]
minus=[]
for i in range(1,n+1):
    plus.append(i+h[i-1])
    minus.append(i-h[i-1])
#print(plus)
#print(minus)

ans=0
c=Counter(plus)
for m in minus:
    ans+=c[m]
print(ans)

Submission status: Accepted

Solution code:
def read_int():
    return int(input())

def read_int_map():
    return map(int,input().split(' '))

def read_int_list():
    return list(map(int,input().split(' ')))

def read_s_list_loop(n):
    return [input() for _ in range(n)]

from bisect import bisect_right
from bisect import bisect_left
import copy

N = read_int()
An = read_int_list()

An_diff = [0]*N
for i,a in enumerate(An):
    An_diff[i] = a - i
An_store = copy.deepcopy(An_diff)
An_diff.sort()
count_map = {}
ans = 0
for i,a in enumerate(An):
    target = (a+i)*(-1)
    shoud_be_minus_cnt = An_store[i]
    if shoud_be_minus_cnt not in count_map:
        count_map[shoud_be_minus_cnt] = 1
    else:
        count_map[shoud_be_minus_cnt] += 1
    cnt = bisect_right(An_diff,target) - bisect_left(An_diff,target)
    if target in count_map:
        cnt -= count_map[target]
    ans += cnt
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d1=defaultdict(int)
d2=defaultdict(int)

ans=0
for g in range(n):
    ans+=d1[a[g]-g]
    ans+=d2[a[g]+g]
    d1[-a[g]-g]+=1
    d2[-a[g]+1]+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
plus={}
minus={}
for i in range(n):
  if(a[i]+(i+1)<=10**9):
    if a[i]+(i+1) in plus.keys():
      plus[a[i]+(i+1)]+=1
    else:
      plus[a[i]+(i+1)]=1
  if(a[i]<(i+1)):
    if (i+1)-a[i] in minus.keys():
      minus[(i+1)-a[i]]+=1
    else:
      minus[(i+1)-a[i]]=1
ans=0
for i in plus.keys():
  if i in minus.keys():
    ans+=plus[i]*minus[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    add = []
    counter = defaultdict(int)
    
    for i in range(N):
        add.append(i+1 + A[i])
        key = i+1 - A[i]
        #key = abs(i+1 - A[i])
        counter[key] += 1
    
    ans = 0
    for add_value in add:
        ans += counter[add_value]
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import bisect
N = int(input())
alist = list(map(int, input().split()))
alist = [0] + alist
sumlist = []
# (j, wj)のリストを作る
for i in range(1,N+1):
    sumlist.append(i+alist[i])
sumlist.sort()
ans = 0
# 差と一致するものを探す
for i in range(1, N+1):
    diff = i - alist[i]
    if diff <= 0:
        continue
    i = bisect.bisect_left(sumlist, diff)
    j = bisect.bisect_right(sumlist, diff)
    ans += j - i
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
l=list(map(int,input().split()))
dic={}
ans=0
for i in range(n):
    a=i-l[i]
    if a in dic.keys():
       dic[a].append(i)
    else:
       dic[a]=[i]
for i in range(n):
  a=i+l[i]
  if a in dic.keys():
    s=dic[a]
  else:
    continue
  k=bisect.bisect_right(s,i)
  ans+=(len(s)-k)
print(ans)

Submission status: Accepted

Solution code:
# %%time
n = int(input())
a = list(map(int, input().split()))

# n = 10000
# a = np.random.randint(1, 1000, n)

import numpy as np
from collections import Counter

a = np.array(a)
ap = a + np.arange(n)
am = a - np.arange(n)
am = -am

c = Counter(am)

s = 0
for k in range(n):
    s += c[ap[k]]
    c[am[k]] -= 1

print(s)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A_list = list(map(int, input().split()))

left = [i - a for i, a in enumerate(A_list)]
right = [i + a for i, a in enumerate(A_list)]

left_c = collections.Counter(left)
right_c = collections.Counter(right)

count = 0
for i in left_c:
    if i in right_c:
        count += left_c[i] * right_c[i]

print(count)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = [A[i] - i for i in range(n)]
C = [-A[i] - i for i in range(n)]

# Bの要素それぞれに対するCの中ある等しいものの数の総和

C.sort()
from bisect import *

ans = 0

for b in B:
    ans += bisect(C, b) - bisect_left(C, b)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))

from collections import defaultdict
ue=defaultdict(int)
st=defaultdict(int)

for i in range(N):
  ue[i+1+A[i]]+=1
  st[i+1-A[i]]+=1

ans=0

for i in ue.keys():
  ans+=ue[i]*st[i]
  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int, input().split()))

cnt = {}
ans = 0

for i in range(len(a)):
    add = (i + 1) + a[i]
    sub = (i + 1) - a[i]

    #check
    if sub in cnt:
        ans += cnt[sub]

    #add cnt
    if add in cnt:
        cnt[add] += 1
    else:
        cnt[add] = 1

print(ans)

Submission status: Accepted

Solution code:
import collections
n=int(input())
l=list(map(int,input().split()))
a=[0]*n
b=[0]*n
for i in range(n):
  a[i]=i+1+l[i]
  b[i]=(i+1-l[i])
A=collections.Counter(a)
aa=A.most_common()
B=collections.Counter(b)

ans=0
for i in range(len(aa)):
  ans+=B[aa[i][0]]*aa[i][1]

print(ans)

Submission status: Accepted

Solution code:
import bisect

N = int(input())
alist = list(map(int, input().split()))
alist = [0] + alist
# print(alist)

sumlist = []
# (j, wj)のリストを作る
for i in range(1,N+1):
    # sumlist.append((i, i+alist[i]))
    sumlist.append(i+alist[i])

# 並び替え
sumlist.sort()
# print(sumlist)
# num = 4
# i = bisect.bisect_left(sumlist, num)
# j = bisect.bisect_right(sumlist, num)
# print(i,j)
ans = 0
# 差と一致するものを探す
for i in range(1, N+1):
    diff = i - alist[i]
    if diff <= 0:
        continue
    i = bisect.bisect_left(sumlist, diff)
    j = bisect.bisect_right(sumlist, diff)
    ans += j - i
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
B=[]
C=[]
for i,a in enumerate(A):
  B.append(i+a)
  C.append(i-a)
  
b = Counter(B)
c = Counter(C)
ans=0
for d in b.items():
  ans+=d[1]*c[d[0]]
print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())

A = list(map(int, input().split()))


def serch(li, x):
    l = 0
    r = len(li)
    mid = 0
    while True:
        mid = (l + r) // 2
        if li[mid] == x:
            return True

        if l >= r:
            break

        if li[mid] < x:
            l = mid + 1
        else:
            r = mid

    return False


ma = []
for i, a in enumerate(A):
    ma.append(i + a)

cnt = collections.Counter(ma)

ans = 0
for i, a in enumerate(A):
    # print(f"{i}  ===  {cnt[i + a]}")
    ans += cnt[i - a]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

R = [0]*N
L = [0]*N

for i in range(N):
    R[i] = - A[i] + i
    L[i] = A[i] + i

R.sort()
L.sort()

p = 0
q = 0

ans = 0
while p < N and q < N:
    if L[p] == R[q]:
        a = 1
        b = 1
        while p+a < N and L[p+a] == L[p]:
            a += 1
        while q+b < N and R[q+b] == R[q]:
            b += 1
        ans += a*b
        p += a
        q += b
    elif L[p] < R[q]:
        p += 1
    else:
        q += 1
    
    ###
    #if p < N and q < N:
    #    print(L[p],R[q],ans)
    ###

###
#print(L)
#print(R)
###

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
from collections import *
c=Counter()
a=0
for i in range(n):
  c[i+l[i]]+=1
  if i>l[i]:
    a+=c[i-l[i]]
print(a)

Submission status: Accepted

Solution code:
import bisect

n = int(input())

a_l = list(map(int, input().split()))

plus_l = [i + a_l[i] for i in range(n)]
minus_l = [i - a_l[i] for i in range(n)]

minus_l = sorted(minus_l)

ans = 0

for i in range(n):
    cur = plus_l[i]
    left = bisect.bisect_left(minus_l, cur)
    right = bisect.bisect_right(minus_l, cur)

    if left >= n or minus_l[left] != cur:
        continue

    ans = ans + right - left

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c,d=dict(),dict()
for i in range(n):
    if i+1-a[i] in c:
        c[i+1-a[i]]+=1
    else:
        c[i+1-a[i]]=1
    if i+1+a[i] in d:
        d[i+1+a[i]]+=1
    else:
        d[i+1+a[i]]=1
ans=0
for i in c:
    if i in d:
        ans+=(c[i]*d[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
ls = list(map(int,input().strip().split()))
dic1 = defaultdict(int)
dic2 = defaultdict(int)
for i,val in enumerate(ls,1):
    dic1[val+i] += 1
    dic2[val-i] += 1
ans = 0
for key,val in dic2.items():
    if -key in dic1:
        ans += val*dic1[-key]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


n = int(input())
A = list(map(int, input().split()))

plusA = A.copy()
minusA = A.copy()

for i in range(n):
    plusA[i] += i
    minusA[i] -= i

pldic = defaultdict(int)
midic = defaultdict(int)

for a, b in zip(plusA, minusA):
    pldic[a] += 1
    midic[b] += 1

ans = 0
keys = list(pldic.keys())
for key in keys:
    count = pldic[key]

    pair = midic[-key]
    ans += count * pair
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))


def solve(N,A):
    ans = 0
    lis = [0]*(2*10**5)
    for i,a in enumerate(A):
        if -a-i >= -2*10**5:
            lis[-a-i]+=1
    for i,a in enumerate(A):
        if a-i < 0:
            ans += lis[a-i]
    return ans
print(solve(N,A))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

#初期値が0の辞書
from collections import defaultdict
ab_dic = defaultdict(lambda: 0) 

#a+b
ab=[]

#b-aの個数
ba=[]

for i in range(n):
    banme=i+1
    ab.append(a[i]+banme)
    ba.append(banme-a[i])
    ab_dic[banme+a[i]]+=1


result=0
for i in range(n):
    ii=n-1-i
    if ab_dic[ba[ii]]>=1:
        result+=ab_dic[ba[ii]]
    ab_dic[ab[ii]]-=1


print(result)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    l = [x - i for i, x in enumerate(a)]
    from collections import Counter
    c = Counter(l)
    ans = 0
    for i in range(n):
        index = -i * 2 - l[i]
        ans += c[index] if index in c else 0
        c[l[i]] -= 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n=input()
a=map(int,raw_input().split())
b=[]
d={}
for i in range(n):
    b+=[i+a[i]]
    if i+a[i] in d:
        d[i+a[i]]+=1
    else:
        d[i+a[i]]=1

c=0
#print d
for j in range(n-1,-1,-1):
    if (j-a[j]) in d:
        c+=d[(j-a[j])]
        #print j
print c

Submission status: Accepted

Solution code:
#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    res = 0
    l = [0]*(10**6)
    used = []
    for i in range(n):
        if 0<=i+1-a[i]<n:
            l[i+1-a[i]] += 1
            used.append(i+1-a[i])
    cnt = 0
    for i in range(n):
        if 0<=i+1-a[i]<n:
            l[used[cnt]] -= 1
            cnt += 1
        if 0<=i+1+a[i]<10**6:
            b = i+1+a[i]
            res += l[b]
    print(res)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
import bisect
B = [(i+A[i],i-A[i]) for i in range(N)]

B.sort(key=lambda x: x[1])
C = [B[i][1] for i in range(N)]

ans = 0
for i in range(N):
    idl = bisect.bisect_left(C,B[i][0])
    idr = bisect.bisect_right(C,B[i][0])
    
    if 0<=idl<idr<=N and C[idl]==C[idr-1]==B[i][0]:
        ans += idr-idl
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left,bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [i+A[i] for i in range(N)] 
    B.sort()
    C = [i-A[i] for i in range(N)] 
    C.sort()
    ans = 0
    for i in range(N):
        ans += bisect_right(C,B[i]) - bisect_left(C,B[i])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

A=list(map(int,input().split()))
#print(A)

dic={}
for i in range(len(A)):
    if i-A[i] in dic:
        dic[i-A[i]]+=1
    else:
        dic[i-A[i]]=1

ans=0
for i in range(len(A)):
    temp=i+A[i]
    if temp in dic:
        ans+=dic[temp]
        #print(A[i],ans)
    if i-A[i]==i+A[i]:
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    AA = list(sorted([i+1+A[i] for i in range(N)]))

    ans = 0
    for i in range(N):
        idx_l = bisect.bisect_left(AA, i+1-A[i])
        idx_r = bisect.bisect_right(AA, i+1-A[i])
        # print(idx_l, idx_r, i+1-A[i], i+1)
        # num = min(idx_r, N-1)-max(idx_l, 0)
        num = 0
        if 0<=idx_l<N and 0<=idx_r<N:
            num = idx_r - idx_l
        # if AA[idx] == i+1-A[i]:
        #     ans += 1
        # print(num)
        ans += num

    print(ans)

if __name__ == '__main__':
    resolve()