ABC_166_E - This Message Will Self-Destruct in 5s #48
Description
Problem link
https://atcoder.jp/contests/abc166/tasks/abc166_e
Problem Summary
배열에서 두 원소를 선택할 때 값의 합이 인덱스의 차이의 절댓값이 되는 경우의 수를 구하는 문제.
Solution
뭔가 수학적인 것이 보일 듯 해서 정리를 해봤다.
Ai + Aj == | j - i |
j > i로 고정하고 절댓값을 풀면 j - Aj = i + Ai 가 되는데 i + Ai가 몇개인지 계속 더해주면서 j에 대해 j - Aj 개수를 더해주면 된다.
참고: https://codeforces.com/blog/entry/76833?#comment-614685
Source Code
#include <iostream>
#include <map>
using namespace std;
int a[200000];
map<int, int> diff;
int main() {
int n;
cin >> n;
long long res = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
res += diff[i - a[i]];
diff[a[i] + i]++;
}
cout << res << endl;
}