ABC_166_E - This Message Will Self-Destruct in 5s

[zeikar]

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;
}