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:
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

b=Counter(r)
for i in l:
    ans+=b.get(i,0)

print(ans)

Submission status: Accepted

Solution code:
import collections

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

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

countL = collections.Counter(L)

countR = collections.Counter(R)


print(sum([countL[n] * countR[n] for n in countL.keys()]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    heights = list(map(int, input().split()))

    """
    for j>i, j-i = Ai + Aj
    -> i + Ai = j -Aj
    """

    x = [0] * N  # x represents i + Ai

    count = 0
    for i, height in enumerate(heights):
        right = i + height
        left = i - height

        if right < N:
            x[right] += 1

        if left > 0:
            count += x[left]

    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    heights = list(map(int, input().split()))

    """
    for j>i, j-i = Ai + Aj
    i + Ai = j -Aj
    """

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

    count = 0
    for i, height in enumerate(heights):
        right = i + height
        left = i - height

        if right < N:
            R[right] += 1

        if left > 0:
            L[left] += 1
            count += R[left]

    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    heights = list(map(int, input().split()))

    """
    for j>i, j-i = Ai + Aj
    i + Ai = j -Aj
    """

    L = defaultdict(int)
    R = defaultdict(int)

    for i, height in enumerate(heights):
        if i + height < N:
            L[i + height] += 1
        
        if i - height > 0:
            R[i - height] += 1

    total_count = 0
    for x, count_l in L.items():
        if x in R:
            count_r = R[x]
            total_count += count_l * count_r

    print(total_count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    _ = int(input())
    heights = list(map(int, input().split()))

    """
    for j>i, j-i = Ai + Aj
    i + Ai = j -Aj
    """

    L = defaultdict(int)
    R = defaultdict(int)

    for i, height in enumerate(heights):
        L[i + height] += 1
        R[i - height] += 1

    total_count = 0
    for x, count_l in L.items():
        if x in R:
            count_r = R[x]
            total_count += count_l * count_r

    print(total_count)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#Ai + i 
#j-Aj
ans = 0
cnt = [0]*(n+1)
for i in range(n-1):
    j=i+1
    a = mp[i]+i
    if(a<=n):
        cnt[a] += 1 
    b = j-mp[j]
    if(b<0):
        continue
    ans += cnt[b]
    

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
N=int(input())
A=list(map(int,input().strip().split()))

D=defaultdict(list)
for i in range(N):
    D[A[i]].append(i)

CNT={}

for k,v in D.items():
    #find ind of k in v  
    for n in v:
        if n-k>0:
            if n-k in CNT:
                CNT[n-k]+=1
            else:
                CNT[n-k]=1
Ans=0
for i in range(len(A)):
    shift=A[i]+i
    if shift in CNT:
        Ans+=CNT[shift]
print(Ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = 0
ma = defaultdict(int)

for i in range(N):
    ans += ma[i - A[i]]
    ma[i + A[i]] += 1

print(ans)

Submission status: Accepted

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

pear = 0

i_result = {}
j_result = {}

for i in range(N):
  result = str(i + int(A[i]))
  if result in i_result:
    i_result[result] += 1
  else:
    i_result[result] = 1

for j in range(N):
  result = str(j - int(A[j]))
  if result in j_result:
    j_result[result] += 1
  else:
    j_result[result] = 1

for k in i_result.keys():
  if k in j_result:
    pear += (i_result[k] * j_result[k])
      
      
print(pear)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))


def main() -> None:
    """Entry point
    """
    # 求解処理
    """
    1 <= i < j <= Nとすると、
    j - i = A_i + A_j ⇒ -A_j + j = A_i +i
    となる。
    したがって、各jについて、左辺の値を計算し、等式が成立するようなi(< j)の個数を求めればよい。
    """
    right = {}
    result = 0
    for j in range(N):
        l = -A[j] + j
        result += right.get(l, 0)
        r = A[j] + j
        right[r] = right.get(r, 0) + 1

    # 結果出力
    print(result)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import collections

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
left = {}
result = 0
for j in range(N):
    r = -A[j] + j
    result += left.get(r, 0)
    l = A[j] + j
    left[l] = left.get(l, 0) + 1

# 結果出力
print(result)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
AM = []
AP = []
AMlist = [0] * N
APlist = [0] * N

for i in range(N):
  plus = i+1 + A[i]
  AP.append(plus)  
  if AP[i] <= N:
    APlist[AP[i]-1] += 1
  minus = i+1 - A[i]
  AM.append(minus)
  if AM[i] > 0 and AM[i] <= N:
    AMlist[AM[i]-1] += 1
    
ans = 0

for j in range(N):
  ans += APlist[j] * AMlist[j]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

B = [i - a for i, a in enumerate(A)]
C = [i + a for i, a in enumerate(A)]
#print(B)
#print(C)

B_cnt = defaultdict(int)
C_cnt = defaultdict(int)
for b in B:
    B_cnt[b] += 1
for c in C:
    C_cnt[c] += 1

answer = 0
B_lst = list(B_cnt.items())
#print(B_lst)
for n, c in B_lst:
    answer += c * C_cnt[n]
#print(answer)

for i in range(N):
    if B[i] == C[i]:
        print(i)
        answer -= 1

print(answer)

Submission status: Accepted

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

memo=collections.defaultdict(int)
ans=0
for i,x in enumerate(a,1):
    ans+=memo[i-x]
    memo[i+x]+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * n

ans = 0
for i in range(n):
    tmp = i + a[i]

    if tmp < n:
        b[tmp] += 1

    if a[i] <= i and b[i - a[i]]:
        ans += b[i - a[i]]

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    d = dict()
    count = 0
    ar = [(a[i]+i+1) for i in range(n)]
    br = [(i+1-a[i]) for i in range(n)]
    for i in range(n):
        if d.get(ar[i]) is not None:
            d[ar[i]] += 1
        else:
            d[ar[i]] = 1
    c = dict()
    for i in range(n):
        if c.get(br[i]) is not None:
            c[br[i]] += 1
        else:
            c[br[i]] = 1
    count = 0
    for no in c.keys():
        if d.get(no) is not None:
            count += (c[no]*d[no])
    
    print(count)

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------


n = int(input())
a = list(mapi())
mpi = defaultdict(list)
mpj = defaultdict(list)
for i in range(n):
    mpi[a[i]+i].append(i+1)
    mpj[-a[i]+i].append(i+1)
res =0
for i in mpi.keys():
    tmpi = mpi[i]
    tmpj = mpj[i]
    m = len(tmpj)
    #print(i,tmpi,tmpj)
    for j in tmpi:
        res+=m-bisect.bisect_left(tmpj,j)
print(res)

Submission status: Accepted

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

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    num = tuple(range(1, N + 1))
    cand = 0
    log = {}
    for i in range(0, N):
        if i + 1 - A[i] in log:
            cand += log[i + 1 - A[i]]
        if i + 1 + A[i] in log:
            log[i + 1 + A[i]] += 1
        else:
            log[i + 1 + A[i]] = 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    c = [0] * n
    s = 0
    for i, a in enumerate(a_list):
        if i+a < n:
            c[i+a] += 1
        if i-a >= 0:
            s += c[i-a]
    print(s)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

dic = {}
count = 0

for i in range(n):
    if i + a[i] in dic.keys():
        dic[i + a[i]] += 1
    else:
        dic[i + a[i]] = 1

for i in range(n):
    if i - a[i] in dic.keys():
        count += dic[i - a[i]]
print(count)

Submission status: Accepted

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

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

countL = []
countR = []
for i in range(N):
  countL.append(i - A[i])
  countR.append(i + A[i])

countL = collections.Counter(countL)
countR = collections.Counter(countR)

ans = sum([countL[i] * countR[i] for i in countL.keys()])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

# process
ans = 0
check = Counter()
for i, a in enumerate(A):
    ans += check[i-a]
    check[i+a] += 1
    
# output
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N = int(input())
As = list(map(int, input().split()))

Ls = {}
Rs = {}
ct = Counter()

for idx, A in enumerate(As, start=1):
	Ls[idx] = idx + A
	ct[idx - A] +=1

ans = 0
for L_value in Ls.values():
	ans += ct[L_value]
print(ans)

Submission status: Accepted

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

# process
ans = 0
check = {}
for i, a in enumerate(A):
    x = i-a
    y = i+a
    ans += check.get(x, 0)
    check.setdefault(y, 0)
    check[y] += 1
    
# output
print(ans)

Submission status: Accepted

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

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

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

C_L = collections.Counter(L)
C_R = collections.Counter(R)
ans = 0
for l, t in C_L.items():
    if l in C_R:
        ans += t*C_R[l]
print(ans)

Submission status: Accepted

Solution code:
input()
A = [int(h) for h in input().split()]
iph_dic = {}
pair_of_spies = 0

for i, h in enumerate(A):
    if i - h in iph_dic:
        pair_of_spies += iph_dic[i - h]
    if i + h in iph_dic:
        iph_dic[i + h] += 1
    else:
        iph_dic[i + h] = 1

print(pair_of_spies)

Submission status: Accepted

Solution code:
N = int(input())
M = list(map(int, input().split()))
L = [0] * N
R = [0] * N
for i,m in enumerate(M):
  if i+m >= N:
    continue
  L[i+m] += 1
for i,m in enumerate(M[::-1]):
  if i+m >= N:
    continue
  R[i+m] += 1
R = R[::-1]
#print(L)
#print(R)
print(sum([l*r for l,r in zip(L,R)]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
MP={}
res = 0
for i, A in reversed(list(enumerate(LI(), start=1))):
    if (-A-i) in MP: res += MP[-A-i]
    if not A-i in MP:
        MP[A-i] = 0
    MP[A-i] += 1

# print(MP)

print(res)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
assert n >= 2
a = [int(x) for x in input().split()]
assert len(a) == n
ap = Counter([i + x for i, x in enumerate(a)])
am = Counter([i - x for i, x in enumerate(a)])
count = sum([v * ap.get(k, 0) for k, v in am.items() if k >= 1])
print(count)

Submission status: Accepted

Solution code:
import collections

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

L = collections.Counter(map(lambda x: x[0] + x[1] + 1, enumerate(A)))
R = collections.Counter(map(lambda x: x[0] - x[1] + 1, enumerate(A)))

res = 0
for i in range(2, N):
    res += L.get(i, 0) * R.get(i, 0)
print(res)

Submission status: Accepted

Solution code:
import collections
N=int(input())
NUM=[i for i in range(1,N+1)]
H=list(map(int, input().split()))
L_NUM=[x+y for (x,y) in zip(NUM,H)]
R_NUM=[x-y for (x,y) in zip(NUM,H)]

L_dict=collections.Counter(L_NUM)
R_dict=collections.Counter(R_NUM)

ANS=0
for i in L_dict.keys():
    cnt=L_dict[i]*R_dict[i]
    ANS+=cnt
print(ANS)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input().strip())
L = list(map(int, input().strip().split()))
seen=Counter()
ans=0
for j in range(n):
    ans+=seen[j-L[j]]
    seen[L[j]+j]+=1
print(ans)

Submission status: Accepted

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

ml = [0] * n
pl = [0] * n

out = 0

for i in range(0, n):
    if(i+a[i]<n):
        pl[i+a[i]] += 1
    if(i-a[i]>=0):
        ml[i-a[i]] += 1

for i in range(0, n):
    out += pl[i] * ml[i]

print(out)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = [int(i) for i in input().split()]

i_ai = defaultdict(list)
j_aj = defaultdict(list)
for i, h in enumerate(a):
  i_ai[i+h].append(i)
  j_aj[i-h].append(i)

cand = set(i_ai.keys()) & set(j_aj.keys())
ans = 0
for item in cand:
  ans += len(i_ai[item]) * len(j_aj[item])
print(ans)

Submission status: Accepted

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

check = {}
ans = 0

for i in range(N):
    x = i - A[i]
    y = A[i] + i
    ans += check.get(x, 0)
    check.setdefault(y, 0)
    check[y] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
my_list = list(map(int, input().split()))
my_dict1 = {}
my_dict2 = {}

# j - i == Aj + Ai
# j - Aj == Ai + i

#Ai + i
for i in range(N):
    key = my_list[i] + i
    if key in my_dict1.keys():
        my_dict1[key] += 1
    else:
        my_dict1[key] = 1

#j - Aj
for j in range(N):
    key = j - my_list[j]
    if key in my_dict2.keys():
        my_dict2[key] += 1
    else:
        my_dict2[key] = 1


ans = 0
for key in my_dict1.keys():
    if key in my_dict2.keys():
        ans += my_dict1[key] * my_dict2[key]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase
from collections import defaultdict

import __pypy__


def main():
    n = int(input())
    a = [int(i) for i in input().split(" ")]
    s = defaultdict(int)
    ans = 0
    for i in xrange(n):
        ans += s[a[i]-i]
        s[-i-a[i]] += 1
    print(ans)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

n = int(raw_input())
a = [int(i) for i in raw_input().split(' ')]
s = defaultdict(int)
ans = 0

for i in xrange(n):
  ans += s[a[i] - i]
  s[-i-a[i]] += 1

print ans

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
dp = [0] * n
ans = 0
for i,j in enumerate(a):
    if i + j < n:
        dp[i+j] += 1
    if 0 < i-j:
        ans += dp[i-j]
print(ans)

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    A = list(map(int, input().split(" ")))
    # print(N)
    # print(A)
    d_i = {}
    d_j = {}

    for i, ai in enumerate(A):
        p = ai -i
        if p in d_i.keys():
            d_i[p] +=1
        else:
            d_i[p] = 1
        p = -ai - i
        if p in d_j.keys():
            d_j[p] +=1
        else:
            d_j[p] = 1
    # print(d_i)
    # print(d_j)

    ans = 0
    for q in list(set(d_i.keys()) & set(d_j.keys())):
        ans += d_i[q]*d_j[q]
    print(ans)


    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
pair=0
As={}

for i in range(N):
    a=A[i]
    x1=i+1-a
    x2=i+1+a
    if x1 in As:
        pair+=As[x1]
    if x2 in As:
        As[x2]+=1
    else:
      As[x2]=1
print(pair)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
ans = 0
for i, j in enumerate(a):
    if i + j < n:
        dp[i + j] += 1
    if 0 < i - j:
        ans += dp[i - j]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import defaultdict, deque

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()

def main():
	n = int(rl())
	A = deque((int(x) for x in rll()))
	A.appendleft(0)
	store = defaultdict(lambda: 0)
	#j - i = A[j] + A[i]
	#-(A[i] + i) = A[j] - j
	ans = 0
	for i in range(1, n+1):
		val = A[i] - i 
		ans += store[val]
		store[-(A[i] + i)] += 1
	stdout.write(str(ans));stdout.write("\n")
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
import collections
import bisect
N=int(input())
# N,M=map(int,input().split())
# S=[[]for i in range(N)]
# # for i in range(Q):
A=list(map(int,input().split()))
# #     S[i]=a
L=[i-A[i] for i in range(N)]
R=[i+A[i] for i in range(N)]
L.sort()
R.sort()
ans=0
for i in R:
    ans+=-bisect.bisect_left(L,i)+bisect.bisect_right(L,i)
print(ans)

Submission status: Accepted

Solution code:
import math
import collections
N=int(input())
# N,M=map(int,input().split())
# S=[[]for i in range(N)]
# # for i in range(Q):
A=list(map(int,input().split()))
# #     S[i]=a
D=dict()
ans=0
for i in range(N):
    a=A[i]+i
    if a in D.keys():
        D[a]+=1
    else:
        D[a] = 1
    b=i-A[i]
    if b in D.keys():
        ans+=D[b]


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
backward = [0] * n
forward = [0] * n
for i, a in enumerate(A):
    if i + a < n:
        forward[i + a] += 1
    if i - a >= 0:
        backward[i - a] += 1
ans = 0
for x, y in zip(forward, backward):
    ans += x * y
print(ans)

Submission status: Accepted

Solution code:
def main():
    _ = input()
    lst_a = [int(a) for a in input().strip().split(' ')]

    # build hash table
    hash_tbl = {}
    for i, a_i in enumerate(lst_a):
        n_i = i + 1
        tmp = int(n_i - a_i)
        if tmp > 0:
            if tmp in hash_tbl.keys():
                hash_tbl[tmp].append(n_i)
            else:
                hash_tbl[tmp] = [n_i]

    ans = 0
    for j, a_j in enumerate(lst_a):
        n_j = j + 1
        tmp = int(n_j + a_j)
        if tmp in hash_tbl.keys():
            ans += len(hash_tbl[tmp])
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    _ = input()
    lst_a = [int(a) for a in input().strip().split(' ')]

    # build hash table
    hash_tbl = {}
    for i, a_i in enumerate(lst_a):
        n_i = i + 1
        tmp = int(n_i - a_i)
        if tmp > 0:
            if tmp in hash_tbl.keys():
                hash_tbl[tmp].append(n_i)
            else:
                hash_tbl[tmp] = [n_i]

    ans = 0
    for j, a_j in enumerate(lst_a):
        n_j = j + 1
        tmp = int(n_j + a_j)
        if tmp in hash_tbl.keys():
            # ans += len([idx for idx in hash_tbl[tmp] if idx > j])
            ans += len(hash_tbl[tmp])
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# i < j
# j - i = Aj + Ai
# j - Aj = i + Ai

ans = 0
adds = dict()
for j in range(n):
    sub = j - a[j]
    if sub in adds.keys():
        ans += adds[sub]

    add = j + a[j]
    if add in adds.keys():
        adds[add] += 1
    else:
        adds[add] = 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
*A, = map(int, input().split())
B = [A[i] + i for i in range(n)]
C = [i - A[i] for i in range(n)]
B.sort()
C.sort()
ans = 0
for b in B:
    ans += bisect.bisect_right(C, b) - bisect.bisect_left(C, b)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=["-1"]+list(map(int,input().split()))

S={}
D={}

for i in range(1,n+1):
    a=A[i]
    if a+i in S.keys():
        S[a+i]+=1
    else:
        S[a+i]=1
    if i-a in D.keys():
        D[i-a]+=1
    else:
        D[i-a]=1
    
ans=0

for k in S.keys():
    if k in D.keys():
        ans+=S[k]*D[k]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

L = []
R = []

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

L = list(Counter(L).items())
R = dict(list(Counter(R).items()))

ans = 0

for i ,j in L:
    if i in R:
        ans += j * R[i]

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc166/tasks/abc166_e

from collections import defaultdict

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

# j - i = Ai + Aj (i < j)
# i + Ai = j - Aj
# Li = Ri

ans = 0
memo = defaultdict(int)  # i + Aiを記録

for i in range(N):
    # i + Ai
    memo[i + 1 + A[i]] += 1


# jについて，j > iの値を確認
for j in range(N):
    ans_j = j + 1 - A[j]
    if ans_j in memo:
        ans += memo[ans_j]

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	N = int(input())
	ls = [int(a) for a in input().split()]
	c = 0
	dic = {}
	for i in range(N):
		h = ls[i]
		if i > 0:
			c += dic.get(i-h,0)
		v = dic.get(i+h,0)
		if v == 0:
			dic[i+h] = 1
		else:
			dic[i+h] += 1

	print(c)

Submission status: Accepted

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

check = {}
ans = 0

for i in range(N):
    x = i - A[i]
    y = A[i] + i
    ans += check.get(x, 0)
    check.setdefault(y, 0)
    check[y] += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(n-1):
  idx = i + a[i] + 1
  if idx in dic:
    dic[idx] += 1
  else:
    dic[idx] = 1
ans = 0
j = n-1
while j > 0:
  target = j + 1 - a[j]
  idx = j + 1 + a[j]
  if target in dic:
    ans += dic[target]
  if j < n-1:
  	dic[idx] -= 1
  j -= 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [0]*n
    R = [0]*n
    for i,ai in enumerate(a):
        L[i] = i+ai
        R[i] = i-ai
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    c = Counter(R)
    for Li in L:
        count += c.get(Li,0)

    print(count)

main()

Submission status: Accepted

Solution code:
import collections

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

tmp = [0 for _ in range(N)]
for i in range(N):
  tmp[i] = (i + 1) + A[i]

c = collections.Counter(tmp)

ans = 0
for i in range(N):
  aj = (i+1) - A[i]
  ans += c[aj]

print(ans)
  
'''
i < jとする
A[i] + A[j] = j - i
A[i] + i = j - A[j]
K = j - A[j]
'''

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

# i < j
# j - i == Ai + Aj
# j - Aj == i + Ai

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

ans = 0
# key: i + Ai, value: count
d = {}

for j in range(n):
    a1 = j - a[j]
    try:
        ans += d[a1]
    except KeyError:
        d[a1] = 0

    a2 = j + a[j]
    try:
        d[a2] += 1
    except KeyError:
        d[a2] = 1

print(ans)