1520-D, *1200

Problem - 1520D - Codeforces

문제

• $n(1\leq n \leq 2\cdot 10^{5})$개의 수열 $a_{1}a_{2}...a_{n}(1\leq a_{i} \leq n)$이 주어진다
• $i < j,\ a_{j}-a_{i}=j-i$인 좌표쌍 $(i,\ j)$의 개수는?

 

$O(n)$

조건식을 변형하면
$$a_{j}-j=a_{i}-i$$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
 
ll n;
 
ll C(ll m)
{
    if(m == 1) return 0;
    else return m*(m-1)/2;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    int tmp;
    while(t--){
        map<int, int> m;
        cin >> n;
        loop(i, n){
            cin >> tmp;
            m[tmp-i]++;
        }
 
        ll res = 0;
        for(const auto& e: m) res += C(e.second);
 
        cout << res << endl;
    }
 
    return 0;
}cs